稳健型选手

题目链接：UNR #6 C

题目大意

有一排卡牌，然后每次询问一个区间，问先手最多的分数。
玩法是先手后手轮流选一张牌拿走，先手任选，后手一定会选最左边的。
然后分数是拿的牌的分数和。

思路

考虑一次询问怎么搞：
不难想到一个反着的贪心，每次把数加进堆里面，每次有偶数个就把最大的拿走。

发现奇数有问题，不过你会发现奇数的话最后一个数一定会去到，所以可以转化成偶数的问题。

其实不难又想到一个前面的贪心：
两个两个看，先拿优的（扔进堆里），然后看劣的会不会之前最劣的优的优，然后换。

然后考虑你有两个方向的贪心，有没有什么搞头。
那就类似扩展，考虑分治，于是考虑解决跨过 mid 的询问。

然后你考虑从 mid 往两边扩展得到两边的贪心，问题是如何合并两边的贪心。
思考一下过程，就是左边一些选了的不选，右边的一些不选的选了。

那我们可以用两个主席树分别记录左边选了的，右边不选的。
（因为要主席树所以记得要离散化）
然后我们二分一个交换数量，使得最优即可。

然后注意到基本上都是两个两个处理，所以要分端点的奇偶来分开搞。
然后就差不多了。

代码

#include
#include
#include
#include
#include
#define ll long long

using namespace std;

const int N = 2e5 + 100;
int n, Q, a[N], num, b[N], X[N], Y[N];
//int g[N], b[N];
//priority_queue , vector >, less > > q;
vector <int> qq, qu[N];
ll ans[N], pre[N], suf[N];
int rt1[N], rt2[N];
priority_queue <int> q;

struct XD_tree {
	int num[N << 6], ls[N << 6], rs[N << 6], tot; ll sum[N << 6];
	
	int copy(int x) {
		int now = ++tot;
		num[now] = num[x]; ls[now] = ls[x]; rs[now] = rs[x]; sum[now] = sum[x];
		return now;
	}
	
	void change(int &now, int l, int r, int pl, int val) {
		now = copy(now); num[now] += val; sum[now] += 1ll * b[pl] * val;
		if (l == r) return ;
		int mid = (l + r) >> 1;
		if (pl <= mid) change(ls[now], l, mid, pl, val); else change(rs[now], mid + 1, r, pl, val);
	}
	
	int ask(int now, int l, int r, int k) {
		if (l == r) return l;
		int mid = (l + r) >> 1;
		if (num[ls[now]] >= k) return ask(ls[now], l, mid, k);
			else return ask(rs[now], mid + 1, r, k - num[ls[now]]);
	}
	
	ll query(int now, int l, int r, int k) {
		if (k >= num[now]) return sum[now];
		if (k <= 0) return 0;
		if (l == r) return 1ll * b[l] * k;
		int mid = (l + r) >> 1;
		if (num[ls[now]] >= k) return query(ls[now], l, mid, k);
			else return sum[ls[now]] + query(rs[now], mid + 1, r, k - num[ls[now]]);
	}
	
	void clear(int m) {
		tot = 0;
	}
}T;

