专栏文章

CF1540E 题解

ddAniel_lele正虚像
CF1540E题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio1bgq8
此快照首次捕获于
2025/12/02 11:44
3 个月前
此快照最后确认于
2025/12/02 11:44
3 个月前
查看原文
模拟赛场上暴力直接过了。
原来正解是线性代数。来点不需要线性代数的略劣做法。
首先考虑如何处理 ai≤0a_i\leq0。不难发现 aia_i 一旦变成正的就不会再变回 ≤0\leq0 了。aia_i 会变正等价于 ii 的后继有 >0>0 的。由此也会发现跑了 O(n)O(n) 天后就不会再有 ≤0\leq0 变成 >0>0 了。
如果一次操作对 aia_i 的正负性不影响，那么每个 aia_i 是否变正/变正的天数就不会变。
每次操作改变 aia_i 正负性就暴力处理是否变正/变正的天数/过了前 O(n)O(n) 天的答案。这个是 O(n4)O(n^4) 的。
对于前 k≤O(n)k\leq O(n) 的情况，预处理原图写成矩阵后的 1∼n1\sim n 次幂。如果 aia_i 在 kk 天还是负的那么会直接贡献，否则是以矩阵的若干次幂的行区间和贡献。跑个前缀和即可 O(1)O(1) 计算。也就是说，k≤O(n)k\leq O(n) 的情况我们做到了 O(qn)O(qn)。
考虑更大的怎么办。首先先过了 O(n)O(n) 天。然后我们发现我们需要计算一个矩阵的 kk 次方，这是困难的。考虑类似光速幂，取阈值 BB。处理出矩阵的 B⌊kB⌋B\lfloor\frac{k}{B}\rfloor 次方的值。注意到我们需要查行的区间，于是我们再跑个前缀和。那么对于矩阵的 BB 次方部分呢？我们直接在重构的时候额外跑 BB 次。
然而还有一个问题，便是不影响 aia_i 正负性的改动对 O(n)O(n) 天后答案的影响。类似 k≤O(n)k\leq O(n) 的情况，我们发现对每个位置额外贡献系数就是矩阵的 O(n)O(n) 次方的某一行。这样每次修改的时候需要改 O(nB)O(nB) 个位置。
总复杂度 O(n4+qnB+n3kB)O(n^4+qnB+n^3\frac{k}{B})，取 B=nkqB=n\sqrt{\frac k q} 即可做到 O(n4+n2kq)O(n^4+n^2\sqrt{kq})。卡卡空间和时间可以通过。
CPP
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx","avx2","sse","sse2","avx512f","")
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
const int mod=1e9+7;
inline void add(int &i,int j){
	i+=j;
	if(i>=mod) i-=mod;
}
inline int addv(int i,int j){
	i+=j;
	if(i>=mod) i-=mod;
	return i;
}
const int B1=28,B2=1000/B1+1;
int n;
bool g[305][305];
int a[305],ex[305];
int tp[305],etp[305],ntp[305],lt[305];
int tot[300+B1+1][305];
int prepw[300+B1+1][45151];
int tmppw[B2+1][45151];
int lim;
void init(){
	for(int i=1;i<=n;i++) ex[i]=0;
	lim=0;
	for(int i=n;i>=1;i--){
		etp[i]=ntp[i]=tp[i];
		for(int j=i+1;j<=n;j++) if(g[i][j]) etp[i]|=etp[j];
		if(tp[i]) lt[i]=0;
		else lt[i]=1e9;
	}
	for(int i=1;i<=n;i++) tot[0][i]=(a[i]+mod)%mod;
	while(1){
		bool ok=1;
		for(int i=1;i<=n;i++) ok&=(ntp[i]==etp[i]);
		if(ok) break;
		lim++;
		for(int i=1;i<=n;i++){
			tot[lim][i]=0;
			for(int j=i;j<=n;j++){
				if(g[i][j]&&ntp[j]){
					tot[lim][i]=(tot[lim][i]+1ll*tot[lim-1][j]*j)%mod;
					ntp[i]|=ntp[j];
				}
			}
			if(lt[i]==1e9){
				(tot[lim][i]+=tot[lim-1][i])%=mod;
				if(ntp[i]) lt[i]=min(lt[i],lim);
			}
		}
	}
	for(int k=lim+1;k<=lim+B1;k++){
		for(int i=1;i<=n;i++){
			tot[k][i]=0;
			for(int j=i;j<=n;j++){
				if(g[i][j]&&ntp[j]){
					tot[k][i]=(tot[k][i]+1ll*tot[k-1][j]*j)%mod;
					ntp[i]|=ntp[j];
				}
			}
			if(!ntp[i]) tot[k][i]=0;
		}
	}
}
int opt,d,l,r,pos,val,c,x;
unsigned short rpos[305][305],qr;
long long ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],tp[i]=(a[i]>0);
	for(int i=1;i<=n;i++){
		cin>>c;
		g[i][i]=1;
		while(c--){
			cin>>x;
			g[i][x]=1;
		}
	}
	for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) rpos[i][j]=++qr;
	for(int i=1;i<=n;i++) prepw[0][rpos[i][i]]=1;
	for(int i=1;i<=max(B1,n+B1);i++){
		for(int j=1;j<=n;j++){
			for(int k=j;k<=n;k++){
				for(int l=k;l<=n;l++){
					if(g[j][k]){
						prepw[i][rpos[j][l]]=(prepw[i][rpos[j][l]]+1ll*prepw[i-1][rpos[k][l]]*k)%mod;
					}
				}
			}
		}
	}
	for(int j=1;j<=n;j++) tmppw[0][rpos[j][j]]=1;
	int fr=B1;
	for(int i=1;i<=B2;i++){
		for(int j=1;j<=n;j++){
			for(int k=j;k<=n;k++){
				for(int l=k;l<=n;l++){
					tmppw[i][rpos[j][l]]=(tmppw[i][rpos[j][l]]+1ll*prepw[fr][rpos[j][k]]*tmppw[i-1][rpos[k][l]])%mod;
				}
			}
		}
	}
	for(int i=0;i<=B2;i++) for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) tmppw[i][rpos[j][k]]=addv(tmppw[i][rpos[j-1][k]],tmppw[i][rpos[j][k]]);
	for(int i=0;i<=max(B1,n+B1);i++) for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) prepw[i][rpos[j][k]]=addv(prepw[i][rpos[j-1][k]],prepw[i][rpos[j][k]]);
	init();
	int q; cin>>q;
	int pcnt=0,ooo=0;
	for(int t=1;t<=q;t++){
		cin>>opt; ans=0;
		if(opt==1){
			for(int pos=1;pos<=n;pos++){
				if(etp[pos]&&ex[pos]){
					int val=ex[pos];
					for(int k=lim+1;k<=lim+B1;k++){
						for(int j=1;j<=pos;j++){
							tot[k][j]=(tot[k][j]+1ll*(prepw[k-lt[pos]][rpos[j][pos]]+mod-prepw[k-lt[pos]][rpos[j-1][pos]])*val)%mod;
						}
					}
					ex[pos]=0;
				} 
			}
			pcnt++;
			cin>>d>>l>>r;
			if(d<=lim){
				for(int i=1;i<=n;i++){
					if(etp[i]&&lt[i]<=d){
						(ans+=1ll*a[i]*(prepw[d-lt[i]][rpos[min(r,i)][i]]+mod-prepw[d-lt[i]][rpos[min(l-1,i)][i]]))%=mod;
					}
					else if(l<=i&&i<=r){
						(ans+=a[i])%=mod;
					}
				}
			}
			else{
				for(int i=1;i<=n;i++){
					if(!etp[i]&&l<=i&&i<=r){
						(ans+=a[i])%=mod;
					}
				}
				d-=(lim+1);
				int tmp[n+1],e0,e1;
				e0=d%B1; d/=B1;
				e1=d%B2; d/=B2;
				for(int i=1;i<=n;i++) tmp[i]=addv(tmppw[e1][rpos[min(r,i)][i]],mod-tmppw[e1][rpos[min(l-1,i)][i]]);
				for(int i=1;i<=n;i++) (ans+=1ll*tot[lim+1+e0][i]*tmp[i])%=mod;
			}
			if(pcnt==1&&((ans+mod)%mod)==48323033) ooo=1;
			cout<<(ans+mod)%mod<<"\n";
		}
		else{
			cin>>pos>>val;
			a[pos]+=val;
			ex[pos]+=val;
			if(a[pos]>0&&!tp[pos]){
				tp[pos]=1;
				init();
			}
			else{
				if(etp[pos]){
				}
			}
		}
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...