LibreOJ β Round _#2 题解(全解锁) | Bill Yang's Blog

LibreOJ β Round _#2 题解(全解锁)

盲目找题切,发现LibreOJ这场比赛的题目名字很有意思,就做了一下题。

先丢几个链接
比赛地址
官方题解
大佬题解

Problem A. 模拟只会猜题意

题目大意

给定一个长度为$n$的序列$A$。
定义$f(l,r)=\sum_{i=l}^{r}A_{i}f(l,r)$。
询问$m$次,每次询问一个数字$x$,请求出所有满足$r-l+1 \ge x$区间$[l,r]$中最大的$f(l,r)$。

题目分析

因为LibreOJ很快,所以可以直接$O(n^2+m)$暴力。
是不是很坑爹。。

可能错因

  • 没有memset成负无穷
  • 后缀取$\max$时不应从最后一个开始

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=10005;
int n,m,sum[maxn],f[maxn];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+Get_Int();
for(int len=1; len<=n; len++) {
f[len]=-INT_MAX;
for(int i=1; i+len-1<=n; i++) {
int j=i+len-1;
f[len]=max(f[len],sum[j]-sum[i-1]);
}
}
for(int i=n-1; i>=1; i--)f[i]=max(f[i],f[i+1]);
for(int i=1; i<=m; i++) {
int x=Get_Int();
printf("%d\n",f[x]);
}
return 0;
}

Problem B. 贪心只能过样例

题目大意

一共有$n$个数,第$i$个数$x_i$可以取$[a_i,b_i]$中任意值。
设$S=\sum x_i^2$​,求$S$种类数。

题目分析

和最多为$n^3$,因此可以设计出一个类似背包的Dp,转移时间复杂度为$O(n^5)$。
可以使用bitset进行优化。
时间复杂度$O(\frac{n^5}{64})$。

可能错因

  • bitset开成了$1000000$,应该开$1000001$。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
bitset<1000005> now,pre;
void add(int l,int r) {
pre=now;
now.reset();
for(int i=l,last=0; i<=r; last=i*i,i++) {
pre<<=(i*i-last);
now|=pre;
}
}
int n;
int main() {
now[0]=1;
n=Get_Int();
for(int i=1; i<=n; i++) {
int a=Get_Int(),b=Get_Int();
add(a,b);
}
printf("%d\n",now.count());
return 0;
}

Problem C. DP 一般看规律

题目大意

给定一个长度为$n$的序列$a$,一共有$m$个操作。
每次操作的内容为:给定$x,y$,序列中所有$x$会变成$y$。
同时我们有一份代码:

1
2
3
4
5
6
7
8
int ans = 2147483647;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j])
ans = std::min(ans, j - i);
}
}
std::cout << ans << std::endl;

请在每次修改后输出代码运行的结果。

题目分析

每次修改后答案肯定不会变大。
set或启发式合并splay/treap来合并信息,每次合并时统计可能产生贡献的差。
时间复杂度$O(n\log^2 n+m)/O(n\log n+m)$。

可能错因

  • 某些方法没有特判$x=y$。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
