正文
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-;
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 = ;while(!isdigit(c)) c = getchar();
while(isdigit(c)) { x = x * + c - ''; c = getchar(); }
} const int maxn=+;
struct Seg { LL sum,f,MAX,MIN; }s[*maxn];
int T,n,m; void pushUp(int rt)
{
s[rt].sum=s[*rt].sum+s[*rt+].sum;
s[rt].MAX=max(s[*rt].MAX,s[*rt+].MAX);
s[rt].MIN=min(s[*rt].MIN,s[*rt+].MIN);
} void pushDown(int l,int r,int rt)
{
if(s[rt].MIN==s[rt].MAX)
{
s[*rt].MIN=s[*rt+].MIN=s[rt].MIN;
s[*rt].MAX=s[*rt+].MAX=s[rt].MAX; int fz=(l+r)/-l+;
s[*rt].sum=(LL)fz*s[rt].MIN;
s[*rt+].sum=s[rt].sum-s[*rt].sum;
s[rt].f=s[*rt].f=s[*rt+].f=;
return;
} if(s[rt].MIN==s[rt].MAX-)
{
int Tmin=min(s[*rt].MIN,s[*rt+].MIN),Tmax=max(s[*rt].MAX,s[*rt+].MAX); int len,x1,x2;
if(s[*rt].MIN==s[*rt].MAX)
{
if(s[*rt].MIN==Tmin) s[*rt].MIN=s[*rt].MAX=s[rt].MIN;
else s[*rt].MIN=s[*rt].MAX=s[rt].MAX;
s[*rt].sum=(LL)((l+r)/-l+)*s[*rt].MIN;
}
else
{
len=(l+r)/-l+;
x1=(s[*rt].sum-s[*rt].MAX*(LL)len)/(s[*rt].MIN-s[*rt].MAX); x2=len-x1;
s[*rt].MAX=s[rt].MAX; s[*rt].MIN=s[rt].MIN;
s[*rt].sum=(LL)x1*s[*rt].MIN+(LL)x2*s[*rt].MAX;
} if(s[*rt+].MIN==s[*rt+].MAX)
{
if(s[*rt+].MIN==Tmin) s[*rt+].MIN=s[*rt+].MAX=s[rt].MIN;
else s[*rt+].MIN=s[*rt+].MAX=s[rt].MAX;
s[*rt+].sum=(r-(l+r)/)*s[*rt+].MIN;
}
else
{
len=r-(l+r)/;
x1=(s[*rt+].sum-s[*rt+].MAX*(LL)len)/(s[*rt+].MIN-s[*rt+].MAX); x2=len-x1;
s[*rt+].MAX=s[rt].MAX; s[*rt+].MIN=s[rt].MIN;
s[*rt+].sum=(LL)x1*s[*rt+].MIN+(LL)x2*s[*rt+].MAX;
}
s[rt].f=s[*rt].f=s[*rt+].f=;
return;
} if(s[rt].f==) return; s[*rt].f=s[*rt].f+s[rt].f;
s[*rt+].f=s[*rt+].f+s[rt].f; s[*rt].MAX=s[*rt].MAX+s[rt].f;
s[*rt+].MAX=s[*rt+].MAX+s[rt].f; s[*rt].MIN=s[*rt].MIN+s[rt].f;
s[*rt+].MIN=s[*rt+].MIN+s[rt].f; int m=(l+r)/;
s[*rt].sum=s[*rt].sum+(LL)(m-l+)*s[rt].f;
s[*rt+].sum=s[*rt+].sum+(LL)(r-m)*s[rt].f; s[rt].f=;
} void build(int l,int r,int rt)
{
s[rt].f=; s[rt].MAX=; s[rt].MIN=; s[rt].sum=;
if(l==r)
{
read(s[rt].sum);
s[rt].f=; s[rt].MAX=s[rt].sum; s[rt].MIN=s[rt].sum;
return;
}
int m=(l+r)/;
build(l,m,*rt);
build(m+,r,*rt+);
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+)*(LL)x;
return;
}
pushDown(l,r,rt);
int m=(l+r)/;
if(L<=m) add(L,R,x,l,m,*rt);
if(R>m) add(L,R,x,m+,r,*rt+);
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)/; LL x1=,x2=;
if(L<=m) x1=quary(L,R,l,m,*rt);
if(R>m) x2=quary(L,R,m+,r,*rt+);
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+)*s[rt].MIN;
return;
} if(s[rt].MIN==s[rt].MAX-)
{
int len=r-l+;
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)/;
if(s[*rt].MAX!=) force(l,m,*rt);
if(s[*rt+].MAX!=) force(m+,r,*rt+);
pushUp(rt);
} void update(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) { if(s[rt].MAX==) return; force(l,r,rt); return; }
pushDown(l,r,rt);
int m=(l+r)/;
if(L<=m&&s[*rt].MAX!=) update(L,R,l,m,*rt);
if(R>m&&s[*rt+].MAX!=) update(L,R,m+,r,*rt+);
pushUp(rt);
} int main()
{
scanf("%d",&T); while(T--)
{
read(n); read(m); build(,n,);
for(int i=;i<=m;i++)
{
int op,L,R,x;
read(op); read(L); read(R);
if(op==) { read(x); add(L,R,x,,n,); }
else if(op==) update(L,R,,n,);
else if(op==) printf("%lld\n",quary(L,R,,n,));
}
}
return ;
}
