描述

要求支持區間插入、區間修改、區間翻轉、區間刪除、區間求和 和求和最大的子列.

分析

• 從最開始學完splay做了翻轉區間后就想做這個題目, 結果WA了N次后失去調試的信心, 40分收場(這題暴力30分)
• 快省選了想拿出來再做一下, 因為splay的區間操作這個題算是最全的了, 不做一下的話總擔心模版是錯的.
• 然后做了好長時間...終于不耐煩了拿HZWER的改了改, 直到改到所有操作和我的都寫的一模一樣——除了標記下傳. 然后就很開(傷)心地接受了這個現實.
• 在網上看每個人寫的標記下傳都不一樣, 有的寫的簡單有的很復雜(比如HZWER). 但一種標記下傳對應一種維護方式吧, 看網上很少有寫如何處理細節的, 我就寫詳細點吧.

• 首先, mls, mrs, maxs分別記錄左、右端開始的最大子序列和, 和整段區間的最大子序列和.
• 規定如果整段區間為負值, mls和mrs可以取0, 而maxs必須取一個存在的數, 這樣也是為了維護起來方便吧.
• 那么mls可以取左子結點的mls、左子結點的sum+根結點的權值+右子結點的mls. mrs同理.
• maxs可以取左子結點的maxs、右子結點的maxs、左子結點的mrs+根結點權值+右子結點的mls.
• 這就是mls、mrs最小為0的優勢.
• 在標記下傳時下傳的實際上是子結點的標記, 而根結點的標記實際上已經在此之前生效了. 這樣可以避免在旋轉時出錯. 旋轉里的那個 ch[p][d] 的標記可能沒有生效.
• 遇到帶區間修改的題目都要用這種標記下傳的方式吧..
• 又想起原來寫過的區間翻轉類的題目, 那里的標記下傳只需要下傳當前節點的即可, 那是因為翻轉不影響最大值、不影響求和. 而區間修改會影響.

