社区讨论
样例没过,求条(玄两关)
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 条回复,欢迎继续交流。
正在加载回复...