[THOI 2015]


[Prob 1] 异或运算

[Describtion]

给定长度为$n$的数列$ X = \lbrace x_1,x_2,…,x_n\rbrace $和长度为$m$的数列$Y=\lbrace y_1,y_2,…,y_m\rbrace $,令矩阵$A$中第$i$行第$j$列的值$A_{ij}=x_i\bigoplus y_j$,每次询问给定矩形区域$i\in[u,d],j\in[l,r]$,找出第$k$大的$A_{ij}$。

[Input]

第一行包含两个正整数$n,m$,分别表示两个数列的长度
第二行包含$n$个非负整数$x_i$
第三行包含$m$个非负整数$y_j$
第四行包含一个正整数$p$,表示询问次数
随后$p$行,每行均包含$5$个正整数,用来描述一次询问,每行包含五个正整数$u,d,l,r,k$,含义如题意所述。

[Output]

共$p$行,每行包含一个非负整数,表示此次询问的答案。

[Sample Input]

1
2
3
4
5
6
7
3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4

[Sample Output]

1
2
3
6
5
1

[Hint]

对于$100\%$的数据,$0<=X_i,Y_j<2^{31}$,
$1\leq u\leq d\leq n\leq 1000$,
$1\leq l\leq r\leq m\leq 300000$,
$1\leq k\leq (d-u+1)*(r-l+1)$,
$1\leq p\leq 500$

[Idea]

如果是只有一行的话,我们用可持久化Trie可以轻松解决
如果有多行的话,我们可以参考可持久化线段树的写法,将多行一起询问即可
说起来就是暴力啊……看数据范围真是不知道怎么A掉的……

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
#include<bits/stdc++.h>
using namespace std;

inline int getint()
{

int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x;
}
inline void putint(int x)
{

static char output[20];
static int out = 0;
for(; x >= 10; x /= 10) output[out++] = x % 10 + '0';
output[out++] = x + '0';
while(out) putchar(output[--out]); putchar('\n');
}

#define rep(i, l, r) for(register int i = (l); i <= (r); i++)
#define dep(i, r, l) for(register int i = (r); i >= (l); i--)

const int N = 1005;
const int M = 300005;
const int inf = 0x7fffffff;
typedef long long LL;

int n, m;
int a[N], b[M];

struct trie
{
trie *son[2];
int size;
};
trie* t[M];

inline trie* newtrie(const trie* v)
{
static trie pool[20000000], *C = pool;
*C = *v;
return C++;
}

inline trie* insert(trie* x, int v, int bit)
{
trie* p = newtrie(x);
p->size++;
if(bit == 0) return p;
int k = (v & bit) > 0;
p->son[k] = insert(x->son[k], v, bit >> 1);
return p;
}

struct node
{
trie *l, *r;
int v;
};
node Stack[N]; int top;

inline int getkth(node *Stack, int top, int K, int bit)
{

if(bit == 0) return 0;
int re = 0, k;
rep(i, 1, top)
{
k = (Stack[i].v & bit) == 0;
re += Stack[i].r->son[k]->size - Stack[i].l->son[k]->size;
}
if(K <= re)
{
rep(i, 1, top)
{
k = (Stack[i].v & bit) == 0;
Stack[i].r = Stack[i].r->son[k];
Stack[i].l = Stack[i].l->son[k];
}
return bit | getkth(Stack, top, K, bit >> 1);
}
else
{
rep(i, 1, top)
{
k = (Stack[i].v & bit) == 0;
Stack[i].r = Stack[i].r->son[k ^ 1];
Stack[i].l = Stack[i].l->son[k ^ 1];
}
return getkth(Stack, top, K - re, bit >> 1);
}
}

int main()
{

n = getint(), m = getint();
rep(i, 1, n) a[i] = getint();
rep(i, 1, m) b[i] = getint();

t[0] = new trie();
t[0]->size = 0, t[0]->son[0] = t[0]->son[1] = t[0];
rep(i, 1, m) t[i] = insert(t[i - 1], b[i], 1 << 30);

int Q, l1, r1, l2, r2, K;
Q = getint();
while(Q--)
{
l1 = getint(), r1 = getint(), l2 = getint(), r2 = getint(), K = getint();
top = 0;
rep(i, l1, r1)
{
Stack[++top].v = a[i];
Stack[ top].r = t[r2];
Stack[ top].l = t[l2 - 1];
}
putint(getkth(Stack, top, K, 1 << 30));
}
return 0;
}

[Prob 2] 平方运算

[Describtion]

现有一个长度为$N$的序列$ \lbrace X_1,X_2,…,X_N\rbrace $,要求支持两种操作:
$1.\ 0\ l\ r$ 表示将$\forall i\in [l,r],X_i = X_i^2\ {\rm mod}\ p$
$2.\ 1\ l\ r$ 询问$\sum_{l\leq i\leq r}X_i$

