HZOJ Weed
作者的題解：
如果一段操作被執(zhí)行，會(huì)對整個(gè)棧有什么影響呢？
把棧彈出若干個(gè)數(shù)后再插入若干個(gè)數(shù)。
線段樹：
每個(gè)點(diǎn)紀(jì)錄三個(gè)值：執(zhí)行完這段操作后會(huì)刪多少個(gè)，再插多少個(gè)，插的和一共是多少。
合并值時(shí)再用一個(gè)函數(shù)查找左孩子被從右刪除若干個(gè)后剩下的插入總和是多少。
建樹復(fù)雜度O( N log N ), 單次查詢復(fù)雜度O( log ^ 2 N), 總復(fù)雜度O( N log N + Q log ^2 N ).
樹袋熊學(xué)長的題解：
? 實(shí)際上,每個(gè)加數(shù)和刪除的操作可以看作是入棧和彈棧操作,之后可以用線段樹維護(hù)多個(gè)操作間的關(guān)系。線段樹的下標(biāo)是操作時(shí)間,由于我們想得到整個(gè)序列經(jīng)過修改操作后的結(jié)果,因此線段
樹上維護(hù)四個(gè)信息:
s:區(qū)間內(nèi)加數(shù)總和(僅考慮區(qū)間內(nèi)部影響);
nd:當(dāng)前區(qū)間向前刪除數(shù)字的數(shù)量;
na:當(dāng)前區(qū)間內(nèi)“凈”加的元素?cái)?shù)。
sd:當(dāng)前區(qū)間被右兄弟刪除后的總和。 ※僅對左兒子維護(hù)此信息。
? 我們通過維護(hù)以上四個(gè)標(biāo)記,就可以得到答案(root->s)。現(xiàn)在我們考慮如何維護(hù)信息。
首先,在建樹或修改時(shí),只需要將葉子節(jié)點(diǎn)的前三個(gè)標(biāo)記維護(hù)好即可;在遞歸返回時(shí),再計(jì)算最后一個(gè)。如果左兒子不夠右兒子刪,那么非常簡單,直接利用這幾個(gè)標(biāo)記計(jì)算即可,l->sd=0。
比較麻煩的是左兒子不被刪光的情況。我們先實(shí)現(xiàn)一個(gè)函數(shù)cal(x),利用sd標(biāo)記計(jì)算在當(dāng)前區(qū)間中刪去x個(gè)元素后的和
? 有了這個(gè)函數(shù),我們就可以非常方便地計(jì)算左兒子的sd,維護(hù)其
他標(biāo)記了,不再贅述。
由于這個(gè)奇怪的函數(shù)在每層節(jié)點(diǎn)都會(huì)調(diào)用,而一共有O(logn)層節(jié)點(diǎn),所以線段樹操作的時(shí)間復(fù)雜度變?yōu)镺(log 2 n),總時(shí)間復(fù)雜度也比常規(guī)的線段樹多一個(gè)log。
? 難點(diǎn)主要在于使用額外的函數(shù)維護(hù)信息,并正確的討論各種情況。
? 考試時(shí)一定要想清楚,時(shí)間復(fù)雜度是靠“鏈狀”延伸的維護(hù)函數(shù)保障的,如果不小心寫成了兩邊都下去,就變成O(n 2 )了。
?還是說我自己咋寫的吧，
用線段樹維護(hù)操作（好象是第二次碰到這種題），對于線段樹的每個(gè)節(jié)點(diǎn)，維護(hù)三個(gè)信息，del當(dāng)前節(jié)點(diǎn)刪除其左兄弟幾個(gè)元素，add只考慮當(dāng)前區(qū)間影響區(qū)間內(nèi)的元素個(gè)數(shù)，val只考慮當(dāng)前區(qū)間影響區(qū)間內(nèi)的和。
建樹時(shí)對于葉子節(jié)點(diǎn)就很容易了，直接賦值就行了。下面考慮怎么合并，分三種情況：
cal（k，x）表示k節(jié)點(diǎn)的區(qū)間刪掉結(jié)尾x個(gè)元素后的和：
int cal(int k,int x) {if(x==add(rs(k)))return val(k)-val(rs(k));if(x<add(rs(k))) return val(k)-val(rs(k))+cal(rs(k),x);if(x>add(rs(k))) return cal(ls(k),x-add(rs(k))+del(rs(k))); }?到這里大概就沒什么了。
最后答案為val（1），對于每次修改直接遞歸到對應(yīng)葉子節(jié)點(diǎn)即可。
?
1 #include<iostream> 2 #include<cstdio> 3 #define MAXN 200100 4 #define LL long long 5 using namespace std; 6 struct tree 7 { 8 int l,r,del,add,val; 9 #define l(x) tr[x].l 10 #define r(x) tr[x].r 11 #define del(x) tr[x].del 12 #define add(x) tr[x].add 13 #define val(x) tr[x].val 14 #define ls(x) (x<<1) 15 #define rs(x) (ls(x)+1) 16 }tr[MAXN*10]; 17 int m,q,k[MAXN],v[MAXN]; 18 int cal(int k,int x) 19 { 20 if(x==add(rs(k)))return val(k)-val(rs(k)); 21 if(x<add(rs(k))) return val(k)-val(rs(k))+cal(rs(k),x); 22 if(x>add(rs(k))) return cal(ls(k),x-add(rs(k))+del(rs(k))); 23 } 24 void updata(int x) 25 { 26 if(add(ls(x))==del(rs(x))) 27 { 28 del(x)=del(ls(x));add(x)=add(rs(x));val(x)=val(rs(x)); 29 } 30 if(add(ls(x))<del(rs(x))) 31 { 32 del(x)=del(ls(x))+del(rs(x))-add(ls(x)); 33 add(x)=add(rs(x)); 34 val(x)=val(rs(x)); 35 } 36 if(add(ls(x))>del(rs(x))) 37 { 38 del(x)=del(ls(x)); 39 add(x)=add(rs(x))+add(ls(x))-del(rs(x)); 40 val(x)=val(rs(x))+cal(ls(x),del(rs(x))); 41 } 42 } 43 void build(int x,int l,int r) 44 { 45 l(x)=l,r(x)=r; 46 if(l==r) 47 { 48 if(k[l]==0) del(x)=0,val(x)=v[l],add(x)=1; 49 else del(x)=v[l],val(x)=0,add(x)=0; 50 return; 51 } 52 int mid=(l+r)>>1; 53 build(ls(x),l,mid); 54 build(rs(x),mid+1,r); 55 updata(x); 56 } 57 void change(int x,int t,int k,int v) 58 { 59 if(l(x)==r(x)) 60 { 61 if(k==0)del(x)=0,val(x)=v,add(x)=1; 62 else del(x)=v,val(x)=0,add(x)=0; 63 return; 64 } 65 int mid=(l(x)+r(x))>>1; 66 if(t<=mid)change(ls(x),t,k,v); 67 else change(rs(x),t,k,v); 68 updata(x); 69 } 70 signed main() 71 { 72 /// freopen("weed.in","r",stdin); 73 74 cin>>m>>q; 75 for(int i=1;i<=m;i++) 76 cin>>k[i]>>v[i]; 77 build(1,1,m); 78 int c,kk,vv; 79 for(int i=1;i<=q;i++) 80 { 81 cin>>c>>kk>>vv; 82 change(1,c,kk,vv); 83 cout<<val(1)<<endl; 84 } 85 } View Code?
轉(zhuǎn)載于:https://www.cnblogs.com/Al-Ca/p/11331095.html
總結(jié)
- 上一篇： 改造我们的学习：有钱不会花，抱着金库抓瞎
- 下一篇： HZOJ Drink