LOJ6777

_SeeleVollerei_ · 2023-05-23 19:15:38 · 个人记录

考虑维护没火的连续段。

可以证明，每次暴力枚举所有连续段并缩减，复杂度上界为 O(q\sqrt n)。

考虑证明。

首先每次操作只会贡献 O(1) 个连续段，所以整个过程涉及连续段个数只有 O(q) 个。

对于 >\sqrt n 的连续段，每一时刻只有至多 \sqrt n 个。

对于 \le \sqrt n 的连续段，在经过至多 \sqrt n 时刻后这个连续段就会消失。

到了这里就可以对连续段根号分治，可行但没必要。

因为这两个结论往下推一下你就会发现，每一时刻连续段个数就是 O(\sqrt n) 的。

所以每次直接暴力枚举所有连续段。

那么后两个操作就是分裂连续段，以及合并若干个连续的连续段。

剩下的操作相当于，加一个区间的点，删 O(\sqrt n) 个点，区间加，区间求和。

可以线段树，但是 O(\sqrt n) 的删点再多个 \log 比较危险。实际上可以分块，每次删点都大力判断 tag 然后 pushdown。分析一下会发现是均摊 O(q\sqrt n) 的。因为我懒这里就不写怎么分析的了。

实现上拿个 vector 存连续段，然后写个分块就行了，很好写。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> pr;
const int N=1e5+5;
const int block=320;
const int M=320;
int n,q;
inline int Read(){
    char ch;
    int f=1;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-') f=-1;
    int x=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
inline void print(LL x){
    if(x>=10) print(x/10);
    putchar(x%10+48);
    return ;
}
inline void Print(LL x,char ch='\n'){
    if(x<0){
        putchar('-');
        print(-x);
    }
    else print(x);
    putchar(ch);
    return ;
}
inline int Max(int x,int y){
    return x>y?x:y;
}
inline int Min(int x,int y){
    return x<y?x:y;
}
inline void Cmax(int&x,int y){
    if(y>x) x=y;
    return ;
}
inline void Cmin(int&x,int y){
    if(y<x) x=y;
    return ;
}
struct DS{
    LL val[N],sum[M],tag[M];
    bool tagvis[M];
    LL tagall[M];
    int cnt[M];
    bool vis[N];
    int bl[M],br[M],t;
    int pos[N];
    inline void Init(){
        while(br[t]<n){
            ++t;
            bl[t]=br[t-1]+1;
            br[t]=Min(bl[t]+block-1,n);
            for(int i=bl[t];i<=br[t];i++){
                pos[i]=t;
                val[i]=Read();
                sum[t]+=val[i];
                vis[i]=1;
            }
            cnt[t]=br[t]-bl[t]+1;
        }
        return ;
    }
    inline void PushDown(int p){
        if(tag[p]){
            for(int i=bl[p];i<=br[p];i++)
                if(vis[i]) val[i]+=tag[p];
            tag[p]=0;
        }
        if(tagall[p]){
            for(int i=bl[p];i<=br[p];i++)
                val[i]+=tagall[p];
            tagall[p]=0;
        }
        if(tagvis[p]){
            cnt[p]=br[p]-bl[p]+1;
            for(int i=bl[p];i<=br[p];i++)
                vis[i]=1;
            tagvis[p]=0;
        }
        return ;
    }
    inline void Add(int ql,int qr,int value){
        int p=pos[ql],q=pos[qr];
        if(p==q){
            PushDown(p);
            for(int i=ql;i<=qr;i++)
                if(vis[i]){
                    val[i]+=value;
                    sum[p]+=value;
                }
            return ;
        }
        PushDown(p);
        for(int i=ql;i<=br[p];i++)
            if(vis[i]){
                val[i]+=value;
                sum[p]+=value;
            }
        for(int i=p+1;i<=q-1;i++)
            if(tagvis[i]){
                sum[i]+=1ll*value*(br[i]-bl[i]+1);
                tagall[i]+=value;
            }
            else{
                sum[i]+=1ll*value*cnt[i];
                tag[i]+=value;
            }
        PushDown(q);
        for(int i=bl[q];i<=qr;i++)
            if(vis[i]){
                val[i]+=value;
                sum[q]+=value;
            }
        return ;
    }
    inline void Add(int ql,int qr){
        int p=pos[ql],q=pos[qr];
        if(p==q){
            PushDown(p);
            for(int i=ql;i<=qr;i++)
                if(!vis[i]){
                    vis[i]=1;
                    cnt[p]++;
                }
            return ;
        }
        PushDown(p);
        for(int i=ql;i<=br[p];i++)
            if(!vis[i]){
                vis[i]=1;
                cnt[p]++;
            }
        for(int i=p+1;i<=q-1;i++)
            tagvis[i]=1;
        PushDown(q);
        for(int i=bl[q];i<=qr;i++)
            if(!vis[i]){
                vis[i]=1;
                cnt[q]++;
            }
        return ;
    }
    inline void Del(int x){
        int p=pos[x];
        PushDown(p);
        if(vis[x]){
            sum[p]-=val[x];
            cnt[p]--;
            val[x]=vis[x]=0;
        }
        return ;
    }
    inline LL Query(int ql,int qr){
        LL ss=0;
        int p=pos[ql],q=pos[qr];
        if(p==q){
            PushDown(p);
            for(int i=ql;i<=qr;i++)
                if(vis[i]) ss+=val[i];
            return ss;
        }
        PushDown(p);
        for(int i=ql;i<=br[p];i++)
            if(vis[i]) ss+=val[i];
        for(int i=p+1;i<=q-1;i++)
            ss+=sum[i];
        PushDown(q);
        for(int i=bl[q];i<=qr;i++)
            if(vis[i]) ss+=val[i];
        return ss;
    }
}ds;
vector<pr>in;
vector<pr>in1;
inline void WorkFire(){
    in1.clear();
    for(int i=0;i<in.size();i++){
        int l=in[i].first,r=in[i].second;
        if(l!=1) ds.Del(l++);
        if(r!=n) ds.Del(r--);
        if(l<=r) in1.push_back(make_pair(l,r));
    }
    in=in1;
    return ;
}
inline void AddFire(int x){
    in1.clear();
    ds.Del(x);
    for(int i=0;i<in.size();i++){
        int l=in[i].first,r=in[i].second;
        if(x>r||x<l) in1.push_back(make_pair(l,r));
        else{
            if(x>l) in1.push_back(make_pair(l,x-1));
            if(x<r) in1.push_back(make_pair(x+1,r));
        }
    }
    in=in1;
    return ;
}
inline void Clear(int ql,int qr){
    in1.clear();
    ds.Add(ql,qr);
    int i=0;
    while(i<in.size()&&in[i].second<ql-1)
        in1.push_back(in[i++]);
    int nowl=ql,nowr=qr;
    while(i<in.size()&&in[i].first<=qr+1){
        Cmin(nowl,in[i].first);
        Cmax(nowr,in[i].second);
        i++;
    }
    in1.push_back(make_pair(nowl,nowr));
    while(i<in.size()) in1.push_back(in[i++]);
    in=in1;
    return ;
}
inline void Init(){
    n=Read(),q=Read();
    ds.Init();
    in.push_back(make_pair(1,n));
    return ;
}
inline void Solve(){
    for(;q;q--){
        int opt=Read();
        if(opt==1){
            int ql=Read(),qr=Read();
            int value=Read();
            ds.Add(ql,qr,value);
        }
        if(opt==2){
            int ql=Read(),qr=Read();
            Print(ds.Query(ql,qr));
        }
        if(opt==3){
            int x=Read();
            AddFire(x);
        }
        if(opt==4){
            int ql=Read(),qr=Read();
            Clear(ql,qr);
        }
        WorkFire();
    }
    return ;
}
#include<ctime>
int main(){
    //#define LOCAL
    #ifdef LOCAL
    int st=clock();
    #endif
    Init();
    Solve();
    #ifdef LOCAL
    int en=clock();
    printf("cost %d ms\n",en-st);
    #endif
    return 0;
}