void slove(int l, int r, vector <int> p) {
	if (!p.size()) return ;
	for (int i = l; i <= r; i++) qu[i].clear();
	int mid = (l + r) >> 1; vector <int> lp, rp; lp.clear(); rp.clear();
	
	for (int i = 0; i < p.size(); i++) { int id = p[i];
		if (Y[id] <= mid) {lp.push_back(id); continue;}
		if (mid < X[id]) {rp.push_back(id); continue;}
		qu[X[id]].push_back(id);
	}
	
	for (int op = 0; op < 2; op++) {
		int m = mid + op; while (!q.empty()) q.pop(); T.clear(m);
		pre[m] = suf[m + 1] = 0; rt1[m] = rt2[m + 1] = 0;
		for (int i = m + 1; i <= r; i++) {//右边（主席树记录空的） 
			rt1[i] = rt1[i - 1]; pre[i] = pre[i - 1];
			if ((i - m) % 2 == 0) {
				int x = i, y = i - 1; if (a[x] > a[y]) swap(x, y);
				pre[i] += b[a[y]]; q.push(-a[y]);
				if (!q.empty() && -q.top() < a[x]) {
					int val = -q.top(); q.pop();
					q.push(-a[x]); pre[i] += b[a[x]] - b[val];
					T.change(rt1[i], 1, b[0], val, 1);
				}
				else T.change(rt1[i], 1, b[0], a[x], 1);
			}
		}
		while (!q.empty()) q.pop();
		for (int i = m; i >= l; i--) {//左边（主席树记录有的） 
			rt2[i] = rt2[i + 1]; suf[i] = suf[i + 1]; q.push(a[i]);
			if ((m - i + 1) % 2 == 0) {
				int x = q.top(); q.pop();
				suf[i] += b[x]; T.change(rt2[i], 1, b[0], x, 1);
			}
		}
		while (!q.empty()) q.pop();
		for (int i = m - 1; i >= l; i -= 2) {
			for (int pp = 0; pp < qu[i].size(); pp++) { int id = qu[i][pp];
				int x = X[id], y = Y[id];
				int L = 1, R = min((y - m) / 2, (m - x + 1) / 2), re = 0;
				while (L <= R) {
					int mid = (L + R) >> 1;
					if (T.ask(rt1[y], 1, b[0], (y - m) / 2 - mid + 1) >= T.ask(rt2[x], 1, b[0], mid)) re = mid, L = mid + 1;
						else R = mid - 1;
				}
				ll val = suf[x] + pre[y];
				val -= T.query(rt2[x], 1, b[0], re);
				val += T.sum[rt1[y]] - T.query(rt1[y], 1, b[0], (y - m) / 2 - re);
				ans[id] += val;
			}
		}
	}
	
	slove(l, mid, lp); slove(mid + 1, r, rp);
}

int main() {
//	freopen("ex_game4.in", "r", stdin);
//	freopen("write.txt", "w", stdout);
	
	scanf("%d %d", &n, &Q);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
	
//	if ((n <= 500 && Q <= 500) || Q == 1) {
//		for (int p = 1; p <= Q; p++) {
//			int l, r; scanf("%d %d", &l, &r);
//			num = (r - l + 1 + 1) / 2;
//			for (int i = 1; i <= num; i++) {
//				if (i == num && (r - l + 1) & 1) {
//					g[i] = a[r]; b[i] = 0;
//				}
//				else {
//					g[i] = max(a[l + (i - 1) * 2], a[l + (i - 1) * 2 + 1]);
//					b[i] = min(a[l + (i - 1) * 2], a[l + (i - 1) * 2 + 1]);
//				}
//			}
//			
//			ll di = g[num]; while (!q.empty()) q.pop();
//			q.push(make_pair(b[num], num));
//			for (int i = num - 1; i >= 1; i--) {
//				di += g[i];
//				if (q.top().first > g[i]) {
//					di += q.top().first - g[i];
//					q.pop();
//					q.push(make_pair(g[i], i));
//				}
//				q.push(make_pair(b[i], i));
//			}
//			printf("%lld\n", di);
//		}
//		
//		return 0;
//	}
	
	sort(b + 1, b + n + 1); b[0] = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + b[0] + 1, a[i]) - b;
	
	for (int i = 1; i <= Q; i++) {
		scanf("%d %d", &X[i], &Y[i]);
		int x = X[i], y = Y[i];
		if ((y - x + 1) & 1) ans[i] = b[a[Y[i]]], Y[i]--, y--;
		if (x > y) continue;
		qq.push_back(i);
	}
	
	slove(1, n, qq);
	for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
	
	return 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
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