HDU 5306 Gorgeous Sequence 線段樹

2019-11-14 12:34:59

字體：大中小

來源：轉載

供稿：網友

Gorgeous Sequence

讀完題，可以知道顯然要維護最大值和區間和，可以用線段樹。寫著寫著感覺第一種操作好像不能延遲更新，然后就不會了。。。查題解的時候發現都是線段樹，不過各有各的做法，后來有一種說是吉如一論文中介紹的，可以證明每次操作均攤復雜度為 O(logN) $O(logN)$ 。這個論文的標題我倒是找到了（吉如一 -《區間最值操作與歷史最值問題》）然而論文沒找到。。。做法如下：線段樹的每個節點記錄最大值a，次大值b，區間和sum，以及最大值個數cnt。當進行第一種操作時，

如果當前節點有 a≤t $a /leq t$ ，則直接退出。這個很好理解，即區間內所有數都不變。如果當前節點有 b<t $b /lt t$ ，則先利用 a $a$ 和 cnt $cnt$ 更新sum $sum$ 再更新 a $a$ 后退出。這里要注意的是絕對不能加等號！若 b=t $b=t$ 也是如此退出，則之后的次大值和最大值個數都不準確【沒錯我就是因為這個WA了幾次 ←_←直接往下遞歸

第二種第三種為線段樹常規的操作，不表。期間還發生一件事，找了一份3k+的代碼邊抄邊理解然后調了半天終于A了，結果又找到一份代碼，感覺非常好懂而且只有2k+，于是又照著這個寫了一遍。。。可見理思路是多么的重要。。。

#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) {