P8441

letitdown · 2022-07-31 09:38:03 · 题解

我们考虑使用 std::set 维护每种颜色出现的连续段。

下面对于一个连续段使用 L,R 表示，对于一个询问区间使用 l,r 表示。

对于一次询问，我们钦定一种颜色的贡献由 [l,r] 包含或相交的最左端的 [L,R] 给出。

那么若现在在颜色 c 中有两个相邻的连续段 [L_1,R_1],[L_2,R_2]，那么第二个连续段的贡献形式就是对于 l\in(R_1,R_2],r\in[L_2,n] 的询问答案增加 c 。删除一个连续段的贡献形式是类似的。

对于这样的矩形加单点查形式，我们考虑使用树套树或者 KD 树维护，由于颜色段均摊，复杂度是 O(nlog^2n) 或者 O(n\sqrt{n}) 的。

但是本题的空间限制不能满足树套树 O(n\log^2n) 的需求，使用 KD 树的常数较大，不能保证通过本题。

但是我们发现本题并没有强制在线，所以把所有操作离线下来进行 CDQ 分治即可。

时间复杂度 O(n\log^2n)，空间复杂度 O(n)。

Code

#include<set>
#include<cassert>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
namespace EMT{
    typedef long long ll;typedef double db;
    #define pf printf
    #define F(i,a,b) for(int i=a;i<=b;i++)
    #define D(i,a,b) for(int i=a;i>=b;i--)
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
    inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
    inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
    inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
    const int N=1e5+10;
    struct qs{int opt,x,l,r,v;friend bool operator <(qs a,qs b){return a.x<b.x;}}q[N*10];
    int n,m,qcnt;
    struct BIT{
        ll t[N];
        inline void add(int x,int v){while(x<=n)t[x]+=v,x+=x&-x;}
        inline void add(int l,int r,int v){add(l,v),add(r+1,-v);}
        inline ll ask(int x){ll ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
    }bit;
    ll ans[N];
    struct dp{int l,r;friend bool operator <(dp a,dp b){return a.l<b.l;}};
    std::set<dp>s[N];
    inline void add(int l,int r,int ql,int qr,int v){
        q[++qcnt]={1,l,ql,qr,v},
        q[++qcnt]={1,r+1,ql,qr,-v};
    }
    inline int ask(std::set<dp> &s,std::set<dp>::iterator it){
        if(it==s.begin())return 1;it--;return it->r+1;
    }
    inline void ins(int v,int l,int r){
        if(1){
            auto it=s[v].upper_bound({r,r});
            if(it!=s[v].begin()){
                it--;
                if(it->r>=r&&it->l<=l)return;
            }
        }
        auto it=s[v].upper_bound({r,r});bool fl=0;
        if(it!=s[v].end()){
            add(ask(s[v],it),it->r,it->l,n,-v);
            if(it->l==r+1){r=it->r;it=s[v].erase(it);fl=1;}
        }
        while(it!=s[v].begin()){
            it--;
            if(l<=it->l&&it->r<=r){add(ask(s[v],it),it->r,it->l,n,-v);it=s[v].erase(it);continue;}
            if(it->r+1<l)break;
            if(it->r+1==l){add(ask(s[v],it),it->r,it->l,n,-v);l=it->l;s[v].erase(it);break;}
            if(it->r>r){add(ask(s[v],it),it->r,it->l,n,-v);r=it->r;it=s[v].erase(it);continue;}
            assert(it->l<=l);l=it->l;add(ask(s[v],it),it->r,it->l,n,-v);it=s[v].erase(it);break;
        }
        if(!fl){
            it=s[v].upper_bound({r,r});
            if(it!=s[v].end())add(r+1,it->r,it->l,n,v);
        }
        it=s[v].insert({l,r}).first;add(ask(s[v],it),r,l,n,v);
    }
    inline void cdq(int l,int r){
        if(l==r)return;
        int mid=(l+r)>>1;
        cdq(l,mid),cdq(mid+1,r);
        std::sort(q+l,q+mid+1),
        std::sort(q+mid+1,q+r+1);
        int j=l;
        F(i,mid+1,r){
            while(q[i].x>=q[j].x&&j<=mid){
                if(q[j].opt==1)bit.add(q[j].l,q[j].r,q[j].v);
                j++;
            }if(q[i].opt==2)ans[q[i].v]+=bit.ask(q[i].r);
        }
        while(j>l){
            j--;
            if(q[j].opt==1)bit.add(q[j].l,q[j].r,-q[j].v);
        }
    }
    inline short main(){
        n=read();m=read();
        memset(ans,-1,sizeof(ans));
        F(i,1,m){
            int opt=read(),l=read(),r=read();
            if(opt==1){ins(read(),l,r);}
            else q[++qcnt]={2,l,r,r,i},ans[i]=0;
        }
        cdq(1,qcnt);
        F(i,1,m)if(~ans[i])pf("%lld\n",ans[i]);
        return 0;
    }
}
signed main(){return EMT::main();}