#define pii pair<int,int>
#define mp make_pair
mt19937 g(rand());
const int maxn=1000005;
int ans=INT_MAX/2;
struct Treap {
struct Tree {
int l,r,size;
int val;
Tree() {}
Tree(int _l,int _r,int s,int v):l(_l),r(_r),size(s),val(v) {}
} tree[maxn*3];
int size;
#define val(x) tree[x].val
#define size(x) tree[x].size
int newnode(int v) {
tree[++size]=Tree(0,0,1,v);
return size;
}
void push_up(int index) {
int l=tree[index].l,r=tree[index].r;
size(index)=size(l)+size(r)+1;
}
pii split(int index,int num) {
if(!index)return mp(0,0);
int l=tree[index].l,r=tree[index].r;
if(num<=size(l)) {
pii lt=split(l,num);
tree[index].l=lt.second;
push_up(index);
return mp(lt.first,index);
} else {
pii rt=split(r,num-size(l)-1);
tree[index].r=rt.first;
push_up(index);
return mp(index,rt.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
if(g()%(size(a)+size(b))<size(a)) {
tree[a].r=merge(tree[a].r,b);
push_up(a);
return a;
} else {
tree[b].l=merge(a,tree[b].l);
push_up(b);
return b;
}
}
int get_rank(int index,int v) {
if(!index)return 0;
if(v<val(index))return get_rank(tree[index].l,v);
else return size(tree[index].l)+1+get_rank(tree[index].r,v);
}
int insert(int index,int k,int v) {
pii tmp=split(index,k-1);
return merge(merge(tmp.first,newnode(v)),tmp.second);
}
int pre(int now,int num) {
int ans=-INT_MAX/2;
while(now) {
if(val(now)<num)ans=max(ans,val(now)),now=tree[now].r;
else now=tree[now].l;
}
return ans;
}
int suc(int now,int num) {
int ans=INT_MAX/2;
while(now) {
if(val(now)>num)ans=min(ans,val(now)),now=tree[now].l;
else now=tree[now].r;
}
return ans;
}
void dfs(int x,int &y) {
if(!x)return;
ans=min(ans,min(suc(y,tree[x].val)-tree[x].val,tree[x].val-pre(y,tree[x].val)));
y=insert(y,get_rank(y,tree[x].val)+1,tree[x].val);
dfs(tree[x].l,y);
dfs(tree[x].r,y);
}
} treap;
int n,m,a[maxn],X[maxn],Y[maxn],tmp[maxn*3],cnt=0,root[maxn*3];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)tmp[++cnt]=a[i]=Get_Int();
for(int i=1; i<=m; i++) {
tmp[++cnt]=X[i]=Get_Int();
tmp[++cnt]=Y[i]=Get_Int();
}
sort(tmp+1,tmp+cnt+1);
int tot=unique(tmp+1,tmp+cnt+1)-tmp-1;
for(int i=1; i<=n; i++)a[i]=lower_bound(tmp+1,tmp+tot+1,a[i])-tmp;
for(int i=1; i<=m; i++) {
X[i]=lower_bound(tmp+1,tmp+tot+1,X[i])-tmp;
Y[i]=lower_bound(tmp+1,tmp+tot+1,Y[i])-tmp;
}
for(int i=1; i<=n; i++) {
ans=min(ans,min(treap.suc(root[a[i]],i)-i,i-treap.pre(root[a[i]],i)));
root[a[i]]=treap.insert(root[a[i]],treap.get_rank(root[a[i]],a[i])+1,i);
}
for(int i=1; i<=m; i++) {
int x=X[i],y=Y[i];
if(x==y) {
printf("%d\n",ans);
continue;
}
bool bj=0;
if(treap.tree[root[x]].size>treap.tree[root[y]].size) {
swap(x,y);
bj=1;
}
treap.dfs(root[x],root[y]);
root[x]=0;
if(bj)root[x]=root[y],root[y]=0;
printf("%d\n",ans);
}
return 0;
}

Problem D. 计算几何瞎暴力

题目大意

有一个长度为$n$的数组$A$。下标从$1$开始标号。有$m$个操作需要处理,操作有如下四种:

  1. 在数组$A$的末尾添加一个数$x$。
  2. 输出$\sum_{i=l}^{r}A_i$。
  3. 将数组$A$中的每个数$A_i$都改为$A_i\oplus x$。($\oplus$表示异或操作)。
  4. 将数组$A$从小到大排序。

题目分析

第$4$个操作看上去很不可做。
先考虑前$3$个操作。

因为异或有结合律,因此可以维护一个懒标记$lazy$,表示到目前所有第$3$个异或操作$\oplus x$的$x$异或和。

每次插入数的时候都给这个数异或上$lazy$。
再维护一下每个二进制位出现个数的前缀和。

查询时,根据$lazy$每个二进制位$0/1$的情况即可知道是应该统计该位上$1$的个数还是$0$的个数。

现在来考虑第$4$个操作。
我们发现这个操作是全局sort,而不是区间sort
那么我们就可以玄学,我们只需要用数据结构维护前$k$小的数就可以代替排序的意义。

维护一个变量$pos$表示上一次排序的位置,以及$last$表示上一次排序时的$lazy$。
$pos$前归数据结构管,表示已经排好序了。而后面部分归前缀和管,表示尚未有序。

这个数据结构需要支持插入,查询前$k$小,以及打全局异或标记。
不难想到使用trie
trie的全局异或标记就是如果last某个二进制位为$1$,就交换两个儿子。(不需要真的交换,判断一下方向就可以了)
然后在trie上二分即可得到前$k$小的和。
最后还是有个根据lazy决定是统计$0$的个数还是$1$的个数的过程。

