https://codeforces.com/contest/1179

A. Valeriy and Deque

 

题意：一个队列，每次拿出队首和队首后面那个，把大的放回队首，小的放到队尾，多次询问，问第m次操作时拿出的是哪两个数。

模拟

显然如果队首是最大值，以后就是队列其他元素循环。所以先模拟到把最大值放到队首，以后只要看循环到哪里即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n, q, mx, cnt, A, B;
ll m;
int ansa[N], ansb[N];
deque<int>dq;
vector<int>vc;
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		dq.push_back(x);
		mx = max(mx, x);
	}
	while (dq.front() < mx) {
		cnt++;
		A = dq.front(); dq.pop_front();
		B = dq.front(); dq.pop_front();
		ansa[cnt] = A, ansb[cnt] = B;
		dq.push_front(max(A, B)); dq.push_back(min(A, B));
	}
	dq.pop_front();
	while (!dq.empty()) {
		vc.push_back(dq.front());
		dq.pop_front();
	}
	while (q--) {
		scanf("%lld", &m);
		if (m <= cnt)printf("%d %d\n", ansa[m], ansb[m]);
		else {
			printf("%d %d\n", mx, vc[(m - cnt - 1) % (ll)vc.size()]);
		}
	}
	return 0;
}

 

B. Tolik and His Uncle

 

题意：nm的网格，从左上角开始，要走遍所有格子，每格停一次，且走的向量不能重复，构造走的序列。

构造

考虑只有一行时，左右走位，1，n，2，n-1，···

同样还是左右走，不过要在两行里跳，左上到右下，走中心对称。走完两行后再向中间缩，再走两行，直到走完或者还剩一行，对这一行就向之前说的左右走位。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n, m;
void pr(int U, int D) {
	int L = 1, R = m;
	while (L <= m) {
		printf("%d %d\n", U, L++);
		printf("%d %d\n", D, R--);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int U = 1, D = n;
	while (U < D) {
		pr(U++, D--);
	}
	if (U == D) {
		int L = 1, R = m;
		while (L < R) {
			printf("%d %d\n", U, L++);
			printf("%d %d\n", U, R--);
		}
		if (L == R)printf("%d %d\n", U, L);
	}
	return 0;
}

 

C. Serge and Dining Room

 

题意：排队买饭，队伍里有n个人，每人有钱数，m道菜，各有价格，每道菜只有1份，每人只买他能买到的最贵的菜。问最终剩下的菜里最贵的价格。

线段树

考虑什么时候一道菜会没人买。

只有当能买得起的人数小于比它贵的菜数，它才没人买。注意可能存在买得起的人小于比它贵的菜数，但它仍被买了，原因是有人买不起更贵的，只能买这个菜，这时更贵的那个就没人买了，就是答案。

所以就是要找最大的，买的起的人数小于比它贵的菜数的价格。

权值线段树维护区间修改，对每道菜从1到它的价格区间+1，表明它比这些价格贵，每个人从1到钱数区间-1，表明能买得起这些价格，最终要找最右的大于值0的位置。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n, m, q;
int a[N], b[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2], laz[N << 2];
void up(int rt) {
	tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
void down(int rt) {
	int& x = laz[rt];
	if (x) {
		tr[rt << 1] += x;
		tr[rt << 1 | 1] += x;
		laz[rt << 1] += x;
		laz[rt << 1 | 1] += x;
		x = 0;
	}
}
void upda(int ql, int qr, int x, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		tr[rt] += x;
		laz[rt] += x;
		return;
	}
	down(rt);
	if (ql <= mid)upda(ql, qr, x, lson);
	if (qr > mid)upda(ql, qr, x, rson);
	up(rt);
}
int query(int l, int r, int rt) {
	if (l == r)return l;
	down(rt);
	if (tr[rt << 1 | 1] > 0)return query(rson);
	else return query(lson);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		upda(1, a[i], 1, 1, N-1, 1);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &b[i]);
		upda(1, b[i], -1, 1, N-1, 1);
	}
	scanf("%d", &q);
	while (q--) {
		int op, k, x;
		scanf("%d%d%d", &op, &k, &x);
		if (op == 1) {
			if (x > a[k])upda(a[k] + 1, x, 1, 1, N-1, 1);
			if (x < a[k])upda(x + 1, a[k], -1, 1, N-1, 1);
			a[k] = x;
		}
		else {
			if (x > b[k])upda(b[k] + 1, x, -1, 1, N-1, 1);
			if (x < b[k])upda(x + 1, b[k], 1, 1, N-1, 1);
			b[k] = x;
		}
		if (tr[1] <= 0)puts("-1");
		else printf("%d\n", query(1, N-1, 1));
	}
	return 0;
}