LuoguP4119 [Ynoi2018] 未来日记

(Updated: )
oi
,

Description

题目链接：P4119

一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

  1. 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。
  2. 查询区间 $[l,r]$ 内第 $k$ 小值。

$1\leq n,m,a_i\leq 10^5$

Solution

stO 陈指导 Orz，陈指导码了一个下午就做完了，蒟蒻我竟然写了3天。

首先要对序列分块，对于整块，考虑直接把一种数字直接改成另一种数字，然后可以考虑使用并查集。对于散块，我们可以直接暴力枚举修改，暴力重构并查集即可。

这时候需要分类讨论：

  1. 该块中没有出现 $x$，那么直接跳过即可。
  2. 该块出现了 $x$，没有出现 $y$，那么就直接用并查集映射即可。
  3. 该块出现了 $x$，也出现了 $y$，直接暴力重构。

然后我们会发现一个细节：如果我们并查集记录的是每个块的颜色指向的真实颜色，那么会出现一些问题：如果将块内所有 $1$ 改为 $2$，再将所有 $3$ 改为 $1$ 这种情况就非常难处理。

所以我们可以选择记录块内每个位置在块内与其数字相同的编号最小值，这样就可以完美规避上面的问题了。

然后我们发现询问还是有点苦难，这时候应该可以想到查找区间第 $k$ 小的常见套路：值域分块，记录每个序列块的前缀和。具体实现方法就是”带插入区间第 $k$ 小”方法。

这时候敲代码的时候又会发现一个问题：每次修改要更新的是前缀和，复杂度会升到 $O(NM)$。考虑修改的过程中开个桶记录下第 $k$ 个块修改的权值和，修改全部完成后再扫一遍所有的块，更新前缀和即可。

可以发现暴力重构块的次数是有限的，每次合并时块内权值种类会减少 $1$，而权值种类总共不会超过$n+m$，可以保证复杂度正确性 $O((N+M)\sqrt{N})$。

然后不知道为什么被lxl卡得很慢

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,S=452,M=N/S+5,SS=385,MM=N/SS+5;
int n,m,b[M][S+5],sz[M],L[M],cnt[M][N],cntS[M][MM],F[M][S+5],H[M][N],tot,stk[N],top,tcnt[N],tcntS[MM],T[M];
I int Find(CI k,CI x,CI t=0){return x==F[k][x]?x:F[k][x]=Find(k,F[k][x],t);}//并查集
I void B(CI k,CI x=-1,CI y=-1,CI l=0,CI r=0,CI v=0){//暴力重构块
    RI i,t;for(i=0;i<sz[k];i++) t=b[k][Find(k,i,1)],b[k][i]=t,H[k][t]=-1;//并查集重置
    if(~x) for(i=(v?l:0);i<=(v?r:sz[k]-1);i++) if(b[k][i]==x) b[k][i]=y,T[k]++;//暴力修改
    for(i=0;i<sz[k];i++) F[k][i]=((~H[k][b[k][i]])?H[k][b[k][i]]:H[k][b[k][i]]=i);//重构并查集
}
I void P(CI k,CI l,CI r,CI x,CI y){RI i;B(k,x,y,l,r,1);}//边角暴力重构
I void R(CI x,CI y){RI i,t=0;for(i=1;i<=tot;i++) t+=T[i],cnt[i][x]-=t,cntS[i][x/SS]-=t,cnt[i][y]+=t,cntS[i][y/SS]+=t,T[i]=0;}//开临时数组记录，最后直接扫一遍累加更新前缀和
I void U(RI l,RI r,CI x,CI y){
    if(x==y) return ;RI i,bL=(l-1)/S+1,bR=(r-1)/S+1;if(l-=L[bL],r-=L[bR],bL==bR) return P(bL,l,r,x,y),R(x,y);
    for(P(bL,l,sz[bL]-1,x,y),P(bR,0,r,x,y),i=bL+1;i<=bR-1;i++) if(cnt[i][x]^cnt[i-1][x]&&cnt[i][y]==cnt[i-1][y]) T[i]+=cnt[i][x]-cnt[i-1][x],F[i][H[i][x]]=H[i][y]=H[i][x],b[i][H[i][x]]=y,H[i][x]=-1;//如果没有y，直接映射
    else if(cnt[i][x]^cnt[i-1][x]&&cnt[i][y]^cnt[i-1][y]) B(i,x,y);return R(x,y);//如果有y，直接暴力重构
}
I void G(CI k,CI l,CI r){RI i;for(i=l;i<=r;i++) stk[++top]=b[k][Find(k,i)],tcnt[stk[top]]++,tcntS[stk[top]/SS]++;}//散块暴力统计
I void C(){W(top) tcnt[stk[top]]--,tcntS[stk[top]/SS]--,top--;}//记得清空
I int Q(RI l,RI r,RI k){//值域分块，基本套路
    RI i,j,bL=(l-1)/S+1,bR=(r-1)/S+1;if(l-=L[bL],r-=L[bR],bL==bR) for(G(bL,l,r),i=0;;i++) if(tcntS[i]<k) k-=tcntS[i];
    else for(j=SS*i;;j++) if(k>tcnt[j]) k-=tcnt[j];else return C(),j;
    else for(G(bL,l,sz[bL]-1),G(bR,0,r),i=0;;i++) if(k>tcntS[i]+cntS[bR-1][i]-cntS[bL][i]) k-=tcntS[i]+cntS[bR-1][i]-cntS[bL][i];
    else for(j=SS*i;;j++) if(k>tcnt[j]+cnt[bR-1][j]-cnt[bL][j]) k-=tcnt[j]+cnt[bR-1][j]-cnt[bL][j];else return C(),j;
}
int main(){
    RI i,j,k,opt,l,r,x,y;for(read(n,m),i=1;i<=n;i++) read(x),!((i-1)%S)&&(L[++tot]=i),b[tot][sz[tot]++]=x;
    memset(F,-1,sizeof(F));memset(H,-1,sizeof(H));for(i=1;i<=tot;i++) for(j=0;j<sz[i];j++) for(F[i][j]=((~H[i][b[i][j]])?H[i][b[i][j]]:H[i][b[i][j]]=j),k=i;k<=tot;k++) cnt[k][b[i][j]]++,cntS[k][b[i][j]/SS]++;
    W(m--) if(read(opt,l,r,x),opt==1) read(y),U(l,r,x,y);else writeln(Q(l,r,x));return 0;
}