CF1540E 题解

· · 题解

模拟赛场上暴力直接过了。

原来正解是线性代数。来点不需要线性代数的略劣做法。

首先考虑如何处理 a_i\leq0。不难发现 a_i 一旦变成正的就不会再变回 \leq0 了。a_i 会变正等价于 i 的后继有 >0 的。由此也会发现跑了 O(n) 天后就不会再有 \leq0 变成 >0 了。

如果一次操作对 a_i 的正负性不影响，那么每个 a_i 是否变正/变正的天数就不会变。

每次操作改变 a_i 正负性就暴力处理是否变正/变正的天数/过了前 O(n) 天的答案。这个是 O(n^4) 的。

对于前 k\leq O(n) 的情况，预处理原图写成矩阵后的 1\sim n 次幂。如果 a_i 在 k 天还是负的那么会直接贡献，否则是以矩阵的若干次幂的行区间和贡献。跑个前缀和即可 O(1) 计算。也就是说，k\leq O(n) 的情况我们做到了 O(qn)。

考虑更大的怎么办。首先先过了 O(n) 天。然后我们发现我们需要计算一个矩阵的 k 次方，这是困难的。考虑类似光速幂，取阈值 B。处理出矩阵的 B\lfloor\frac{k}{B}\rfloor 次方的值。注意到我们需要查行的区间，于是我们再跑个前缀和。那么对于矩阵的 B 次方部分呢？我们直接在重构的时候额外跑 B 次。

然而还有一个问题，便是不影响 a_i 正负性的改动对 O(n) 天后答案的影响。类似 k\leq O(n) 的情况，我们发现对每个位置额外贡献系数就是矩阵的 O(n) 次方的某一行。这样每次修改的时候需要改 O(nB) 个位置。

总复杂度 O(n^4+qnB+n^3\frac{k}{B})，取 B=n\sqrt{\frac k q} 即可做到 O(n^4+n^2\sqrt{kq})。卡卡空间和时间可以通过。

#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;
}