首页 > 代码库 > HDU 5828 Rikka with Sequence
HDU 5828 Rikka with Sequence
好久没写线段树了，这题作为一个回味..
第一种操作的话，就是一个延迟标记。
第二种操作可以暴力更新下去，但是有一个优化，如果某区间内所有值都是一样的，或者最大值和最小值相差1，那么到此结束，不要继续往下面更新了。
这样一来的话，pushDown的时候要注意一下，如果该区间内所有值都一样，或者最大值和最小值相差1，那么延迟标记不要往下扔了，直接把该区间的信息传下去。如果该区间内所有值不一样，将延迟标记扔下去。
总体难度不算大，仔细一些就能AC。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const int maxn=100000+10;struct Seg { LL sum,f,MAX,MIN; }s[4*maxn];int T,n,m;void pushUp(int rt){ s[rt].sum=s[2*rt].sum+s[2*rt+1].sum; s[rt].MAX=max(s[2*rt].MAX,s[2*rt+1].MAX); s[rt].MIN=min(s[2*rt].MIN,s[2*rt+1].MIN);}void pushDown(int l,int r,int rt){ if(s[rt].MIN==s[rt].MAX) { s[2*rt].MIN=s[2*rt+1].MIN=s[rt].MIN; s[2*rt].MAX=s[2*rt+1].MAX=s[rt].MAX; int fz=(l+r)/2-l+1; s[2*rt].sum=(LL)fz*s[rt].MIN; s[2*rt+1].sum=s[rt].sum-s[2*rt].sum; s[rt].f=s[2*rt].f=s[2*rt+1].f=0; return; } if(s[rt].MIN==s[rt].MAX-1) { int Tmin=min(s[2*rt].MIN,s[2*rt+1].MIN),Tmax=max(s[2*rt].MAX,s[2*rt+1].MAX); int len,x1,x2; if(s[2*rt].MIN==s[2*rt].MAX) { if(s[2*rt].MIN==Tmin) s[2*rt].MIN=s[2*rt].MAX=s[rt].MIN; else s[2*rt].MIN=s[2*rt].MAX=s[rt].MAX; s[2*rt].sum=(LL)((l+r)/2-l+1)*s[2*rt].MIN; } else { len=(l+r)/2-l+1; x1=(s[2*rt].sum-s[2*rt].MAX*(LL)len)/(s[2*rt].MIN-s[2*rt].MAX); x2=len-x1; s[2*rt].MAX=s[rt].MAX; s[2*rt].MIN=s[rt].MIN; s[2*rt].sum=(LL)x1*s[2*rt].MIN+(LL)x2*s[2*rt].MAX; } if(s[2*rt+1].MIN==s[2*rt+1].MAX) { if(s[2*rt+1].MIN==Tmin) s[2*rt+1].MIN=s[2*rt+1].MAX=s[rt].MIN; else s[2*rt+1].MIN=s[2*rt+1].MAX=s[rt].MAX; s[2*rt+1].sum=(r-(l+r)/2)*s[2*rt+1].MIN; } else { len=r-(l+r)/2; x1=(s[2*rt+1].sum-s[2*rt+1].MAX*(LL)len)/(s[2*rt+1].MIN-s[2*rt+1].MAX); x2=len-x1; s[2*rt+1].MAX=s[rt].MAX; s[2*rt+1].MIN=s[rt].MIN; s[2*rt+1].sum=(LL)x1*s[2*rt+1].MIN+(LL)x2*s[2*rt+1].MAX; } s[rt].f=s[2*rt].f=s[2*rt+1].f=0; return; } if(s[rt].f==0) return; s[2*rt].f=s[2*rt].f+s[rt].f; s[2*rt+1].f=s[2*rt+1].f+s[rt].f; s[2*rt].MAX=s[2*rt].MAX+s[rt].f; s[2*rt+1].MAX=s[2*rt+1].MAX+s[rt].f; s[2*rt].MIN=s[2*rt].MIN+s[rt].f; s[2*rt+1].MIN=s[2*rt+1].MIN+s[rt].f; int m=(l+r)/2; s[2*rt].sum=s[2*rt].sum+(LL)(m-l+1)*s[rt].f; s[2*rt+1].sum=s[2*rt+1].sum+(LL)(r-m)*s[rt].f; s[rt].f=0;}void build(int l,int r,int rt){ s[rt].f=0; s[rt].MAX=0; s[rt].MIN=0; s[rt].sum=0; if(l==r) { read(s[rt].sum); s[rt].f=0; s[rt].MAX=s[rt].sum; s[rt].MIN=s[rt].sum; return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); pushUp(rt);}void add(int L,int R,int x,int l,int r,int rt){ if(L<=l&&r<=R) { s[rt].f=s[rt].f+x; s[rt].MAX=s[rt].MAX+x; s[rt].MIN=s[rt].MIN+x; s[rt].sum=s[rt].sum+(r-l+1)*(LL)x; return; } pushDown(l,r,rt); int m=(l+r)/2; if(L<=m) add(L,R,x,l,m,2*rt); if(R>m) add(L,R,x,m+1,r,2*rt+1); pushUp(rt);}LL quary(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return s[rt].sum; pushDown(l,r,rt); int m=(l+r)/2; LL x1=0,x2=0; if(L<=m) x1=quary(L,R,l,m,2*rt); if(R>m) x2=quary(L,R,m+1,r,2*rt+1); pushUp(rt); return x1+x2;}void force(int l,int r,int rt){ if(l==r) { s[rt].sum=(LL)sqrt(1.0*s[rt].sum); s[rt].MIN=s[rt].MAX=s[rt].sum; return; } if(s[rt].MIN==s[rt].MAX) { s[rt].MAX=s[rt].MIN=(LL)sqrt(1.0*s[rt].MIN); s[rt].sum=(LL)(r-l+1)*s[rt].MIN; return; } if(s[rt].MIN==s[rt].MAX-1) { int len=r-l+1; int x1=(s[rt].sum-s[rt].MAX*(LL)len)/(s[rt].MIN-s[rt].MAX), x2=len-x1; s[rt].MAX=(LL)sqrt(1.0*s[rt].MAX); s[rt].MIN=(LL)sqrt(1.0*s[rt].MIN); s[rt].sum=(LL)x1*s[rt].MIN+(LL)x2*s[rt].MAX; return; } pushDown(l,r,rt); int m=(l+r)/2; if(s[2*rt].MAX!=1) force(l,m,2*rt); if(s[2*rt+1].MAX!=1) force(m+1,r,2*rt+1); pushUp(rt);}void update(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { if(s[rt].MAX==1) return; force(l,r,rt); return; } pushDown(l,r,rt); int m=(l+r)/2; if(L<=m&&s[2*rt].MAX!=1) update(L,R,l,m,2*rt); if(R>m&&s[2*rt+1].MAX!=1) update(L,R,m+1,r,2*rt+1); pushUp(rt);}int main(){ scanf("%d",&T); while(T--) { read(n); read(m); build(1,n,1); for(int i=1;i<=m;i++) { int op,L,R,x; read(op); read(L); read(R); if(op==1) { read(x); add(L,R,x,1,n,1); } else if(op==2) update(L,R,1,n,1); else if(op==3) printf("%lld\n",quary(L,R,1,n,1)); } } return 0;}
HDU 5828 Rikka with Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。