zcy的励志故事.jpg
傻逼zcy突然想立一个flag，写一个segment-tree-beats的题娱乐一下
于是他就想起了这道题。
他打算今晚写完
然后光是写他就写的头昏脑涨，还犯了询问写反这种傻逼错误
后来他发现调不出来了
然后调了快2h，写个暴力对拍才发现pushup写的是萎的。
这题其实就是很恶心的吧操作扔在一起
但是还是维护最大值，最大值出现次数，次大值能解决的问题。
标记合并的时候注意讨论下，细节有点多，样例比较彩笔
建议提交之前先测试所有操作或者跟暴力对拍。
#include<bits/stdc++.h>
#define N 600005
#define lson (o<<1)
#define rson (o<<1|1)
#define inf 1<<30
using namespace std;
typedef long long ll;
int n;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
//Segment-Tree-Beats!
int maxv[N<<],seca[N<<],cnta[N<<],minv[N<<],seci[N<<],cnti[N<<],tagv[N<<];
ll sumv[N<<];
inline void pushup(int o){
int l=o<<,r=o<<|;sumv[o]=sumv[l]+sumv[r];
if(maxv[l]==maxv[r])maxv[o]=maxv[l],cnta[o]=cnta[l]+cnta[r],seca[o]=max(seca[l],seca[r]);
else{
if(maxv[l]>maxv[r]) swap(l,r);maxv[o]=maxv[r]; cnta[o]=cnta[r];seca[o]=max(seca[r],maxv[l]);
}
if(minv[l]==minv[r])
minv[o]=minv[l],cnti[o]=cnti[l]+cnti[r],seci[o]=min(seci[l],seci[r]);
else{
if(minv[l]<minv[r]) swap(l,r);minv[o]=minv[r]; cnti[o]=cnti[r];seci[o]=min(seci[r],minv[l]);
}
}
inline void puttag(int o,int l,int r,int v){
tagv[o]+=v;sumv[o]+=(ll)(r-l+)*v;
minv[o]+=v;maxv[o]+=v;seca[o]+=v;seci[o]+=v;
}
inline void tmax(int o,int l,int r,int v){
sumv[o]+=(ll)(cnti[o])*(v-minv[o]);
minv[o]=v;maxv[o]=max(v,maxv[o]);
if(minv[o]==maxv[o]){
sumv[o]=1LL*(r-l+)*v;cnta[o]=cnti[o]=r-l+;seca[o]=-inf;seci[o]=inf;
}else seca[o]=max(v,seca[o]);
}
inline void tmin(int o,int l,int r,int v){
sumv[o]-=(ll)(cnta[o])*(maxv[o]-v);
maxv[o]=v;minv[o]=min(v,minv[o]);
if(maxv[o]==minv[o]){
sumv[o]=(ll)(r-l+)*v;cnta[o]=cnti[o]=r-l+;seca[o]=-inf;seci[o]=inf;
}else seci[o]=min(v,seci[o]);
}
inline void pushdown(int o,int l,int r){
int mid=(l+r)>>;
if(tagv[o]){
puttag(lson,l,mid,tagv[o]);puttag(rson,mid+,r,tagv[o]);
tagv[o]=;
}
if(maxv[lson]>maxv[o]&&seca[lson]<maxv[o])tmin(lson,l,mid,maxv[o]);
if(maxv[rson]>maxv[o]&&seca[rson]<maxv[o])tmin(rson,mid+,r,maxv[o]);
if(minv[lson]<minv[o]&&seci[lson]>minv[o])tmax(lson,l,mid,minv[o]);
if(minv[rson]<minv[o]&&seci[rson]>minv[o])tmax(rson,mid+,r,minv[o]);
}
void build(int o,int l,int r){
tagv[o]=;
if(l==r){
int x=read();
sumv[o]=maxv[o]=minv[o]=x;cnta[o]=cnti[o]=;seca[o]=-inf;seci[o]=inf;tagv[o]=;return;
}
int mid=(l+r)>>;
build(lson,l,mid);build(rson,mid+,r);
pushup(o);
}
void changemax(int o,int l,int r,int ql,int qr,int v){
if(minv[o]>=v)return;
if(ql<=l&&r<=qr&&v<seci[o]){tmax(o,l,r,v);return;}
pushdown(o,l,r);int mid=(l+r)>>;
if(ql<=mid)changemax(lson,l,mid,ql,qr,v);
if(qr>mid)changemax(rson,mid+,r,ql,qr,v);
pushup(o);
}
void changemin(int o,int l,int r,int ql,int qr,int v){
if(maxv[o]<=v)return;
if(ql<=l&&r<=qr&&v>seca[o]){tmin(o,l,r,v);return;}
pushdown(o,l,r);int mid=(l+r)>>;
if(ql<=mid)changemin(lson,l,mid,ql,qr,v);
if(qr>mid)changemin(rson,mid+,r,ql,qr,v);
pushup(o);
}
void add(int o,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){puttag(o,l,r,v);return;}
pushdown(o,l,r);int mid=(l+r)>>;
if(ql<=mid)add(lson,l,mid,ql,qr,v);
if(qr>mid)add(rson,mid+,r,ql,qr,v);
pushup(o);
}
int querymax(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return maxv[o];
pushdown(o,l,r);int mid=(l+r)>>,ans=-inf;
if(ql<=mid)ans=max(ans,querymax(lson,l,mid,ql,qr));
if(qr>mid)ans=max(ans,querymax(rson,mid+,r,ql,qr));
return ans;
}
int querymin(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return minv[o];
pushdown(o,l,r);int mid=(l+r)>>,ans=inf;
if(ql<=mid)ans=min(ans,querymin(lson,l,mid,ql,qr));
if(qr>mid)ans=min(ans,querymin(rson,mid+,r,ql,qr));
return ans;
}
ll querysum(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sumv[o];
pushdown(o,l,r);int mid=(l+r)>>;ll ans=;
if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
if(qr>mid)ans+=querysum(rson,mid+,r,ql,qr);
return ans;
}
//End of Segment Tree
int main(){
n=read();build(,,n);
int T=read();
while(T--){
int opt=read(),l=read(),r=read(),v;
if(opt==)v=read(),add(,,n,l,r,v);
if(opt==)v=read(),changemax(,,n,l,r,v);
if(opt==)v=read(),changemin(,,n,l,r,v);
if(opt==)printf("%lld\n",querysum(,,n,l,r));
if(opt==)printf("%d\n",querymax(,,n,l,r));
if(opt==)printf("%d\n",querymin(,,n,l,r));
}
}
这个代码可读性挺不错的，而且只有120行