RT,不知道哪里错了,#7,8,15,16,17WA了。
https://www.luogu.com.cn/record/176828340
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
register int x = 0, f = 1;
register char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')f = -1;
c = getchar();
}
while(c <= '9' && c >= '0')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(int x)
{
if(!x)return;
write(x / 10);
putchar(x % 10 + '0');
return;
}
struct query
{
int op, x, y;
}Q[102000];
struct stk
{
int x, y;
}st[102100];
int fa[102100], siz[102000], tf[102100];
int top, cnt, ans[102100], len, n, m, a[102100], b[102100], v[102100];
int tot[120100], L, R;
vector <int> son[102100];
bool cmp(int x, int y){return a[x] < a[y];}
int getfa(int x)
{
while(fa[x] != x)x = fa[x];
return x;
}
void merge(int x, int y)
{
if((x = getfa(x)) == (y = getfa(y)))
{
st[++top].x = st[top].y = 0;
return;
}
if(siz[x] < siz[y])
{
swap(x, y);
}
siz[x] += siz[y];
fa[y] = x;
st[++top].x = x, st[top].y = y;
tot[x] += tot[y];
return;
}
void cut()
{
stk x = st[top--];
if(x.x)
{
siz[x.x] -= siz[x.y];
tot[x.x] -= tot[x.y];
fa[x.y] = x.y;
}
return;
}
void query(int x)
{
if(ans[x] != -1)return;
int a = getfa(Q[x].x);
if(tot[a] < Q[x].y)
{
Q[x].y -= tot[a];
return;
}
for(int i = L;i <= R;i++)
{
if(a == getfa(b[i]))
{
Q[x].y--;
if(Q[x].y == 0)
{
ans[x] = i;
return;
}
}
}
return;
}
void dfs(int x)
{
if(Q[x].op == 1)
{
merge(Q[x].x, Q[x].y);
for(int i = 0;i < son[x].size();i++)
{
dfs(son[x][i]);
}
cut();
}
if(Q[x].op == 2)
{
for(int i = 0;i < son[x].size();i++)
{
dfs(son[x][i]);
}
}
if(Q[x].op == 3)
{
query(x);
for(int i = 0;i < son[x].size();i++)
{
dfs(son[x][i]);
}
}
return;
}
signed main()
{
n = read(), m = read();
len = 1600;
top = 5;
for(int i = 1;i <= n;i++)
{
fa[i] = i;
siz[i] = 1;
a[i] = read();
b[i] = i;
}
sort(b + 1, b + n + 1, cmp);
for(int i = 1;i <= n;i++)
{
v[i] = a[b[i]];
}
int k = 0;
for(int i = 1;i <= n;i++)
{
a[b[i]] = i;
}
for(int i = 1;i <= m;i++)
{
Q[i].op = read(), Q[i].x = read();
ans[i] = -1;
if(Q[i].op & 1)Q[i].y = read(), tf[i] = i - 1;
else tf[i] = Q[i].x;
son[tf[i]].push_back(i);
}
Q[0].op = 2;
for(cnt = 1;cnt <= n / len + 1;cnt++)
{
L = (cnt - 1) * len + 1, R = min(n, cnt * len), top = 5;
for(int i = 0;i <= n;i++)
{
tot[i] = 0;
fa[i] = i;
siz[i] = 1;
if(a[i] >= L && a[i] <= R)tot[i] = 1;
}
dfs(0);
}
for(int i = 1;i <= n;i++)
{
if(Q[i].op == 3)
{
if(ans[i] <= m && ans[i] >= 1)cout << v[ans[i]] << "\n";
else cout << "-1\n";
}
}
return 0;
}