#include #include using namespace std;const int INF = 0x3f3f3f3f; const int maxn = 3000000;int n, m; int fa[maxn], ch[maxn][2], id[maxn]; int mls[maxn], mrs[maxn], maxs[maxn], s[maxn], rech[maxn], v[maxn], sumv[maxn]; bool mdf[maxn], rev[maxn];#define lc ch[o][0] #define rc ch[o][1]void update(int o) {s[o] = s[lc] + s[rc] + 1;sumv[o] = sumv[lc] + sumv[rc] + v[o];maxs[o] = max(maxs[lc], maxs[rc]);maxs[o] = max(maxs[o], mrs[lc] + v[o] + mls[rc]);mls[o] = max(mls[lc], sumv[lc] + v[o] + mls[rc]);mrs[o] = max(mrs[rc], sumv[rc] + v[o] + mrs[lc]); }void pushdown(int o) {if(mdf[o]) {mdf[o] = rev[o] = 0;if(lc) mdf[lc] = 1, v[lc] = v[o], sumv[lc] = v[o]*s[lc];if(rc) mdf[rc] = 1, v[rc] = v[o], sumv[rc] = v[o]*s[rc];if(v[o] >= 0) {if(lc) mls[lc] = mrs[lc] = maxs[lc] = sumv[lc];if(rc) mls[rc] = mrs[rc] = maxs[rc] = sumv[rc];} else {if(lc) mls[lc] = mrs[lc] = 0, maxs[lc] = v[o];if(rc) mls[rc] = mrs[rc] = 0, maxs[rc] = v[o];}}if(rev[o]) {rev[o]^=1;rev[lc]^=1;rev[rc]^=1;swap(mls[lc], mrs[lc]);swap(mls[rc], mrs[rc]);swap(ch[lc][0], ch[lc][1]);swap(ch[rc][0], ch[rc][1]);} }void rotate(int& o, int x) {int p = fa[x], q = fa[p];bool d = (ch[p][1] == x), d2 = (ch[q][1] == p);if(o == p) o = x; else ch[q][d2] = x;fa[x] = q; fa[p] = x; fa[ch[p][d] = ch[x][d^1]] = p;ch[x][d^1] = p; update(p); update(x); }void splay(int& o, int x) {while(o != x) {int p = fa[x], q = fa[p];if(o != p)if(ch[p][0] == x^ch[q][0] == p) rotate(o, x); else rotate(o, p);rotate(o, x);} }void build(int L, int R, int p, int d) {if(L > R) return;int o = (L+R)>>1;ch[p][d] = o; fa[o] = p;build(L, o-1, o, 0);build(o+1, R, o, 1);update(o); }int kth(int o, int k) {pushdown(o);if(s[lc] + 1 == k) return o;else if(s[lc] >= k) return kth(lc, k);else return kth(rc, k-s[lc]-1); }int o, pos, tot, val;void insert() {splay(o, kth(o, pos+1));splay(rc, kth(o, pos+2));for(int i = n+1; i <= n+tot; i++) scanf("%d", &v[i]);build(n+1, n+tot, rc, 0);n += tot; //update(rc); update(o); }void remove() {splay(o, kth(o, pos));splay(rc, kth(o, pos + tot + 1));ch[rc][0] = 0;update(rc); update(o); }void modify() {splay(o, kth(o, pos));splay(rc, kth(o, pos + tot + 1));int p = ch[rc][0];v[p] = val;mdf[p] = 1;sumv[p] = v[p]*s[p];if(val >= 0) mls[p] = mrs[p] = maxs[p] = sumv[p];else mls[p] = mrs[p] = 0, maxs[p] = v[p];update(rc); update(o); }void rever() {splay(o, kth(o, pos));splay(rc, kth(o, pos + tot + 1));if(!mdf[o]) {int p = ch[rc][0];rev[p]^=1;swap(ch[p][0], ch[p][1]);swap(mls[p], mrs[p]);}update(rc); update(o); }void query() {splay(o, kth(o, pos));splay(rc, kth(o, pos + tot + 1));printf("%d\n", sumv[ch[rc][0]]); }int main() {scanf("%d %d", &n, &m); n += 2;v[1] = v[n] = maxs[0] = -INF; //for(int i = 2; i < n; i++) scanf("%d", &v[i]);build(1, n, 0, 0);o = (n+1)>>1;for(int i = 1; i <= m; i++) {char opt[10];scanf("%s", opt);switch(opt[2]) {case 'S': scanf("%d %d", &pos, &tot); insert(); break;case 'L': scanf("%d %d", &pos, &tot); remove(); break;case 'V': scanf("%d %d", &pos, &tot); rever(); break;case 'T': scanf("%d %d", &pos, &tot); query(); break;case 'K': scanf("%d %d %d", &pos, &tot, &val); modify(); break;case 'X': printf("%d\n", maxs[o]);}}return 0; } #include #include using namespace std;const int INF = 0x3f3f3f3f; const int maxn = 3000000;int n, m; int ch[maxn][2], id[maxn]; int mls[maxn], mrs[maxn], maxs[maxn], s[maxn], rech[maxn], v[maxn], sumv[maxn]; bool mdf[maxn], rev[maxn];#define lc ch[o][0] #define rc ch[o][1]void update(int o) {s[o] = s[lc] + s[rc] + 1;sumv[o] = sumv[lc] + sumv[rc] + v[o];maxs[o] = max(maxs[lc], maxs[rc]);maxs[o] = max(maxs[o], mrs[lc] + v[o] + mls[rc]);mls[o] = max(mls[lc], sumv[lc] + v[o] + mls[rc]);mrs[o] = max(mrs[rc], sumv[rc] + v[o] + mrs[lc]); }void pushdown(int o) {if(mdf[o]) {mdf[o] = rev[o] = 0;if(lc) mdf[lc] = 1, v[lc] = v[o], sumv[lc] = v[o]*s[lc];if(rc) mdf[rc] = 1, v[rc] = v[o], sumv[rc] = v[o]*s[rc];if(v[o] >= 0) {if(lc) mls[lc] = mrs[lc] = maxs[lc] = sumv[lc];if(rc) mls[rc] = mrs[rc] = maxs[rc] = sumv[rc];} else {if(lc) mls[lc] = mrs[lc] = 0, maxs[lc] = v[o];if(rc) mls[rc] = mrs[rc] = 0, maxs[rc] = v[o];}}if(rev[o]) {rev[o]^=1;rev[lc]^=1;rev[rc]^=1;swap(mls[lc], mrs[lc]);swap(mls[rc], mrs[rc]);swap(ch[lc][0], ch[lc][1]);swap(ch[rc][0], ch[rc][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; }int cmp(int o, int k) {if(s[lc] + 1 == k) return -1;return k < s[lc] + 1 ? 0 : 1; }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);int k2 = (d2 == 0 ? k : k-s[ch[p][0]]-1);if(d2 != -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); }void getInterval(int& o, int pos, int tot) {splay(o, pos);splay(rc, pos + tot - s[lc]); }int o, pos, tot, val;void insert() {getInterval(o, pos+1, 0);for(int i = n+1; i <= n+tot; i++) scanf("%d", &v[i]);build(ch[rc][0], n+1, n+tot);n += tot; //update(rc); update(o); }void remove() {getInterval(o, pos, tot);ch[rc][0] = 0;update(rc); update(o); }void modify() {getInterval(o, pos, tot);int p = ch[rc][0];v[p] = val;mdf[p] = 1;sumv[p] = v[p]*s[p];if(val >= 0) mls[p] = mrs[p] = maxs[p] = sumv[p];else mls[p] = mrs[p] = 0, maxs[p] = v[p];update(rc); update(o); }void rever() {getInterval(o, pos, tot);if(!mdf[o]) {int p = ch[rc][0];rev[p]^=1;swap(ch[p][0], ch[p][1]);swap(mls[p], mrs[p]);}update(rc); update(o); }void query() {getInterval(o, pos, tot);printf("%d\n", sumv[ch[rc][0]]); }int main() {scanf("%d %d", &n, &m); n += 2;v[1] = v[n] = maxs[0] = -INF; //for(int i = 2; i < n; i++) scanf("%d", &v[i]);build(o, 1, n);for(int i = 1; i <= m; i++) {char opt[10];scanf("%s", opt);switch(opt[2]) {case 'S': scanf("%d %d", &pos, &tot); insert(); break;case 'L': scanf("%d %d", &pos, &tot); remove(); break;case 'V': scanf("%d %d", &pos, &tot); rever(); break;case 'T': scanf("%d %d", &pos, &tot); query(); break;case 'K': scanf("%d %d %d", &pos, &tot, &val); modify(); break;case 'X': printf("%d\n", maxs[o]);}}return 0; }

總結

以上是生活随笔為你收集整理的CODEVS-1758-维护数列-NOI2005-splay的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。