题解 P4119 [Ynoi2018] 未来日记
FutaRimeWoawaSete · · 题解
upd:2021/5/4 被 mcyl35 叉掉了，原因是值域分块值域开小了，在这里感谢他的 hack 。
应该说只要做过第二分块，这道题基本上就没有什么有趣的地方了，我愿称第二分块为最初分块前体。
我们首先考虑一下这个修改操作，不难发现他的本质就是映射，感觉可以维护的方式有点多，先咕着。
查询是区间 rank ，我第一想法就是由乃打扑克，每个块排序然后 lowerbound 查询，但是这样的话就不好修改了，我们得考虑一种能兼容修改的查询方法。
我们不难发现对于 rank ，我们有一个很普遍的值域分块方法，如果此题中我们对每个块进行值域分块，维护下来块的前缀值域情况，那么这道题就很简单了。
我们又发现，修改的映射每一次只会修改两类数，这个显然可以数组存储做到
接着我们思考一个问题：我们的修改在值域分块的维护上面没有问题，但是对于散块修改呢？但是怎么维护整块修改完后每个数变成了什么？
这时候就得并查集了，对于整块我们还要用并查集维护它们的映射关系。
记录 fr[x][y] 表示权值 y 在块 x 内第一个出现的位置，相当于是一个捆绑标记，col[x] 表示序列里面第 x 个数的颜色，令当前块为 t 。
我们判断 a 改为 b 的映射，如果 a 不存在，那么我们不要这个修改。如果 b 不存在，我们就直接让 b 的 fr[t][b] = fr[t][a} 即可，并且把 col[fr[t][b]] 修改为 b ，否则都出现过的话直接并查集，把 fr[t][a]父亲置为 fr[t][b] 就好了。
接着我们对于整块直接并查集进去，对于散块，看着不爽直接重构就好了，时间复杂度
不过此题轻度卡常，建议多玄学剪枝一些东西，建议先做第二分块。
不过要我评，做这道题之前就算我没做过第二分块，估计也只能给 6 的评分。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int Len = 1e5 + 5 , SIZE = 330;
int n,m,fr[SIZE][Len],col[Len],fa[Len],cnt[SIZE][Len],sum[SIZE][SIZE],vt,t,L[SIZE],R[SIZE],pos[Len],VL[SIZE],VR[SIZE],Vpos[Len],a[Len];
void makeSet(int x){for(int i = 1 ; i <= x ; i ++) fa[i] = i;}
int findSet(int x){return fa[x] == x ? fa[x] : fa[x] = findSet(fa[x]);}
inline void merge(int x,int X,int Y)
{
if(!fr[x][X]) return;
else if(!fr[x][Y]){fr[x][Y] = fr[x][X] , col[fr[x][Y]] = Y;}
else fa[fr[x][X]] = fr[x][Y];
fr[x][X] = 0;
}
inline void build(int x,int l,int r,int X,int Y)
{
for(int i = L[x] ; i <= R[x] ; i ++){a[i] = col[findSet(i)] ; fr[x][a[i]] = 0;}
for(int i = l ; i <= r ; i ++) if(a[i] == X) a[i] = Y;
for(int i = L[x] ; i <= R[x] ; i ++)
{
if(!fr[x][a[i]]){fr[x][a[i]] = i;col[fr[x][a[i]]] = a[i];}
fa[i] = fr[x][a[i]];
}
}
inline void upd(int l,int r,int X,int Y)
{
if(X == Y) return;
int LL = pos[l] , RR = pos[r];
int numb = 0 , Tmp = 0;
if(LL == RR)
{
for(int i = l ; i <= r ; i ++) if(col[findSet(i)] == X) numb ++;
if(!numb) return;
for(int i = LL ; i <= t ; i ++) sum[i][Vpos[X]] -= numb , sum[i][Vpos[Y]] += numb , cnt[i][X] -= numb , cnt[i][Y] += numb;
build(LL , l , r , X , Y);
return;
}
for(int i = l ; i <= R[LL] ; i ++) if(col[findSet(i)] == X) numb ++;
if(numb) build(LL , l , R[LL] , X , Y);
for(int i = LL ; i <= RR - 1 ; i ++) numb += Tmp , sum[i][Vpos[X]] -= numb , sum[i][Vpos[Y]] += numb , Tmp = cnt[i + 1][X] - cnt[i][X] , cnt[i][X] -= numb , cnt[i][Y] += numb;
int v = 0;for(int i = L[RR] ; i <= r ; i ++) if(col[findSet(i)] == X) numb ++ , v ++;
for(int i = RR ; i <= t ; i ++) sum[i][Vpos[X]] -= numb , sum[i][Vpos[Y]] += numb , cnt[i][X] -= numb , cnt[i][Y] += numb;
for(int i = LL + 1 ; i <= RR - 1 ; i ++) merge(i , X , Y);
if(v) build(RR , L[RR] , r , X , Y);
return;
}
int UsedSum[Len],UsedBlock[SIZE];
inline int qry(int l,int r,int k)
{
int LL = pos[l] , RR = pos[r];
if(k > r - l + 1) return -1;
if(LL == RR)
{
for(int i = l ; i <= r ; i ++) UsedBlock[Vpos[col[findSet(i)]]] ++ , UsedSum[col[findSet(i)]] ++;
for(int j = 1 ; j <= vt ; j ++)
{
if(k > UsedBlock[j]) k -= UsedBlock[j];
else
{
for(int p = VL[j] ; p <= VR[j] ; p ++)
{
if(k > UsedSum[p]) k -= UsedSum[p];
else
{
for(int i = l ; i <= r ; i ++) UsedBlock[Vpos[col[findSet(i)]]] -- , UsedSum[col[findSet(i)]] --;
return p;
}
}
}
}
}
for(int i = l ; i <= R[LL] ; i ++) UsedBlock[Vpos[col[findSet(i)]]] ++ , UsedSum[col[findSet(i)]] ++;
for(int i = L[RR] ; i <= r ; i ++) UsedBlock[Vpos[col[findSet(i)]]] ++ , UsedSum[col[findSet(i)]] ++;
for(int j = 1 ; j <= vt ; j ++)
{
if(k > (sum[RR - 1][j] - sum[LL][j] + UsedBlock[j])) k -= sum[RR - 1][j] - sum[LL][j] + UsedBlock[j];
else
{
for(int p = VL[j] ; p <= VR[j] ; p ++)
{
if(k > (cnt[RR - 1][p] - cnt[LL][p] + UsedSum[p])) k -= cnt[RR - 1][p] - cnt[LL][p] + UsedSum[p];
else
{
for(int i = l ; i <= R[LL] ; i ++) UsedBlock[Vpos[col[findSet(i)]]] -- , UsedSum[col[findSet(i)]] --;
for(int i = L[RR] ; i <= r ; i ++) UsedBlock[Vpos[col[findSet(i)]]] -- , UsedSum[col[findSet(i)]] --;
return p;
}
}
}
}
}
struct Node
{
int opt,l,r,x,y;
}lxlNB[Len];
signed main()
{
int maxn = 100000;
scanf("%d %d",&n,&m);
makeSet(n);
t = sqrt(n);
for(int i = 1 ; i <= n ; i ++){scanf("%d",&a[i]) ; maxn = max(maxn , a[i]);}
for(int i = 1 ; i <= m ; i ++)
{
scanf("%d %d %d %d",&lxlNB[i].opt,&lxlNB[i].l,&lxlNB[i].r,&lxlNB[i].x);
if(lxlNB[i].opt == 1)
{
scanf("%d",&lxlNB[i].y);
maxn = max(maxn , lxlNB[i].x) , maxn = max(maxn , lxlNB[i].y);
}
}
vt = sqrt(maxn);
for(int i = 1 ; i <= t ; i ++) L[i] = (i - 1) * t + 1 , R[i] = i * t;
R[t] = n;
for(int i = 1 ; i <= vt ; i ++) VL[i] = (i - 1) * vt + 1 , VR[i] = i * vt;
VR[vt] = maxn;
for(int i = 1 ; i <= t ; i ++)
for(int j = L[i] ; j <= R[i] ; j ++) pos[j] = i;
for(int i = 1 ; i <= vt ; i ++)
for(int j = VL[i] ; j <= VR[i] ; j ++) Vpos[j] = i;
for(int i = 1 ; i <= t ; i ++)
{
for(int j = L[i] ; j <= R[i] ; j ++)
{
if(!fr[i][a[j]]){fr[i][a[j]] = j ; col[fr[i][a[j]]] = a[j];}
fa[j] = fr[i][a[j]];
cnt[i][a[j]] ++ , sum[i][Vpos[a[j]]] ++;
}
for(int j = 1 ; j <= vt ; j ++) sum[i][j] += sum[i - 1][j];
for(int j = 1 ; j <= maxn ; j ++) cnt[i][j] += cnt[i - 1][j];
}
for(int i = 1 ; i <= m ; i ++)
{
if(lxlNB[i].opt == 1) upd(lxlNB[i].l , lxlNB[i].r , lxlNB[i].x , lxlNB[i].y);
else printf("%d\n",qry(lxlNB[i].l , lxlNB[i].r , lxlNB[i].x));
}
return 0;
}