[Input]

第一行有三个整数$N,M,p$,分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。
接下来一行$N$个数代表一开始的序列$\lbrace X_1,X_2,…,X_N\rbrace $。
接下来$M$行,每行三个整数$op,l,r$。其中$op$代表本次操作的类型。若$op=0$,代表这是一次平方操作,平方的区间为$[l,r]$;如果$op=1$,代表这是一次询问操作,询问的区间为$[l,r]$。

[Output]

对于每次的询问操作,输出一行代表这段区间内数的总和。注意:答案没有对任何数取模。

[Sample Input]

1
2
3
4
5
3 3 11
1 2 3
1 1 3
0 1 3
1 1 3

[Sample Output]

1
2
6
14

[Hint]

对于$100\%$的数据,保证$\forall i, X_i\in[0, P)$, $l, r\in[1, n]$

测试点 N M P
1 ≤1000 ≤1000 =233
2 ≤1000 ≤1000 =2332
3 ≤100000 ≤100000 =5
4 ≤100000 ≤100000 =8192
5 ≤100000 ≤100000 =23
6 ≤100000 ≤100000 =45
7 ≤100000 ≤100000 =37
8 ≤55000 ≤55000 =4185
9 ≤55000 ≤55000 =5850
10 ≤55000 ≤55000 =2975
11 ≤55000 ≤55000 =2542
12 ≤55000 ≤55000 =2015
13 ≤60000 ≤60000 =2003
14 ≤65000 ≤65000 =2010
15 ≤70000 ≤70000 =4593
16 ≤75000 ≤75000 =4562
17 ≤80000 ≤80000 =1034
18 ≤85000 ≤85000 =5831
19 ≤90000 ≤90000 =9905
20 ≤100000 ≤100000 =9977

[Idea]

在模$P$意义下,每个数字最终都将进入循环
通过打表发现,在给定的$P$中,最后每个环的大小都很小,所有环长度的$LCM$小于$60$
所以我们可以维护线段树,每个节点维护这样一个环,每次暴力维护环即可
特别注意,那些不在环上的点。

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include<bits/stdc++.h>
using namespace std;

inline int getint()
{

int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x;
}
inline void putint(int x)
{

static char output[20];
static int out = 0;
for(; x >= 10; x /= 10) output[out++] = x % 10 + '0';
output[out++] = x + '0';
while(out) putchar(output[--out]); putchar('\n');
}

#define rep(i, l, r) for(register int i = (l); i <= (r); i++)
#define dep(i, r, l) for(register int i = (r); i >= (l); i--)

const int N = 100005;

int n, m, P;
bool on_ring[N];
int tot = 0, lab[N];
int a[N];

struct List
{
List* next;
int val;
inline void* operator new (size_t)
{

static List List_pool[20000000], *List_cnt = List_pool;
return List_cnt++;
}
};

inline List* getring(int x, int &len)
{
List *r = new List(), *head = r;
r->val = x;
len = 1;
for(int v = x * x % P; v != x; v = v * v % P)
{
r->next = new List();
r = r->next;
r->val = v;
len++;
}
return r->next = head;
}

inline List* merge(List* r2, List* r3, int len)
{
List *r1 = 0, *head;
for(int i = 1; i <= len; i++)
{
if(r1) r1->next = new List(), r1 = r1->next;
else head = r1 = new List();
r1->val = r2->val + r3->val;
r2 = r2->next;
r3 = r3->next;
}
return r1->next = head;
}

inline void merge(List* r1, List* r2, List* r3, int len)
{

for(int i = 1; i <= len; i++)
{
r1->val = r2->val + r3->val;
r1 = r1->next;
r2 = r2->next;
r3 = r3->next;
}
}

class Segment_tree
{
public :
inline void Build() {build(1, 1, n, a);}
inline void Modify(int l, int r) {modify(1, l, r);}
inline int Query(int l, int r) {return query(1, l, r);}
private:
struct node
{
int ll, rr;
int sum, lazy;
List *ring; int len;
};
node t[N << 2];
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)

inline void Rotate(int x, int v)
{

t[x].lazy += v;
v %= t[x].len;
for(int i = 1; i <= v; i++)
t[x].ring = t[x].ring->next;
t[x].sum = t[x].ring->val;
}

inline int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

inline void update(int x)
{

t[x].sum = t[lc(x)].sum + t[rc(x)].sum;
if(!t[x].len && t[lc(x)].len && t[rc(x)].len)
{
t[x].len = t[lc(x)].len * t[rc(x)].len / gcd(t[lc(x)].len, t[rc(x)].len);
t[x].ring = merge(t[lc(x)].ring, t[rc(x)].ring, t[x].len);
}
merge(t[x].ring, t[lc(x)].ring, t[rc(x)].ring, t[x].len);
}

