自动搬运

查看原文

来自洛谷，原作者为

	modfish_ 你指尖跃动的电光，事静电罢（恼

搬运于2025-08-24 23:05:24，当前版本为作者最后更新于2024-10-20 20:14:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

先提出一个结论（以下讨论均局限于询问的区间 $(x,y)$ 中）：

令第二个人可以操作的区间集合为 $S$，即：

如果存在一个区间 $(L,R)$ 满足：

• 第一个人可以操作 $(L,R)$，即 $R-L+1\le c_1,\sum_{i=l}^r\le w_1$。

• $(L,R)$ 包含 $S$ 中所有的区间，即 $L\le\min_{(l,r)\in S}l,R\ge\min_{(l,r)\in S}r$。

并且如果忽略第二个人的存在，这个区间可以全部变成红色，即 $\max_{i=x}^ya_i\le w_1$。

如果以上两个条件均满足，那么第一个人会赢。否则第二个人会赢。

证明

先证充分性：充分性是显然的。第一个人只需要先把 $S$ 没有覆盖的点变成红色，再对 $(L,R)$ 操作，一次性把剩下的点变红，第一个人就赢了。

然后证必要性：考虑反证。假设不存在区间 $(L,R)$，下面给出一种第二个人的操作策略，使得第一个人无法胜利。

设 $S$ 中左端点最靠左的区间为 $(l_1,r_1)$，右端点最靠右的区间为 $(l_2,r_2)$。

假设第一个人操作了区间 $(l_3,r_3)$：

• 若 $l_3\le l_1\le r_3$，即操作影响了 $l_1$，那么操作区间 $(l_1,r_1)$，使 $l_1$ 变回蓝色。

• 若 $l_3\le r_2\le r_3$，即操作影响了 $r_2$，那么操作区间 $(l_2,r_2)$，使 $r_2$ 变回蓝色。

• 否则，可以任意进行操作。

因为第一个人的可操作区间中不存在 $(L,R)$ 满足 $L\le l_1,R\ge r_2$，所以前两种情况不会同时出现，故这个操作是可以实现的。而这样操作保证了每一轮操作后 $a_{l_1},a_{r_2}$ 中至少有一个是蓝色的，故第一个人不可能获胜。

于是我们证明了这个结论。于是我们可以对于每次询问，找到集合 $S$ 的左边界和右边界（即证明中提到的 $l_1,r_2$），然后判断是否存在一个区间 $(L,R)$，满足开始提到的两个条件即可。

容易发现，当且仅当第一个人可以操作 $(l_1,r_2)$ 时，满足条件的 $(L,R)$ 存在。这是因为，区间的长度越长，其区间和就越大，就越有可能不满足条件，所以 $(l_1,r_2)$ 是最有可能满足条件的区间。所以直接判断 $r_2-l_1+1\le c_1,\sum_{i=l_1}^{r_2}a_i\le w_1$ 是否成立即可。

那么如何寻找 $(l_1,r_2)$ 呢？同样容易发现，区间的长度越短，其区间和就越小，就越有可能不能被第二个人操作。所以，只需要找所有长度为 $c_2$ 的区间进行判断即可。

可以维护一个值 $f_i$ 表示 $a_i$ 到 $a_{i+c_2-1}$ 的，即：

那么，$l_1$ 就是满足 $f_i>w_2$ 的最小的 $i$，$r_2-c_2+1$ 就是满足 $f_i>w_2$ 的最大的 $i$。可以用线段树维护 $f_i$，查询时在线段树上二分即可。这样就得到了 $(l_1,r_2)$。

当然，如果 $y-x+1<c_2$，就只需要判一下 $(x,y)$ 能不能被第二个人操作即可。

总结一下，具体的步骤就是：

• 先判一下 $\max_{i=x}^ya_i\le w_1$ 是否成立，若不成立直接输出 tetris。

• 然后判断 $y-x+1$ 与 $c_2$ 的大小关系。如果 $y-x+1<c_2$，直接判断 $\sum_{i=x}^ya_i>w_2$ 是否成立，若成立就令 $l_1=x,r_2=y$，否则输出 cont（因为这时第二个人无法操作）。

• 如果 $y-x+1\le c_2$，就用之前讲的方法求 $(l_1,r_2)$。

• 最后判断第一个人能否操作 $(l_1,r_2)$，即 $r_2-l_1+1\le c_1,\sum_{i=l_1}^{r_2}a_i\le w_1$ 是否成立。若成立则输出 cont，否则输出 tetris。

然后就做完了。修改使用线段树、树状数组容易维护。时间复杂度 $O(q\log n)$。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 3e5 + 5;

int n, q, c1, c2;
ll w1, w2;
ll a[maxn], tr[maxn];

