P4119 题解

· · 题解

毒瘤的第一分块，反正我调了整整一周（是我太逊了）。

我的黑历史

这题的操作非常明显：并查集或值域分块（至于为什么不是权值线段树：看看出题人的名字）。

先看第一个操作：看上去只需要一个序列分块套值域分块，但是你发现不能只搞值域，原数组也要修改，但已经有 \sqrt n 个块了，所以我们得 O(1) 修改，于是就很自然的想到并查集（因为我是做完第二分块再来做这题的），散块拆散重构，整块修改并查集和值域分块。

再看第二个操作：区间 kth，看起来像主席树虽然我不会。但是我们既然选择了分块就要坚持到底。显然是值域上的 O(\sqrt n) 的处理，散块可以直接提前统计（也要个简单的值域分块），整块的我们要 O(1) 处理出一个值域块内的数的数量，好像没有黑科技可以做到 O(\sqrt n) 以内的预处理，也可能是我孤陋寡闻。，所以这里需要对整块的值域做一个前缀和。

因为散块的询问是直接暴力统计的，所以块内不用前缀和，这样的背景下修改也只修改整块的值域，也就是 O(\sqrt n) 的复杂度。

既然是大分块，那少不了卡常。

Code

#include <bits/stdc++.h>
using namespace std;
void qr(int &x){
    int f=x=0;
    char c=getchar();
    while(!isdigit(c)) f|=(c=='-'),c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x=f?~(x-1):x;
}
const int N=100005,Sn=205;
int rt[Sn][N],fa[N],a[N],cnt[N],ccnt[Sn],n,m,s,bls,L[Sn],R[Sn],Ls[Sn],Rs[Sn],blss,ss,idx[N],idxx[N],Maxa,numc[Sn][N],nums[Sn][Sn],opt,l,r,x,y,temp;
inline void merge(int p,int x,int y){
    if(x==y) return ;
    if(rt[p][x]==0) return;
    if(rt[p][y]) fa[rt[p][x]]=rt[p][y];
    else a[rt[p][x]]=y,rt[p][y]=rt[p][x];
    rt[p][x]=0;
}
int get(int x){
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
inline void update(int bl,int l,int r,int x,int y){
    rt[bl][x]=rt[bl][y]=temp=0;
    for(int i=L[bl];i<=R[bl];i++) {
        a[i]=a[get(i)];
    }
    for(int i=l;i<=r;i++){
        if(a[i]==x) a[i]=y,++temp;
    }
    for(int i=L[bl];i<=R[bl];i++){
        if(!rt[bl][a[i]]) rt[bl][a[i]]=i;
        fa[i]=rt[bl][a[i]];
    }
    for(int i=bl;i<=bls;i++) numc[i][x]-=temp,numc[i][y]+=temp,nums[i][idxx[x]]-=temp,nums[i][idxx[y]]+=temp;
    return ;
}
int main() {
    qr(n),qr(m);
    s=600,bls=(n+s-1)/s;
    for(int i=1;i<=bls;i++){
        L[i]=R[i-1]+1,R[i]=min(s*i,n);
        for(int j=L[i];j<=R[i];j++) idx[j]=i;
    } 
    Maxa=1e5;
    for(int i=1;i<=n;i++){
        qr(a[i]);
    }
    ss=600,blss=(1e5+ss-1)/ss;
    for(int i=1;i<=blss;i++){
        Ls[i]=Rs[i-1]+1,Rs[i]=min(ss*i,100000);
        for(int j=Ls[i];j<=Rs[i];j++) idxx[j]=i;
    } 
    for(int i=1;i<=bls;i++){
        for(int j=L[i];j<=R[i];j++){
            if(rt[i][a[j]]==0) rt[i][a[j]]=j;
            fa[j]=rt[i][a[j]];
            for(int k=i;k<=bls;k++) ++numc[k][a[j]],++nums[k][idxx[a[j]]];
        }
    }
    for(int zqw=1;zqw<=m;zqw++){
        qr(opt);
        if(opt==1){
            qr(l),qr(r),qr(x),qr(y);
            int lb=idx[l],rb=idx[r];
            if(lb==rb){
                update(lb,l,r,x,y);
                continue;
            }
            ++lb,--rb;
            temp=numc[rb][x]-numc[lb-1][x];
            for(int i=lb;i<=rb;i++) {
                merge(i,x,y);
                int tmp=numc[i][x]-numc[lb-1][x];
                nums[i][idxx[y]]+=tmp;
                nums[i][idxx[x]]-=tmp;
                numc[i][y]+=tmp;
                numc[i][x]-=tmp;
            }
            for(int i=rb+1;i<=bls;i++) numc[i][x]-=temp,nums[i][idxx[x]]-=temp,numc[i][y]+=temp,nums[i][idxx[y]]+=temp;
            ++rb,--lb;
            update(lb,l,R[lb],x,y);
            update(rb,L[rb],r,x,y);
        }else{
            qr(l),qr(r),qr(x);
            int lb=idx[l],rb=idx[r];
            if(lb==rb){
                for(int i=l;i<=r;i++) a[i]=a[get(i)],cnt[a[i]]++,ccnt[idxx[a[i]]]++;
                for(int i=1;i<=blss;i++) {
                    if(x>ccnt[i]) x-=ccnt[i]; 
                    else {
                        for(int j=Ls[i];j<=Rs[i];j++){
                            if(x>cnt[j]) x-=cnt[j];
                            else {
                                printf("%d\n",j);
                                break;
                            }
                        }
                        break;
                    }
                }
                for(int i=l;i<=r;i++) cnt[a[i]]=ccnt[idxx[a[i]]]=0;
                continue;
            }
            ++lb,--rb;
            for(int i=l;i<L[lb];i++) a[i]=a[get(i)],++cnt[a[i]],++ccnt[idxx[a[i]]];
            for(int i=R[rb]+1;i<=r;i++) a[i]=a[get(i)],++cnt[a[i]],++ccnt[idxx[a[i]]];
            for(int i=1;i<=blss;i++) {
                if(x>nums[rb][i]-nums[lb-1][i]+ccnt[i]) x-=nums[rb][i]-nums[lb-1][i]+ccnt[i];
                else {
                    for(int j=Ls[i];j<=Rs[i];j++){
                        if(x>numc[rb][j]-numc[lb-1][j]+cnt[j]) x-=numc[rb][j]-numc[lb-1][j]+cnt[j];
                        else {
                            printf("%d\n",j);
                            break;
                        }
                    }
                    break;
                }
            }
            for(int i=l;i<L[lb];i++) cnt[a[i]]=ccnt[idxx[a[i]]]=0;
            for(int i=R[rb]+1;i<=r;i++) cnt[a[i]]=ccnt[idxx[a[i]]]=0;
        }
    }
    return 0;
}