BZOJ 1500 Luogu P2042 [NOI2005] 維護數列 (Splay)
手動博客搬家: 本文發表于20180825 00:34:49, 原地址https://blog.csdn.net/suncongbo/article/details/82027387
題目鏈接: (luogu) https://www.luogu.org/problem/show?pid=2042
(bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=1500
思路分析:
這個題嘛。。思路沒啥好說的
用splay每個點維護四個量：\(sum[0..3]\), \(sum[3]\)表示splay整個子樹代表的區間內元素之和；\(sum[1]\)和\(sum[2]\)分別表示這個區間內以左、右端點開始的元素最大和；\(sum[0]\)表示這個區間內(不限端點)的最大子段和。
比如：序列是
a: 1 -4 -2 9 -5 -7 -999 666 -999 3 0
sum[3]=1+(-4)+(-2)+8+(-5)+(-7)+(-999)+666+(-999)+3+0=-1338
sum[2]=3+0=3
sum[1]=1+(-4)+(-2)+9=4
sum[0]=666=666
區間合并的話，我們可以先想想線段樹怎么合并兩段區間，分類討論即可。平衡樹由于根節點上還有值，因此合并兩段區間+一個值，稍微麻煩點。(這部分略去，不會的可以去做bzoj 1756)
然后就可以開心地碼啦！
部分易錯點
由于所有插入的元素可能達到\(4\times 10^6\)個, 如果建這么多個splay節點，每一個開\(int\)數組記錄，則每個節點維護每個值就會花\(16MB\)空間，然而空間限制\(128MB\), 也就是我們至多維護\(7\)個量。(什么你說8個??你\(128MB\)空間全開了這一個數組，多開一個字節就MLE了啊)而至少我沒有想出用每個節點\(7\)個量維護的方法。貌似開\(fa, son[2], sum[4], tag\)就已經\(8\)個了啊..
解決辦法: 手寫內存回收池, 對于已經刪除的節點，把它\(clear\)掉并把編號放到一個內存回收池中，insert時先從內存回收池中取出一個編號來用，如果內存回收池為空再開新節點。這樣可以保證平衡樹的大小約等于當前序列的大小，因此開\(5\times 10^5\)即可。由于插入的次數雖然少，但是插入的元素總數是很多的 (一次插入多個)。如果一個一個地插，會導致每次都要\(O(\log n*tot)\), 還帶著splay這么大的常數，\(4\times 10^6\)的規模顯然是無法承受的。
解決辦法：先在\(O(tot)\)的時間內把加入的那\(tot\)個節點建出一棵新的完全BST，然后把\(posi\) splay到根, \(posi+1\) splay到根的右兒子，此時根的右兒子的左兒子為空，把新的平衡樹掛到根的右兒子的左兒子上即可。同時注意內存回收池的使用。刪除也是類似。刪除的時候，首先把刪除的節點一起放到根的右兒子的左兒子上，然后\(O(tot)\)地遍歷這棵子樹，把里面的節點\(clear\)掉并放入內存回收池。有個地方題面說的不明白: \(MAX-SUM\)操作選出來的子列要非空。
因此碰到了全是負數的整個序列，答案應該是絕對值最小的那個，而不是\(0\).
解決辦法: 首先，正常節點的\(sum[0..3], val, tag\)都要設成\(-INF\)而不是\(0\). 根據splay常識，對區間\([l,r]\)單獨拎出來進行操作時我們先把\(l-1\) splay到根，再把\(r+1\) splay到根的右兒子。因此為了避免\(l-1\)和\(r+1\)合法，我們可以把要處理的區間平移一位變成\([2,n+1]\), 而\(1\)號點和\((n+2)\)號點作為緩沖點。如果這兩個點的\(sum[0..3], val, tag\)不慎設成了0, 則也會導致\(MAX-SUM\)無法處理答案為負(因為程序自動默認兩個緩沖點是和最大的子列)。因此無論是正常點還是緩沖點都應該初值賦為\(-INF\). (否則洛谷\(90\)分)本題有個極坑之處，\(GET-SUM\)操作的\(tot\)可能為\(0\)!
解決辦法: 特判 (否則洛谷\(80\)分)
前四條是客觀吐槽，后幾條就是我自己犯的若干sb問題了
######大概是寫出了鍋*7, 我好菜啊建樹時沒有分清原數組中的下標和\(splay\)中的編號。
詳見代碼。build函數中的mid是原數組，pos是節點編號，而cfa，是父親節點在原數組中的編號。(有點亂。。)在\(REVERSE\)操作之后沒有交換\(sum[1]\)和\(sum[2]\)并\(pushup\).
由于我們維護的是最大子段和，如果左右子節點被交換，那么\(sum[1]\)和\(sum[2]\)也隨之交換。(可以認為節點的加法，即區間合并，不滿足交換律)因此在\(REVERSE\)打標記的同時應當交換兩個兒子以及該節點的\(sum[1]\)和\(sum[2]\), 并\(pushup\).同時，在pushdown時如果有\(reverse\)標記，也要交換當前節點的\(sum[1]\)和\(sum[2]\)為了偷懶減少代碼長度，\(sum[0]\)的合并少考慮了一種情況。(原地爆炸...以后再也不偷懶了嗚嗚嗚)
好吧再多也沒得說了，反正這道題盡管很毒瘤，但也是練習Splay的一道經典碼農題，以后一定一定要抽空多寫幾遍！
怎么跑得這么慢啊...luogu不開O2要排后100了，bzoj開O2, 2137人AC我排1300多嗚嗚嗚
代碼實現
(luogu: 4399 ms without O2; bzoj: 5912 ms)
#include<cstdio>
#include<algorithm>
#include<cstring>
#define llong long long
using namespace std;const int SZ = 5e5;
const int N = 4e6;
const int INF = 6e8;
struct SplayNode
{int fa,son[2],tag,sum[4],sz,val;bool rev;SplayNode() {fa = son[0] = son[1] = rev = val = sz = 0; tag = sum[0] = sum[1] = sum[2] = sum[3] = -INF;}void clear() {fa = son[0] = son[1] = rev = val = sz = 0; tag = sum[0] = sum[1] = sum[2] = sum[3] = -INF;}
} spl[SZ+4],tmp[SZ+4];
int ids[N+4];
int id[SZ+4];
int a[SZ+4];
char opt[14];
int n,q,siz,rtn,tp;int newnode()
{if(tp>0) {int ret = ids[tp]; ids[tp] = 0; tp--; return ret;}else {siz++; return siz;}
}void pushup(int pos) //這里有簡化很多的寫法，推薦看洛谷題解
{if(pos==0) return;int ls = spl[pos].son[0],rs = spl[pos].son[1];if(ls==0 && rs==0) {spl[pos].sz = 1; spl[pos].sum[0] = spl[pos].sum[1] = spl[pos].sum[2] = spl[pos].sum[3] = spl[pos].val; return;}if(ls==0 && rs!=0){spl[pos].sz = spl[rs].sz+1;spl[pos].sum[3] = spl[rs].sum[3]+spl[pos].val;spl[pos].sum[2] = max(spl[pos].sum[3],spl[rs].sum[2]);spl[pos].sum[1] = max(spl[pos].sum[3],max(spl[pos].val,spl[pos].val+spl[rs].sum[1]));spl[pos].sum[0] = max(max(spl[pos].sum[1],spl[pos].sum[2]),spl[rs].sum[0]);return;}if(ls!=0 && rs==0){spl[pos].sz = spl[ls].sz+1;spl[pos].sum[3] = spl[ls].sum[3]+spl[pos].val;spl[pos].sum[2] = max(spl[pos].sum[3],max(spl[pos].val,spl[pos].val+spl[ls].sum[2]));spl[pos].sum[1] = max(spl[pos].sum[3],spl[ls].sum[1]);spl[pos].sum[0] = max(max(spl[pos].sum[1],spl[pos].sum[2]),spl[ls].sum[0]);return;}spl[pos].sz = spl[ls].sz+spl[rs].sz+1;spl[pos].sum[3] = spl[ls].sum[3]+spl[pos].val+spl[rs].sum[3];spl[pos].sum[2] = max(max(spl[pos].sum[3],spl[rs].sum[2]),spl[rs].sum[3]+spl[pos].val+(spl[ls].sum[2]>0 ? spl[ls].sum[2] : 0));spl[pos].sum[1] = max(max(spl[pos].sum[3],spl[ls].sum[1]),spl[ls].sum[3]+spl[pos].val+(spl[rs].sum[1]>0 ? spl[rs].sum[1] : 0));spl[pos].sum[0] = max(max(max(spl[pos].sum[1],spl[pos].sum[2]),max(spl[ls].sum[0],spl[rs].sum[0])),max(max(spl[pos].val,spl[ls].sum[2]+spl[pos].val+spl[rs].sum[1]),max(spl[pos].val+spl[ls].sum[2],spl[pos].val+spl[rs].sum[1])));
}void pushdown(int pos)
{if(pos==0) return;int ls = spl[pos].son[0],rs = spl[pos].son[1];if(ls==0 && rs==0) {spl[pos].tag = -INF; spl[pos].rev = 0; return;}if(spl[pos].tag>-INF){if(ls!=0){spl[ls].tag = spl[pos].tag; spl[ls].val = spl[ls].tag;spl[ls].sum[3] = spl[ls].tag*spl[ls].sz;spl[ls].sum[0] = spl[ls].sum[1] = spl[ls].sum[2] = spl[ls].tag>0 ? spl[ls].tag*spl[ls].sz : spl[ls].tag;}if(rs!=0){spl[rs].tag = spl[pos].tag; spl[rs].val = spl[rs].tag;spl[rs].sum[3] = spl[rs].tag*spl[rs].sz;spl[rs].sum[0] = spl[rs].sum[1] = spl[rs].sum[2] = spl[rs].tag>0 ? spl[rs].tag*spl[rs].sz : spl[rs].tag;}spl[pos].tag = -INF;}if(spl[pos].rev==true){if(ls!=0) {spl[ls].rev ^= 1; swap(spl[ls].son[0],spl[ls].son[1]); swap(spl[ls].sum[1],spl[ls].sum[2]);}if(rs!=0) {spl[rs].rev ^= 1; swap(spl[rs].son[0],spl[rs].son[1]); swap(spl[rs].sum[1],spl[rs].sum[2]);}spl[pos].rev = 0;}
}void rotate(int x,bool dir)
{int y = spl[x].fa,z = spl[y].fa;pushdown(z); pushdown(y); pushdown(x);spl[x].fa = z;if(z>0){if(spl[z].son[0]==y) spl[z].son[0] = x;else spl[z].son[1] = x;}spl[y].son[dir^1] = spl[x].son[dir];if(spl[x].son[dir]>0) spl[spl[x].son[dir]].fa = y;spl[x].son[dir] = y; spl[y].fa = x;pushup(y); pushup(x); pushup(z);
}void splaynode(int x,int dest)
{while(spl[x].fa!=dest){int y = spl[x].fa,z = spl[y].fa;if(z==dest){if(spl[y].son[0]==x) rotate(x,1);else rotate(x,0);}else if(spl[z].son[0]==y){if(spl[y].son[0]==x) {rotate(y,1); rotate(x,1);}else {rotate(x,0); rotate(x,1);}}else{if(spl[y].son[0]==x) {rotate(x,1); rotate(x,0);}else {rotate(y,0); rotate(x,0);}}}if(dest==0) rtn = x;
}int ranktopos(int th)
{int pos = rtn;while(pos){pushdown(pos);if(th<=spl[spl[pos].son[0]].sz) pos = spl[pos].son[0];else if(th==spl[spl[pos].son[0]].sz+1) {splaynode(pos,0); return pos;}else {th -= spl[spl[pos].son[0]].sz+1; pos = spl[pos].son[1];}}return 0;
}void build(int lb,int rb,int cfa)
{if(lb>rb) return;int mid = (lb+rb)>>1; int pos = newnode(); id[mid] = pos;spl[pos].val = spl[pos].sum[0] = spl[pos].sum[1] = spl[pos].sum[2] = spl[pos].sum[3] = a[mid];spl[pos].fa = id[cfa];if(cfa>mid) spl[id[cfa]].son[0] = pos;else spl[id[cfa]].son[1] = pos;if(lb==rb) {spl[pos].sz = 1; return;}build(lb,mid-1,mid); build(mid+1,rb,mid);pushup(pos);
}void inserttree(int x,int tot)
{int posx = ranktopos(x),posy = ranktopos(x+1);splaynode(posx,0); splaynode(posy,posx);int mid = (1+tot)>>1; int pos = id[mid];spl[posy].son[0] = pos; spl[pos].fa = posy;pushup(posy); pushup(posx);
}void deletenode(int pos)
{if(spl[pos].son[0]) deletenode(spl[pos].son[0]);if(spl[pos].son[1]) deletenode(spl[pos].son[1]);tp++; ids[tp] = pos;spl[pos].clear();
}void deletetree(int lb,int rb)
{int posl = ranktopos(lb-1),posr = ranktopos(rb+1);splaynode(posl,0); splaynode(posr,posl);int pos = spl[posr].son[0];deletenode(pos);spl[posr].son[0] = 0;pushup(posr); pushup(posl);
}void cover(int lb,int rb,int val)
{int posl = ranktopos(lb-1),posr = ranktopos(rb+1);splaynode(posl,0); splaynode(posr,posl);int pos = spl[posr].son[0];spl[pos].tag = val; spl[pos].val = val;spl[pos].sum[3] = val*spl[pos].sz;spl[pos].sum[1] = spl[pos].sum[2] = spl[pos].sum[0] = val>0 ? val*spl[pos].sz : val;pushup(posr); pushup(posl);
}void revint(int lb,int rb)
{int posl = ranktopos(lb-1),posr = ranktopos(rb+1);splaynode(posl,0); splaynode(posr,posl);int pos = spl[posr].son[0];spl[pos].rev ^= 1; swap(spl[pos].son[0],spl[pos].son[1]); swap(spl[pos].sum[1],spl[pos].sum[2]);pushup(posr); pushup(posl);
}int querysum(int lb,int rb)
{if(rb-lb<0) return 0;int posl = ranktopos(lb-1),posr = ranktopos(rb+1);splaynode(posl,0); splaynode(posr,posl);int pos = spl[posr].son[0];return spl[pos].sum[3];
}int maxsum()
{return spl[rtn].sum[0];
}int main()
{scanf("%d%d",&n,&q);for(int i=2; i<=n+1; i++) scanf("%d",&a[i]);a[1] = a[n+2] = -INF;build(1,n+2,0); rtn = id[(n+3)>>1];memset(id,0,sizeof(id));for(int i=1; i<=q; i++){scanf("%s",opt);if(opt[0]=='I'){int x,tot; scanf("%d%d",&x,&tot);for(int j=1; j<=tot; j++) {scanf("%d",&a[j]); id[j] = 0;}build(1,tot,0);inserttree(x+1,tot);}else if(opt[0]=='D'){int x,tot; scanf("%d%d",&x,&tot);deletetree(x+1,x+tot);}else if(opt[0]=='M' && opt[2]=='K'){int x,tot,y; scanf("%d%d%d",&x,&tot,&y);cover(x+1,x+tot,y);}else if(opt[0]=='R'){int x,tot; scanf("%d%d",&x,&tot);revint(x+1,x+tot);}else if(opt[0]=='G'){int x,tot; scanf("%d%d",&x,&tot);printf("%d\n",querysum(x+1,x+tot));}else if(opt[0]=='M' && opt[2]=='X'){printf("%d\n",maxsum());}}return 0;
} 發表于
2019-01-22 19:41 suncongbo 閱讀(
...) 評論() 編輯 收藏
刷新評論刷新頁面返回頂部
總結
以上是生活随笔為你收集整理的BZOJ 1500 Luogu P2042 [NOI2005] 维护数列 (Splay)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
