HDU 5306 Gorgeous Sequence 线段树

2019-11-14 12:01:29

字体：大中小

来源：转载

供稿：网友

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) { PRintf("%d/n",getmax(x,y,1,n,1)); } else { printf("%lld/n",getsum(x,y,1,n,1)); } } } return 0;}

上一篇：Java Quene

下一篇：abp项目之旅