- 转换成一个数在(0,X + Y)的加减问题
- 考虑一种使用线段树处理的方法， 维护前缀最大值， 前缀最小值， 前缀和， 然后查询的时候先询问右区间是否会同时碰到上下界， 会的话左区间无用直接递归右区间， 否则的话递归左区间， 然后右区间只会碰到上边界或者下边界， 分两种情况讨论即可
#include#include #include #include #include #define M 500010#define ls now << 1#define rs now << 1 | 1#define lson l, mid, now << 1#define rson mid + 1, r, now << 1 | 1#define ll long long#define mmp make_pairusing namespace std;int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f;}int n, q, x, y, z;ll sum[M << 2], minn[M << 2], maxx[M << 2];void pushup(int now) { sum[now] = sum[ls] + sum[rs]; minn[now] = min(minn[ls], sum[ls] + minn[rs]); maxx[now] = max(maxx[ls], sum[ls] + maxx[rs]);}void modify(int l, int r, int now, int pl, int v) { if(l > pl || r < pl) return; if(l == r) { sum[now] = v; minn[now] = min(v, 0); maxx[now] = max(v, 0); return; } int mid = (l + r) >> 1; modify(lson, pl, v), modify(rson, pl, v); pushup(now);}ll s;ll merge(ll v, int now) { if(v + maxx[now] > s) return s - maxx[now] + sum[now]; if(v + minn[now] < 0) return sum[now] - minn[now]; return v + sum[now];}ll query(int l, int r, int now, ll v) { if(l == r) return max(min(s, sum[now] + v), 0ll); int mid = (l + r) >> 1; if(maxx[rs] - minn[rs] > s) return query(rson, 0); else return merge(query(lson, v), rs);}int main() {// freopen("stone1.in", "r", stdin); n = read(), q = read(); x = read(), y = read(); for(int i = 1; i <= n; i++) { z = read(); if(i % 2 == 0) z = -z; modify(1, n, 1, i, z); } while(q--) { int op = read(); if(op == 1) x = read(); else if(op == 2) y = read(); else { int pl = read(), v = read(); if(pl % 2 == 0) v = -v; modify(1, n, 1, pl, v); } s = x + y; cout << query(1, n, 1, x) << "\n"; } return 0;}