void upd(int id, ll k){
	for(int i = id; i <= n; i += i & -i) tr[i] += k; 
}
ll que(int id){
	ll s = 0;
	for(int i = id; i > 0; i -= i & -i) s += tr[i];
	return s;
}
namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2], tag[maxn << 2];
void up(int x){
	max1[x] = max(max1[l(x)], max1[r(x)]);
}
void down(int x){
	max1[l(x)] += tag[x], tag[l(x)] += tag[x];
	max1[r(x)] += tag[x], tag[r(x)] += tag[x];
	tag[x] = 0;
}
void update(int x, int l, int r, int ql, int qr, ll k){
	if(ql <= l && r <= qr){
		max1[x] += k, tag[x] += k;
		return;
	}
	down(x);
	int mid = l + r >> 1;
	if(ql <= mid) update(l(x), l, mid, ql, qr, k);
	if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);
	up(x);
}
int query1(int x, int l, int r, int ql, int qr, ll k){
	if(ql <= l && r <= qr){
		if(max1[x] <= k) return 0;
		if(l == r){
			if(max1[x] > k) return l;
			else return 0;
		}
		down(x);
		int mid = l + r >> 1;
		if(max1[l(x)] > k) return query1(l(x), l, mid, ql, qr, k);
		else return query1(r(x), mid + 1, r, ql, qr, k);
	}
	down(x);
	int mid = l + r >> 1, res = 0;
	if(ql <= mid) res = query1(l(x), l, mid, ql, qr, k);
	if(res) return res;
	if(qr > mid) res = query1(r(x), mid + 1, r, ql, qr, k);
	return res;
}
int query2(int x, int l, int r, int ql, int qr, ll k){
	if(ql <= l && r <= qr){
		if(max1[x] <= k) return 0;
		if(l == r){
			if(max1[x] > k) return l;
			else return 0;
		}
		down(x);
		int mid = l + r >> 1;
		if(max1[r(x)] > k) return query2(r(x), mid + 1, r, ql, qr, k);
		else return query2(l(x), l, mid, ql, qr, k);
	}
	down(x);
	int mid = l + r >> 1, res = 0;
	if(qr > mid) res = query2(r(x), mid + 1, r, ql, qr, k);
	if(res) return res;
	if(ql <= mid) res = query2(l(x), l, mid, ql, qr, k);
	return res;
}}
namespace seg2{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2];
void up(int x){
	max1[x] = max(max1[l(x)], max1[r(x)]);
}
void build(int x, int l, int r){
	if(l == r){
		max1[x] = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(l(x), l, mid), build(r(x), mid + 1, r);
	up(x);
}
void update(int x, int l, int r, int id, ll k){
	if(l == r){
		max1[x] += k;
		return;
	}
	int mid = l + r >> 1;
	if(id <= mid) update(l(x), l, mid, id, k);
	else update(r(x), mid + 1, r, id, k);
	up(x);
}
ll query(int x, int l, int r, int ql, int qr){
	if(ql <= l && r <= qr) return max1[x];
	int mid = l + r >> 1;
	ll res = 0;
	if(ql <= mid) res = max(res, query(l(x), l, mid, ql, qr));
	if(qr > mid) res = max(res, query(r(x), mid + 1, r, ql, qr));
	return res;
}}

int main(){
	scanf("%d %d %d %d %lld %lld", &n, &q, &c1, &c2, &w1, &w2);
	for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i ++){
		upd(i, a[i]);
		seg::update(1, 1, n, max(1, i - c2 + 1), i, a[i]);
	}
	seg2::build(1, 1, n);
	while(q --){
		int op;
		scanf("%d", &op);
		if(op == 1){
			int x;
			ll y;
			scanf("%d %lld", &x, &y);
			upd(x, y);
			seg::update(1, 1, n, max(1, x - c2 + 1), x, y);
			seg2::update(1, 1, n, x, y);
			a[x] += y;
		}else{
			int l, r;
			scanf("%d %d", &l, &r);
			if(seg2::query(1, 1, n, l, r) > w1){
				printf("tetris\n");
				continue;
			}
			int L = 0, R = 0;
			if(r - l + 1 <= c2){
				if(que(r) - que(l - 1) > w2) L = l, R = r;
			}else{
				L = seg::query1(1, 1, n, l, r - c2 + 1, w2);
				R = seg::query2(1, 1, n, l, r - c2 + 1, w2) + c2 - 1;
			}
			if(!L || !R){
				printf("cont\n");
				continue;
			}
			if(que(R) - que(L - 1) <= w1 && R - L + 1 <= c1) printf("cont\n");
			else printf("tetris\n");
		}
	}
	return 0;
}