inline void pushdown(int x)
{

if(t[x].lazy > 0)
{
Rotate(lc(x), t[x].lazy);
Rotate(rc(x), t[x].lazy);
t[x].lazy = 0;
}
}

inline void build(int x, int l, int r, int a[])
{

t[x].ll = l; t[x].rr = r;
t[x].lazy = t[x].len = 0;
t[x].ring = 0;
if(l == r)
{
if(on_ring[a[l]])
t[x].ring = getring(a[l], t[x].len);
return (void)(t[x].sum = a[l]);
}
int mid = (l + r) >> 1;
build(lc(x), l, mid, a);
build(rc(x), mid + 1, r, a);
update(x);
}

inline void modify(int x, int l, int r)
{

if(l <= t[x].ll && t[x].rr <= r)
{
if(t[x].len > 0)
Rotate(x, 1);
else if(t[x].ll == t[x].rr)
{

t[x].sum = t[x].sum * t[x].sum % P;
if(on_ring[t[x].sum])
t[x].ring = getring(t[x].sum, t[x].len);
}
else
{
modify(lc(x), l, r);
modify(rc(x), l, r);
update(x);
}
return;
}
pushdown(x);
int mid = (t[x].ll + t[x].rr) >> 1;
if(l <= mid) modify(lc(x), l, r);
if(mid < r ) modify(rc(x), l, r);
update(x);
}

inline int query(int x, int l, int r)
{

if(l <= t[x].ll && t[x].rr <= r)
return t[x].sum;
pushdown(x);
int mid = (t[x].ll + t[x].rr) >> 1, re = 0;
if(l <= mid) re += query(lc(x), l, r);
if(mid < r ) re += query(rc(x), l, r);
return re;
}

};

Segment_tree Tree;

inline void dfs(int x)
{

if(lab[x])
{
if(lab[x] != tot) return;
int v = x;
do {
on_ring[v] = true;
v = v * v % P;
} while(v != x);
return;
}
lab[x] = tot;
dfs(x * x % P);
}

int main()
{

n = getint(), m = getint(), P = getint();
rep(i, 0, P - 1) if(!lab[i]) ++tot, dfs(i);

rep(i, 1, n) a[i] = getint();
Tree.Build();
for(int i = 1, l, r, k; i <= m; i++)
{
k = getint(), l = getint(), r = getint();
if(k == 0) Tree.Modify(l, r);
if(k == 1) putint(Tree.Query(l, r));
}
return 0;
}

[Prob 3] 解密运算

[Describtion]

对于一个长度为$N$的字符串,我们在字符串的末尾添加一个特殊的字符”.”。
之后将字符串视为一个环,从位置$1,2,3,…,N+1$为起点读出$N+1$个字符,就能得到$N+1$个字符串。
比如对于字符串“ABCAAA”,我们可以得到这$N+1$个串:
ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA
接着我们对得到的这N+1个串按字典序从小到大进行排序(注意特殊字符“.”的字典序小于任何其他的字符)结果如下:
.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB
最后,将排序好的N+1个串的最后一个字符取出,按照顺序排成一个新的字符串,也就是上面这个表的最后一列,就是加密后的密文“AAAC.AB”。
请通过加密后的密文求出加密前的字符串。

[Input]

第一行有两个整数$N,M$,分别表示加密前的字符串长度和字符集大小,其中字符用整数$1,2,3,…,M$编号,添加的特殊字符“.”用$0$编号。
第二行为$N+1$个整数,表示加密后的字符串。

[Output]

输出仅一行,包含$N$个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。

[Sample Input]

1
2
6 3
1 1 1 3 0 1 2

[Sample Output]

1
1 2 3 1 1 1

[Hint]

$N, M\leq 200000$

[Idea]

这个其实就是$BWT$加密,自行查资料脑补……

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<bits/stdc++.h>
using namespace std;

inline int getint()
{

int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x;
}

inline void putint(int x)
{

static char output[20];
static int out = 0;
for(; x >= 10; x /= 10) output[out++] = x % 10 + '0';
output[out++] = x + '0';
while(out) putchar(output[--out]); putchar(' ');
}

#define rep(i, l, r) for(register int i = (l); i <= (r); i++)
#define dep(i, r, l) for(register int i = (r); i >= (l); i--)

const int N = 200005;

int n, m;
int L[N], T[N];
int sum[N], cnt[N];

int main()
{

n = getint(); m = getint();
rep(i, 1, n + 1)
{
L[i] = getint();
cnt[i] = ++sum[L[i]];
}
rep(i, 1, m) sum[i] += sum[i - 1];
int s = 1;
dep(i, n, 1)
{
T[i] = L[s];
s = sum[L[s] - 1] + cnt[s];
}
rep(i, 1, n) putint(T[i]);
return 0;
}