题面传送门
按秩合并并查集写错复杂度假掉以为自己被卡常卡了好久。
首先这种撤销题看上去就是把操作树建立出来然后dfs变成加入与撤销。
然后我们考虑对值域分块,这样看上去求\(k\)小值会可做一些。
首先我们需要确定每个询问在哪个块,这并不困难。我们考虑在dfs时用并查集维护,并查集的根节点维护每个值域块在这个联通块中有多少个。然后询问时逐块确定就可以得知答案在哪个块中。
然后我们考虑确定具体是哪个数。一种simple的想法是枚举每个数,看看是不是在同一个联通块中,但是很遗憾复杂度是有问题的因为可能一种值有很多个。正确的姿势是将同样的值离散到不同的值,这样答案不会变,但是每个值只有一个数,就可以用并查集逐个查询了。
块长取\(\sqrt{\frac{n}{\log n}}\)最优,时空复杂度都是\(O(n\sqrt {n\log n})\),但是实际上开不下这么大的数组,可以看到这道题刻意卡空间了。因此我们将块个数调小,实现上\(B=45\)能卡进空间和时间限制。
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 | #include< bits /stdc++.h> #define I inline #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define abs(x) ((x)>0?(x):-(x)) #define ll long long #define db double #define lb long db #define N (100000+5) #define M ((N<< 2 )+5) #define K (2500+5) #define mod 998244353 #define Mod (mod-1) #define eps (1e-9) #define ull unsigned ll #define it iterator #define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x)) #define Mc(x,y) memcpy(x,y,sizeof(x)) #define d(x,y) ((k+1)*(x)+(y)) #define R(n) (1ll*rand()*rand()%(n)+1) #define Pc(x) putchar(x) #define LB lower_bound #define UB upper_bound #define PB push_back using namespace std; struct yyy{int to,z;};struct ljb{int head,h[N];yyy f[N];I void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;}}s; int n,m,k,x,y,Op[N],X[N],Y[N],A[N],B[N],fa[N],siz[N],st[N],Fr[K],En[K],H,Ans[N];short F[N][46]; I int GF(int x){while(fa[x]^x) x = fa [x];return x;;}I bool cmp(int x,int y){return A[x]<A[y];} I void Merge(int x,int y){ x = GF (x); y = GF (y);if(x==y) return;siz[x]<siz[y]&&(swap(x,y),0);fa[y]=x;for(int i = 0 ;i<=n/k;i++) F[x][i]+=F[y][i];st[++H]=y;siz[x]+=siz[y];} I void POP(){int x = st [H--];siz[fa[x]] - = siz [x];for(int i = 0 ;i<=n/k;i++) F[fa[x]][i] - = F [x][i];fa[x]=x;} I void Make(int x){ int La = H ;Op[x]==1&&(Merge(X[x],Y[x]),0);X[x]=GF(X[x]);if(Op[x]==3){for(int i = 0 ;i<=n/k;i++){if(Y[x]>F[X[x]][i]) {Y[x]-=F[X[x]][i];continue;}for(int j=Fr[i];j<=En[i];j++) {Y[x]-=(GF(B[j])==X[x]);if(!Y[x]) {Ans[x]=j;break;}}break;}} yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],Make(tmp.to);La^H&&(POP(),0); } int main(){ freopen("1.in","r",stdin); int i;scanf("%d%d",&n,&m);k=max(n/45,1);for(i=1;i<=n;i++) scanf("%d",&A[i]),fa[i]=B[i]=i,siz[i]=1;sort(B+1,B+n+1,cmp);for(i=1;i<=n;i++) F[B[i]][i/k]=1; for(i=1;i<=m;i++) scanf("%d%d",&Op[i],&X[i]),Op[i]^2?(scanf("%d",&Y[i]),s.add(i-1,i)):(s.add(X[i],i)),Ans[i]=-1; for(i=0;i<=n/k;i++) Fr[i]=max(1,i*k),En[i]=min(i*k+k-1,n);Make(0);for(i=1;i<=m;i++) Op[i]==3&&(printf("%d\n",~Ans[i]?A[B[Ans[i]]]:-1)); } |