描述

區(qū)間修改, 區(qū)間求和

分析

• 想練練splay打標(biāo)記.

• 因?yàn)閟play不支持永久標(biāo)號(hào), 所以pushdown后必須把標(biāo)記清掉.

• 第一次打上標(biāo)記后要立刻讓標(biāo)記生效.

• 需要注意的地方是pushdown必須讓子結(jié)點(diǎn)的標(biāo)記生效.

#include using namespace std; typedef long long int lli;const int maxn = 200000 + 10;int s[maxn], ch[maxn][2]; lli v[maxn], sumv[maxn], inc[maxn];#define lc ch[o][0] #define rc ch[o][1] #define seq ch[rc][0]void update(int o) {s[o] = s[lc] + s[rc] + 1;sumv[o] = sumv[lc] + sumv[rc] + v[o]; }void pushdown(int o) {if(!inc[o]) return;inc[lc] += inc[o]; v[lc] += inc[o]; sumv[lc] += inc[o] * s[lc];inc[rc] += inc[o]; v[rc] += inc[o]; sumv[rc] += inc[o] * s[rc];inc[o] = 0; }int cmp(int o, int k) {if(s[lc] + 1 == k) return -1;return k < s[lc] + 1 ? 0 : 1; }void rotate(int& o, int d) {int p = ch[o][d^1]; ch[o][d^1] = ch[p][d]; ch[p][d] = o;update(o); update(p); o = p; }void splay(int& o, int k) {pushdown(o);int d = cmp(o, k);if(d == -1) return;if(d == 1) k -= (s[lc] + 1);int p = ch[o][d];pushdown(p);int d2 = cmp(p, k);if(d2 != -1) {int k2 = (d2 == 0 ? k : k-s[ch[p][0]]-1);splay(ch[p][d2], k2);if(d == d2) rotate(o, d^1); else rotate(ch[o][d], d);}rotate(o, d^1); }void build(int& o, int L, int R) {if(L > R) return;o = (L+R)>>1;build(lc, L, o-1); build(rc, o+1, R);update(o); }int main() {int n, m, o;scanf("%d", &n); n += 2;for(int i = 2; i < n; i++) scanf("%d", &v[i]);build(o, 1, n);scanf("%d", &m);for(int i = 0; i < m; i++) {lli x;int k, y1, y2;scanf("%d %d %d", &k, &y1, &y2);y1++; y2++;splay(o, y1-1);splay(rc, y2+1-(s[lc]+1));if(k == 2) printf("%lld\n", sumv[seq]);else {scanf("%lld", &x);inc[seq] += x; v[seq] += x; sumv[seq] += s[seq] * x;update(rc); update(o);}}return 0; } #include using namespace std; typedef long long lli;const int maxn = 600000;lli y1, y2, v; lli addv[maxn]; lli sumv[maxn];#define lc (o<<1) #define rc (o<<1^1) #define M (L+R>>1)void build(int o, int L, int R) {if(L == R) scanf("%lld", &sumv[o]);else {build(lc, L, M);build(rc, M+1, R);sumv[o] = sumv[lc] + sumv[rc];} }void update(int o, int L, int R) {if(y1 <= L && y2 >= R) {addv[o] += v;sumv[o] += v*(R-L+1);} else {if(y1 <= M) update(lc, L, M);if(y2 > M) update(rc, M+1, R);sumv[o] = sumv[lc] + sumv[rc] + addv[o] * (R-L+1);} }lli sum_v; void query(int o, int L, int R, lli add) {if(y1 <= L && R <= y2) sum_v += sumv[o] + add*(R-L+1);else {if(y1 <= M) query(lc, L, M, add + addv[o]);if(y2 > M) query(rc, M+1, R, add + addv[o]);} }int main() {int n, m;scanf("%d", &n);build(1, 1, n);scanf("%d", &m);for(int i = 1; i <= m; i++) {int k;scanf("%d", &k);if(k == 1) {scanf("%lld%lld%lld", &y1, &y2, &v);update(1, 1, n);} else {scanf("%lld%lld", &y1, &y2);sum_v = 0;query(1, 1, n, 0);printf("%lld\n", sum_v);}}return 0; } #includeusing namespace std; typedef long long lli;const int maxn = 200000 + 10; lli n, c1[maxn], c2[maxn], s[maxn];lli query(int x, lli* c) {lli ret = 0;for(; x > 0; x += x&-x) ret += c[x];return ret; }void modify(int x, int d, lli* c) {for(; x <= n; x += x&-x) c[x] += d; }int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%lld", &s[i]);s[i] += s[i-1];}int m, k, d, L, R;scanf("%d", &m);for(int i = 1; i <= m; i++) {scanf("%d", &k);if(k == 1) {scanf("%d%d%d", &L, &R, &d);modify(L, d, c1);modify(R+1, -d, c1);modify(L, L*d, c2);modify(R+1, -(R+1)*d, c2);} else {scanf("%d%d", &L, &R);lli s1 = s[R]-s[L-1];lli s2 = query(R,c1)*(R+1) - query(L-1,c1)*L;lli s3 = query(L-1,c2) - query(R,c2);printf("%lld\n", s1 + s2 + s3);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CODEVS-1082-线段树练习3-splay的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。