时间复杂度为$O(n\log v+m\log^2 v)$,空间复杂度为$O(n\log v)$。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005,K=31;
struct Tree {
int cnt,sum[K];
Tree *child[2];
Tree() {
cnt=0;
fill(sum,sum+K,0);
child[0]=child[1]=NULL;
}
};
LL last,lazy;
int pos;
struct Trie {
Tree *root=new Tree;
void insert(int val) {
Tree *now=root;
for(int i=K-1; i>=0; i--) {
bool ch=val>>i&1;
if(!now->child[ch])now->child[ch]=new Tree;
now=now->child[ch];
now->cnt++;
for(int j=0; j<K; j++)now->sum[j]+=val>>j&1;
}
}
LL query(int kth) {
LL ans=0;
Tree *now=root,*ls;
for(int i=K-1; kth&&i>=0; i--) {
ls=now->child[last>>i&1];
if(ls&&kth<ls->cnt)now=ls;
else {
now=now->child[!(last>>i&1)];
if(!ls)continue;
kth-=ls->cnt;
for(int j=0; j<K; j++)
if(lazy>>j&1)ans+=LL(ls->cnt-ls->sum[j])<<j;
else ans+=LL(ls->sum[j])<<j;
}
}
for(int i=0; i<K&&kth; i++)ans+=LL((lazy>>i&1)^(now->sum[i]>0))<<i;
return ans;
}
} trie;
LL sum[maxn][K];
LL Query(int x) {
LL ans=trie.query(min(x,pos));
if(x<=pos)return ans;
for(int i=0; i<K; i++)
if(lazy>>i&1)ans+=LL(x-pos-(sum[x][i]-sum[pos][i]))<<i;
else ans+=LL(sum[x][i]-sum[pos][i])<<i;
return ans;
}
int n,m,a[maxn];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
for(int j=0; j<K; j++)sum[i][j]=sum[i-1][j]+(a[i]>>j&1);
}
m=Get_Int();
for(int i=1; i<=m; i++) {
int opt=Get_Int();
if(opt==1) {
a[++n]=Get_Int()^lazy;
for(int j=0; j<K; j++)sum[n][j]=sum[n-1][j]+(a[n]>>j&1);
} else if(opt==2) {
int l=Get_Int(),r=Get_Int();
printf("%lld\n",Query(r)-Query(l-1));
} else if(opt==3)lazy^=Get_Int();
else {
last=lazy;
while(pos<n)trie.insert(a[++pos]);
}
}
return 0;
}

Problem E. 数论只会 GCD

题目大意

定义一个序列的权值为不同数字的个数。例如$[1,2,3,3]$的权值为$3$。
现在有$n$个序列,我们在每个序列里面选一个连续非空子串,拼接起来,求所有选法得到的序列的权值之和。
如果一个序列能通过多种方法被选择出来,那么计算多次。
本题带修改操作,格式请参考输入格式。
由于结果可能过大,请输出答案$\bmod 19260817$的结果。

题目分析

我们先考虑只有一个序列,不带任何修改如何求解。
考虑每个颜色对答案的贡献,即包含至少一个该颜色的序列个数。
小容斥一下,将 包含至少一个该颜色的序列数 转化为 所有序列数 - 不包含该颜色的序列数。
对于每个颜色$i$,假设其出现位置分别为$a_1,a_2,a_3,\ldots a_k$,则不包含该颜色的序列数为$\sum_{i=2}F(a_i-a_{i-1}-1)$,其中$F(x)=\frac{x(x+1)}2$。
故贡献为$F(len)-\sum_{i=2}F(a_i-a_{i-1}-1)$。

对于不同颜色,显然将贡献全部加起来即可。

现在考虑多个序列,不带任何修改如何求解。
不难发现对于容斥后面的部分:不包含该颜色的序列数 可以直接将每个颜色的贡献乘起来,再用多个序列$F(len)$之和去减乘积即可得到贡献。

现在考虑带修改如何求解。
发现修改只会使某种颜色的前驱后继产生变化,从而对贡献产生影响。
故用对每个颜色建立一棵线段树,维护所有序列该颜色贡献的积。
统计一下变化量即可得到的答案。
使用可持久化线段树防止炸空间。

