社区讨论

样例没过,求条(玄两关)

P2572[SCOI2010] 序列操作参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lyb0h4t7
此快照首次捕获于
2024/07/07 11:46
2 年前
此快照最后确认于
2024/07/07 14:59
2 年前
查看原帖
rt。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, op, l, r, a[N];
namespace Segment_Tree {
	#define mid (L + R) >> 1
	#define lson ls(p), L, (L + R) >> 1
	#define rson rs(p), ((L + R) >> 1) + 1, R
	#define son p, L, R
	int mx[N << 2], tag[N << 2], lmx[N << 2], rmx[N << 2], sum[N << 2], len[N << 2], Tag[N << 2];
	inline int ls(int p) {return p << 1;}
	inline int rs(int p) {return p << 1 | 1;}
	inline void psup(int p) {
		sum[p] = sum[ls(p)] + sum[rs(p)];
		if(mx[ls(p)] == len[ls(p)]) lmx[p] = mx[ls(p)] + lmx[rs(p)];
		else lmx[p] = lmx[ls(p)];
		if(mx[rs(p)] == len[rs(p)]) rmx[p] = mx[rs(p)] + rmx[ls(p)];
		else rmx[p] = rmx[rs(p)];
		mx[p] = max({mx[ls(p)], mx[rs(p)], rmx[ls(p)] + lmx[rs(p)]});
	}
	inline void build(int p = 1, int L = 1, int R = n) {
		len[p] = R - L + 1;
		if(L == R) {
			mx[p] = lmx[p] = rmx[p] = sum[p] = a[L];
			return;
		}
		build(lson), build(rson), psup(p);
	}
	inline void work(int p) {
		sum[p] = len[p] - sum[p];
		Tag[p] ^= 1;
	}
	inline void work1(int p) {
		sum[p] = mx[p] = lmx[p] = rmx[p] = 0;
		tag[p] = 1;
	}
	inline void work2(int p) {
		sum[p] = mx[p] = lmx[p] = rmx[p] = len[p];
		tag[p] = 2;
	}
	inline void psd(int p, int L, int R) {
		if(! tag[p]) goto place;
		else if(tag[p] == 1) work1(ls(p)), work1(rs(p));
		else work2(ls(p)), work2(rs(p));
		tag[p] = 0;
		place:;
		if(! Tag[p]) return;
		else work(ls(p)), work(rs(p));
		Tag[p] = 0;
	}
	inline void cover(int l, int r, int k, int p = 1, int L = 1, int R = n) {
		if(l <= L && R <= r) {
			if(! k) work1(p);
			else work2(p);
			return;
		}
		psd(son);
		if(l <= mid) cover(l, r, k, lson);
		if(r > mid) cover(l, r, k, rson);
		psup(p);
	}
	inline void flip(int l, int r, int p = 1, int L = 1, int R = n) {
		if(l <= L && R <= r) {
			work(p);
			return;
		}
		psd(son);
		if(l <= mid) flip(l, r, lson);
		if(r > mid) flip(l, r, rson);
		psup(p);
	}
	inline int gts(int l, int r, int p = 1, int L = 1, int R = n) {
		int res = 0;
		if(l <= L && R <= r) return sum[p];
		psd(son);
		if(l <= mid) res += gts(l, r, lson);
		if(r > mid) res += gts(l, r, rson);
		return res;
	}
	inline int query(int l, int r, int p = 1, int L = 1, int R = n) {
		int res = 0;
		if(l <= L && R <= r) return max({mx[p], lmx[p], rmx[p]});
		psd(son);
		if(l <= mid) res = max(res, query(l, r, lson));
		if(r > mid) res = max(res, query(l, r, rson));
		return res;
	}
}
using namespace Segment_Tree;
signed main() {
	ios_base :: sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++ i)
		cin >> a[i];
	build();
	while(m --) {
		cin >> op >> l >> r;
		++ l, ++ r;
		if(op == 0) cover(l, r, 0);
		else if(op == 1) cover(l, r, 1);
		else if(op == 2) flip(l, r);
		else if(op == 3) cout << gts(l, r) << '\n';
		else cout << query(l, r) << '\n';
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...