HDU 5306 Gorgeous Sequence 線(xiàn)段樹(shù)

2019-11-14 12:34:59

字體：大中小

供稿：網(wǎng)友

Gorgeous Sequence

讀完題，可以知道顯然要維護(hù)最大值和區(qū)間和，可以用線(xiàn)段樹(shù)。寫(xiě)著寫(xiě)著感覺(jué)第一種操作好像不能延遲更新，然后就不會(huì)了。。。查題解的時(shí)候發(fā)現(xiàn)都是線(xiàn)段樹(shù)，不過(guò)各有各的做法，后來(lái)有一種說(shuō)是吉如一論文中介紹的，可以證明每次操作均攤復(fù)雜度為 O(logN) $O(logN)$ 。這個(gè)論文的標(biāo)題我倒是找到了（吉如一 -《區(qū)間最值操作與歷史最值問(wèn)題》）然而論文沒(méi)找到。。。做法如下：線(xiàn)段樹(shù)的每個(gè)節(jié)點(diǎn)記錄最大值a，次大值b，區(qū)間和sum，以及最大值個(gè)數(shù)cnt。當(dāng)進(jìn)行第一種操作時(shí)，

如果當(dāng)前節(jié)點(diǎn)有 a≤t $a /leq t$ ，則直接退出。這個(gè)很好理解，即區(qū)間內(nèi)所有數(shù)都不變。如果當(dāng)前節(jié)點(diǎn)有 b<t $b /lt t$ ，則先利用 a $a$ 和 cnt $cnt$ 更新sum $sum$ 再更新 a $a$ 后退出。這里要注意的是絕對(duì)不能加等號(hào)！若 b=t $b=t$ 也是如此退出，則之后的次大值和最大值個(gè)數(shù)都不準(zhǔn)確【沒(méi)錯(cuò)我就是因?yàn)檫@個(gè)WA了幾次 ←_←直接往下遞歸

第二種第三種為線(xiàn)段樹(shù)常規(guī)的操作，不表。期間還發(fā)生一件事，找了一份3k+的代碼邊抄邊理解然后調(diào)了半天終于A了，結(jié)果又找到一份代碼，感覺(jué)非常好懂而且只有2k+，于是又照著這個(gè)寫(xiě)了一遍。。。可見(jiàn)理思路是多么的重要。。。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> PII;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define ls rt<<1#define rs rt<<1|1const int maxn = 1000000;struct Seg { ll sum; int a,b,cnt; void spfy(int t) { if (a<=t) return; sum-=(ll)(a-t)*cnt; a=t; }} s[maxn<<2];void push_up(int rt){ s[rt].sum=s[ls].sum+s[rs].sum; s[rt].a=max(s[ls].a,s[rs].a); s[rt].b=max(s[ls].b,s[rs].b); s[rt].cnt=0; if (s[ls].a==s[rt].a) s[rt].cnt+=s[ls].cnt; else s[rt].b=max(s[rt].b,s[ls].a); if (s[rs].a==s[rt].a) s[rt].cnt+=s[rs].cnt; else s[rt].b=max(s[rt].b,s[rs].a);}void push_down(int rt){ s[ls].spfy(s[rt].a); s[rs].spfy(s[rt].a);}void build(int l,int r,int rt){ if (l==r) { scanf("%d",&s[rt].a); s[rt].sum=s[rt].a; s[rt].b=-1; s[rt].cnt=1; return; } int m=(l+r)>>1; build(lson); build(rson); push_up(rt);}void update(int L,int R,int t,int l,int r,int rt){ if (s[rt].a<=t) return; if (L<=l&&r<=R&&s[rt].b<t) {/* Do not add '=' !!! if s[rt].b == t, it supposed to be push_down, because s[rt].b, s[rt].cnt cannot be determined. */ s[rt].spfy(t); return; } push_down(rt); int m=(l+r)>>1; if (L<=m&&s[ls].a>t) update(L,R,t,lson); if (R>m&&s[rs].a>t) update(L,R,t,rson); push_up(rt);}int getmax(int L,int R,int l,int r,int rt){ if (L<=l&&r<=R) return s[rt].a; int m=(l+r)>>1; int res=0; push_down(rt); if (L<=m) res=max(res,getmax(L,R,lson)); if (m<R) res=max(res,getmax(L,R,rson)); return res;}ll getsum(int L,int R,int l,int r,int rt){ if (L<=l&&r<=R) return s[rt].sum; int m=(l+r)>>1; ll res=0; push_down(rt); if (L<=m) res+=getsum(L,R,lson); if (m<R) res+=getsum(L,R,rson); return res;}int main(){ int T,n,m; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); build(1,n,1); while (m--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if (op==0) { int t; scanf("%d",&t); update(x,y,t,1,n,1); } else if (op==1) {