时间复杂度$O((n+q)\log n)$,空间复杂度$O((n+q)\log n)$。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,mod=19260817;
int Start[maxn],End[maxn];
int Cal(int x) {
return (1ll*x*(x+1)>>1)%mod;
}
void check(int &x) {
if(x>=mod)x-=mod;
if(x<0)x+=mod;
}
void add(int &x,int v) {
x+=v;
check(x);
}
struct Segment_Tree {
struct Tree {
int ls,rs,val;
Tree(int l=0,int r=0,int v=0):ls(l),rs(r),val(v) {}
} tree[maxn*60];
int size;
#define lson tree[now].ls
#define rson tree[now].rs
#define mid ((left+right)>>1)
int build(int left,int right) {
int now=++size;
if(left==right) {
tree[now].val=Cal(End[left]-Start[left]+1);
return now;
}
tree[now]=Tree(build(left,mid),build(mid+1,right));
push_up(now);
return now;
}
void push_up(int now) {
tree[now].val=1ll*tree[lson].val*tree[rson].val%mod;
}
int modify(int pre,int left,int right,int pos,int val) {
int now=++size;
tree[now]=tree[pre];
if(left==right) {
add(tree[now].val,val);
return now;
}
if(pos<=mid)lson=modify(lson,left,mid,pos,val);
else rson=modify(rson,mid+1,right,pos,val);
push_up(now);
return now;
}
} st;
set<int> S[maxn<<1];
int n,m,ans=0,a[maxn],root[maxn<<1],tmp[maxn<<1],X[maxn],Y[maxn],V[maxn],cnt=0;
void insert(int x,int y,int val,int flag) {
auto it=flag?S[val].insert(Start[x]+y-1).first:S[val].find(Start[x]+y-1);
int pre=0,suc=End[x]-Start[x]+2;
if(it!=S[val].begin()) {
if(*(--it)>=Start[x])pre=*it-Start[x]+1;
++it;
}
++it;
if(it!=S[val].end()&&*it<=End[x])suc=*it-Start[x]+1;
--it;
int delta=(Cal(y-pre-1)+Cal(suc-y-1)-Cal(suc-pre-1))%mod;
check(delta);
if(!flag)delta=mod-delta,S[val].erase(it);
add(ans,st.tree[root[val]].val);
root[val]=st.modify(root[val],1,n,x,delta);
add(ans,-st.tree[root[val]].val);
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
Start[i]=End[i-1]+1;
End[i]=Start[i]+x-1;
}
for(int i=1; i<=End[n]; i++)tmp[++cnt]=a[i]=Get_Int();
for(int i=1; i<=m; i++) {
X[i]=Get_Int();
Y[i]=Get_Int();
tmp[++cnt]=V[i]=Get_Int();
}
sort(tmp+1,tmp+cnt+1);
int tot=unique(tmp+1,tmp+cnt+1)-tmp-1;
root[0]=st.build(1,n);
for(int i=1; i<=tot; i++)root[i]=root[0];
for(int i=1; i<=n; i++)
for(int j=Start[i]; j<=End[i]; j++) {
a[j]=lower_bound(tmp+1,tmp+tot+1,a[j])-tmp;
insert(i,j-Start[i]+1,a[j],1);
}
printf("%d\n",ans);
for(int i=1; i<=m; i++) {
int x=X[i],y=Y[i],v=lower_bound(tmp+1,tmp+tot+1,V[i])-tmp;
insert(x,y,a[Start[x]+y-1],0);
insert(x,y,a[Start[x]+y-1]=v,1);
printf("%d\n",ans);
}
return 0;
}

Problem F. 数学上来先打表

题目大意

给你一个图,每个点有点权,最开始没有边。
有一些操作:
添加一条$x$与$y$之间的双向边。
回到第$x$次操作后的状态。(注意这里的$x$可以是$0$,即回到初始状态)
查询$x$所在联通块能到的点中点权第$y$小的值,如果不存在,那么输出$-1$。

题目分析

解法一(标算)

考虑使用bitset来维护每个元素。
bitset怎么处理相同元素呢?离散化时离散成不同元素即可。
合并时直接合并bitset,操作的时间复杂度均为$O(\frac{n}{64})$。

好像没问题……?等等,空间为什么是 50 MB 啊,我的做法要 1280 MB 啊,这还让我怎么活?

因为没有强制在线,故可以离线建立操作树,在操作树上进行DFS。

DFS递归时需要合并$A,B$两个bitset,为了回溯的时候撤销掉合并,需要保存其中一个bitset
利用启发式合并,若保存两者中较小的一个bitset,用一些特技来优化空间,即可使得空间复杂度秒变$O(n\log n)$。

