https://www.luogu.org/problemnew/show/P4243#sub
自己的思路错了
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5 + 10; #define gc getchar() int F[N << 2], tot[N << 2], l_col[N << 2], r_col[N << 2]; int n, Ty, Answer; int my[N], data[N]; inline int read() { int x = 0, f = 1; char c = gc; while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x * f; } #define lson jd << 1 #define rson jd << 1 | 1 void Push_up(int jd) { l_col[jd] = l_col[lson]; r_col[jd] = r_col[rson]; tot[jd] = tot[lson] + tot[rson]; if(r_col[lson] == l_col[rson]) tot[jd] --; return ; } void Build_tree(int l, int r, int jd) { if(l == r) {l_col[jd] = r_col[jd] = data[l]; tot[jd] = 1; return ;} int mid = (l + r) >> 1; Build_tree(l, mid, lson); Build_tree(mid + 1, r, rson); Push_up(jd); } void Push_down(int jd) { F[lson] += F[jd]; F[rson] += F[jd]; l_col[lson] += F[jd]; r_col[lson] += F[jd]; l_col[rson] += F[jd]; r_col[rson] += F[jd]; F[jd] = 0; return ; } void Poi_G(int l, int r, int jd, int x, int num) { if(l == r) {l_col[jd] += num; r_col[jd] += num; return ;} if(F[jd]) Push_down(jd); int mid = (l + r) >> 1; if(x <= mid) Poi_G(l, mid, lson, x, num); else Poi_G(mid + 1, r, rson, x, num); Push_up(jd); } void Sec_G(int l, int r, int jd, int x, int y, int num) { if(x <= l && r <= y) {F[jd] += num; l_col[jd] += num; r_col[jd] += num; return ;} if(F[jd]) Push_down(jd); int mid = (l + r) >> 1; if(x <= mid) Sec_G(l, mid, lson, x, y, num); if(y > mid) Sec_G(mid + 1, r, rson, x, y, num); Push_up(jd); } void Sec_A(int l, int r, int jd, int x, int y) { if(x <= l && r <= y) {Answer += tot[jd]; return ;} if(F[jd]) Push_down(jd); int mid = (l + r) >> 1; if(x <= mid) Sec_A(l, mid, lson, x, y); if(y > mid) Sec_A(mid + 1, r, rson, x, y); if(x <= mid && y > mid && r_col[lson] == l_col[rson]) Answer --; } int main() { n = read(); for(int i = 1; i <= n; i ++) my[i] = read(); for(int i = 1; i <= n; i ++) data[i] = my[i] - my[i - 1]; Build_tree(1, n, 1); Ty = read(); while(Ty --) { string s; cin >> s; if(s[0] == 'A') { int l = read(), r = read(), a = read(), b = read(); int imp = a + (r - l) * b; if(l != 1) Poi_G(1, n, 1, l, a); Sec_G(1, n, 1, l + 1, r, b); Poi_G(1, n, 1, r + 1, - imp); } else { Answer = 0; int l = read(), r = read(); if(l == r) {cout << "1" << endl; continue ;} Sec_A(1, n, 1, l, r); cout << Answer << endl; } } return 0; }
https://www.cnblogs.com/zbtrs/p/8424737.html
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const ll maxn = 500010; ll n,a[maxn],b[maxn],q; struct node { ll ls,rs,lsize,rsize,sum,tag,sizee; void init() { ls = rs = lsize = rsize = sum = tag = sizee = 0; } } e[maxn]; void pushdown(ll o) { if (e[o].tag) { e[o * 2].tag += e[o].tag; e[o * 2 + 1].tag += e[o].tag; e[o * 2].ls += e[o].tag; e[o * 2 + 1].ls += e[o].tag; e[o * 2].rs += e[o].tag; e[o * 2 + 1].rs += e[o].tag; e[o].tag = 0; } } node pushup(node a,node b) { bool flag = (a.rs == b.ls); node c; c.init(); c.ls = a.ls; c.rs = b.rs; c.sizee = a.sizee + b.sizee; c.sum = a.sum + b.sum; if (a.sum == 0 && b.sum == 0) { if (!flag) { c.lsize = a.sizee + b.sizee; c.rsize = a.sizee + b.sizee; } else { c.lsize = a.lsize - 1; c.rsize = b.rsize - 1; ++c.sum; } return c; } if (a.sum == 0) { c.rsize = b.rsize; if (!flag) c.lsize = a.sizee + b.lsize; else { c.lsize = a.lsize - 1; if (b.lsize > 0) c.sum += (b.lsize - 1) / 2 + 1; } return c; } if (b.sum == 0) { c.lsize = a.lsize; if (!flag) c.rsize = b.sizee + a.rsize; else { c.rsize = b.rsize - 1; if (a.rsize > 0) c.sum += (a.rsize - 1) / 2 + 1; } return c; } c.lsize = a.lsize; c.rsize = b.rsize; if (a.rsize == 0 && b.lsize == 0) { if (flag) c.sum--; return c; } if (a.rsize == 0) { if (flag) c.sum += (b.lsize - 1) / 2; else c.sum += b.lsize / 2; return c; } if (b.lsize == 0) { if (flag) c.sum += (a.rsize - 1) / 2; else c.sum += a.rsize / 2; return c; } ll minn = (a.rsize + b.lsize) / 2; if (flag) minn = min(minn,1 + (a.rsize - 1) / 2 + (b.lsize - 1) / 2); c.sum += minn; return c; } void build(ll o,ll l,ll r) { if (l == r) { e[o].init(); e[o].ls = e[o].rs = b[l]; e[o].lsize = e[o].rsize = 1; e[o].sizee = 1; return; } ll mid = (l + r) >> 1; build(o * 2,l,mid); build(o * 2 + 1,mid + 1,r); e[o] = pushup(e[o * 2],e[o * 2 + 1]); } void update1(ll o,ll l,ll r,ll pos,ll v) { if (l == r) { e[o].ls += v; e[o].rs += v; return; } pushdown(o); ll mid = (l + r) >> 1; if (pos <= mid) update1(o * 2,l,mid,pos,v); else update1(o * 2 + 1,mid + 1,r,pos,v); e[o] = pushup(e[o * 2],e[o * 2 + 1]); } void update2(ll o,ll l,ll r,ll x,ll y,ll v) { if (x <= l && r <= y) { e[o].ls += v; e[o].rs += v; e[o].tag += v; return; } pushdown(o); ll mid = (l + r) >> 1; if (x <= mid) update2(o * 2,l,mid,x,y,v); if (y > mid) update2(o * 2 + 1,mid + 1,r,x,y,v); e[o] = pushup(e[o * 2],e[o * 2 + 1]); } node query(ll o,ll l,ll r,ll x,ll y) { if (x <= l && r <= y) return e[o]; pushdown(o); ll mid = (l + r) >> 1; if (y <= mid) return query(o * 2,l,mid,x,y); else if (x > mid) return query(o * 2 + 1,mid + 1,r,x,y); else return pushup(query(o * 2,l,mid,x,mid),query(o * 2 + 1,mid + 1,r,mid + 1,y)); } int main() { scanf("%lld",&n); for (ll i = 1; i <= n; i++) scanf("%lld",&a[i]); for (ll i = 1; i < n; i++) b[i] = a[i + 1] - a[i]; n--; build(1,1,n); scanf("%lld",&q); while (q--) { char ch[2]; ll s,t,a,b; scanf("%s",ch); if (ch[0] == 'A') { scanf("%lld%lld%lld%lld",&s,&t,&a,&b); if (s != 1) update1(1,1,n,s - 1,a); if (t != n + 1) update1(1,1,n,t,-1 * ((t - s) * b + a)); if (s <= t - 1) update2(1,1,n,s,t - 1,b); } else { scanf("%lld%lld",&s,&t); if (s == t) { printf("1 "); continue; } node temp = query(1,1,n,s,t - 1); ll res = (t - s + 2) / 2; if (temp.sum == 0) printf("%lld ",res); else { res = min(res,temp.sum + (temp.lsize + 1) / 2 + (temp.rsize + 1) / 2); printf("%lld ",res); } } } return 0; }