题解：P14164 [ICPC 2022 Nanjing R] 命题作文

· · 题解

分三种情况讨论：

显然前两种拿一个 set 就做完了。

对于第三种，考虑直接大力维护覆盖集合，对每种覆盖集合顺序维护下标，每次修改枚举影响到的覆盖集合，使用平衡树维护修改，修改次数是 O(n) 的，复杂度 O(n\log n)。

那么只需考虑如何找发生了修改的集合，也就是同时在区间内外都有元素的集合，我们对每个点维护其同色的前驱和后继，挂线段树上维护区间最值即可，复杂度也是 O(n\log n)。

const int N=2.5e5+5;

int n,m;
set<int> s0,s1;
ll ans;

int tot,col[N];
int rt[N],ls[N],rs[N],sz[N],fa[N];
ll pri[N];auto rnd=mt19937_64(1017);
il void upd(int x){sz[x]=sz[ls[x]]+1+sz[rs[x]],fa[x]=0,fa[ls[x]]=fa[rs[x]]=x;}
il void pud(int x){col[ls[x]]=col[rs[x]]=col[x];}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(pri[x]>pri[y])return pud(x),rs[x]=merge(rs[x],y),upd(x),x;
    else return pud(y),ls[y]=merge(x,ls[y]),upd(y),y;
}
void split(int v,int x,int &rta,int &rtb){
    if(!x)return rta=rtb=0,void();
    pud(x);
    if(x<v)split(v,rs[x],rs[x],rtb),rta=x;
    else split(v,ls[x],rta,ls[x]),rtb=x;
    upd(x);
}
il int gc(int x){
    while(fa[x])x=fa[x];
    return col[x];
}
il int lf(int x){
    while(ls[x])x=ls[x];
    return x;
}
il int ri(int x){
    while(rs[x])x=rs[x];
    return x;
}
int pre[N],nxt[N];
int dp[N<<2],dn[N<<2];
il int cp(int a,int b){return pre[a]<pre[b]?a:b;}
il int cn(int a,int b){return nxt[a]>nxt[b]?a:b;}
il void upd1(int x){dp[x]=cp(dp[x<<1],dp[x<<1|1]),dn[x]=cn(dn[x<<1],dn[x<<1|1]);}
void build(int x=1,int l=1,int r=n){
    if(l==r)return dp[x]=dn[x]=l,void();
    int m=l+r>>1;build(x<<1,l,m),build(x<<1|1,m+1,r);
    upd1(x);
}
void update(int k,int x=1,int l=1,int r=n){
    if(l==r||!k)return ;
    int m=l+r>>1;k<=m?update(k,x<<1,l,m):update(k,x<<1|1,m+1,r);
    upd1(x);
}
int qp(int lq,int rq,int x=1,int l=1,int r=n){
    if(lq<=l&&r<=rq)return dp[x];
    int m=l+r>>1;
    if(rq<=m)return qp(lq,rq,x<<1,l,m);
    if(m<lq)return qp(lq,rq,x<<1|1,m+1,r);
    return cp(qp(lq,rq,x<<1,l,m),qp(lq,rq,x<<1|1,m+1,r));
}
int qn(int lq,int rq,int x=1,int l=1,int r=n){
    if(lq<=l&&r<=rq)return dn[x];
    int m=l+r>>1;
    if(rq<=m)return qn(lq,rq,x<<1,l,m);
    if(m<lq)return qn(lq,rq,x<<1|1,m+1,r);
    return cn(qn(lq,rq,x<<1,l,m),qn(lq,rq,x<<1|1,m+1,r));
}

int T;
il ll calc0(){return s0.size()*(n-1+T-s0.size());}
il ll calc1(){return s1.size();}
il ll calc2(ll v){return v*(v-1)/2;}

void INIT(){}
void MAIN(){
    read(n,m);
    s0.clear(),s1.clear();
    repl(i,1,n)s0.insert(i);
    T=0;ans=calc0()+calc2(n-1);
    rt[1]=0;
    tot=1;repl(i,1,n)pri[i]=rnd(),ls[i]=rs[i]=0,sz[i]=1,col[i]=1,rt[1]=merge(rt[1],i);
    pre[1]=1;repl(i,2,n)pre[i]=i-1;
    nxt[n-1]=n-1;per(i,n-2,1)nxt[i]=i+1;
    build();
    rep(i,1,m){
        int l,r;read(l,r);
        if(l>r)swap(l,r);--r;
        auto it=s0.begin();
        ans-=calc0()+calc1();
        while((it=s1.lower_bound(l))!=s1.end()&&*it<=r)s1.erase(it);
        while((it=s0.lower_bound(l))!=s0.end()&&*it<=r)s1.insert(*it),s0.erase(it);
        T=i;ans+=calc0()+calc1();
        if(l>r){put(ans);continue;}
        int t;
        while(pre[t=qp(l,r)]<l||nxt[t=qn(l,r)]>r){
            int c0=gc(t),c1=++tot;rt[c1]=0;
            ans-=calc2(sz[rt[c0]]);
            int rta,rtb;
            split(l,rt[c0],rta,rt[c1]),split(r+1,rt[c1],rt[c1],rtb);
            col[rt[c1]]=c1;
            t=lf(rt[c1]),pre[t]=t,update(t),t=ri(rt[c1]),nxt[t]=t,update(t);
            int tl=ri(rta),tr=lf(rtb);nxt[tl]=tr?tr:tl,pre[tr]=tl?tl:tr;update(tl),update(tr);
            rt[c0]=merge(rta,rtb);
            ans+=calc2(sz[rt[c0]])+calc2(sz[rt[c1]]);
        }
        put(ans);
    }
}