特技:
bitset使用vector存储,若某连续$64$位均为$0$,那么没有记录它的必要,就不要它,同时记录一下每个结点对应第几位,这就是所谓的特技。

至于空间复杂度证明:
每次保存较小的bitset,每次它至少变大一倍,这样每个元素最多被记录$\log n$次,空间复杂度即为$O(n\log n)$。

总时间复杂度$O(\frac{nm}{64})$,空间复杂度$O(n\log n+m)$。

代码:
丢一份可读的代码$\rightarrow$传送门

解法二(来自民间大佬)

很好写的解法二,你一定会爱上它!

发现可以通过值域分块优化合并的时间。

首先还是同样的相同变不同的离散化,然后预处理块,建操作树。

同时再维护一个带撤销并查集,来检查每个数是否在集合中。
同时再维护每个集合中每个值域块中的数的个数。
显然这个东西是可以撤销掉的。

假设每个块的大小为$B(n)$,因此在操作树上DFS的时间复杂度为$O(\frac{nm}{B(n)})$。

而询问可以在$O(\frac{n}{B(n)})$的时间内定位到所在的值域块,然后结合并查集在$O(B(n)\log n)$的时间内完成询问。

故总时间复杂度为$O(\frac{nm}{B(n)}+m_3B(n)\log n)$,其中$m_3$是询问的个数。
空间复杂度为$O(\frac{n^2}{B(n)})$。

内存限制为 50 MB,计算发现在$B(n)\ge763$时数组能开下。
然而还有其他数组占用内存,计算发现$B(n)\ge 870$时不会炸空间。
然而不知道为什么LOJ依然炸空间,测试发现$B(n)\ge 1050$时不会炸空间。
然而实际测试$B(n)=1100$时时间复杂度表现最好。

关于时间复杂度,给几个参数。
当$m_3=m$时:

二元组$(x,y)$表示$B(n)=x$时,时间复杂度约为$y$。

当$B(n)=1100$时:

二元组$(x,y)$表示$m_3=x$时,时间复杂度约为$y$。

代码:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,size=1100,maxb=maxn/size+5;
int n,m,a[maxn],id[maxn],Belong[maxn],father[maxn],sum[maxn][maxb],opt[maxn],x[maxn],y[maxn],BCC=0,ans[maxn];
bool vst[maxb];
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int Get_Father(int x) {
if(father[x]<0)return x;
return Get_Father(father[x]);
}
int query(int Now,int kth) {
if(-father[Now]<kth)return 0;
int bcc=1;
while(kth>sum[Now][bcc])kth-=sum[Now][bcc++];
for(int i=1; i<=size; i++) {
kth-=Get_Father(id[(bcc-1)*size+i])==Now;
if(!kth)return id[(bcc-1)*size+i];
}
}
void Dfs(int Now) {
if(opt[Now]==1) {
int fx=Get_Father(x[Now]),fy=Get_Father(y[Now]);
if(father[fx]<father[fy])swap(fx,fy);
int tmp=father[fx];
if(fx!=fy) {
father[fy]+=father[fx];
father[fx]=fy;
for(int i=1; i<=BCC; i++)sum[fy][i]+=sum[fx][i];
}
for(int Next:edges[Now])Dfs(Next);
if(fx!=fy) {
father[fy]-=tmp;
father[fx]=tmp;
for(int i=1; i<=BCC; i++)sum[fy][i]-=sum[fx][i];
}
} else {
if(opt[Now]==3)ans[Now]=query(Get_Father(x[Now]),y[Now]);
for(int Next:edges[Now])Dfs(Next);
}
}
bool cmp(int x,int y) {
return a[x]<a[y];
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),id[i]=i;
sort(id+1,id+n+1,cmp);
for(int i=1; i<=n; i++) {
father[i]=-1;
Belong[i]=(i-1)/size+1;
if(!vst[Belong[i]])vst[Belong[i]]=1,BCC++;
sum[id[i]][Belong[i]]=1;
}
for(int i=1; i<=m; i++) {
opt[i]=Get_Int();
x[i]=Get_Int();
if(opt[i]==2)AddEdge(x[i],i);
else {
y[i]=Get_Int();
AddEdge(i-1,i);
}
}
Dfs(0);
a[0]=-1;
for(int i=1; i<=m; i++)if(opt[i]==3)printf("%d\n",a[ans[i]]);
return 0;
}

0%