各种繁琐的线段树标记操作。。。赤裸裸的码农题。
调了一个晚上,最后写篇题解。
题解亮点:代码短,~~跑得慢(连第一页都没挤进去)~~
其实我跟你们说啊,代码短是好事~~(这里不是说压行好,我的代码不压行也没那么长)~~,因为代码短好调啊,几个类似的语句写个函数,既满足了懒人需要(减少码量),而且也让代码思路清晰,没有那么杂乱了。
the code:
//by Judge
#include<cstdio>
#include<iostream>
using namespace std;
const int M=2e5+;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1=buf,*p2=buf;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x,char chr='\n'){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} inline void cmax(int& a,int b){ if(a<b) a=b; }
struct node{ int l,r,len,tag,rev;
int sum,max[],lmax[],rmax[];
}t[M<<],zero; int n,m,v[M];
#define ls k<<1
#define rs k<<1|1
inline node merge(node a,node b){ //懒人合并
static node c;
c.sum=a.sum+b.sum;
for(int i=;i<=;++i){
c.lmax[i]=a.lmax[i];
if(a.lmax[i]==a.len)
c.lmax[i]+=b.lmax[i];
c.rmax[i]=b.rmax[i];
if(b.rmax[i]==b.len)
c.rmax[i]+=a.rmax[i];
c.max[i]=a.rmax[i]+b.lmax[i];
cmax(c.max[i],a.max[i]);
cmax(c.max[i],b.max[i]);
} return c;
} inline void pushup(int k){ //懒人pushup
t[]=merge(t[ls],t[rs]);
t[k].sum=t[].sum;
for(int i=;i<=;++i){
t[k].max[i]=t[].max[i];
t[k].lmax[i]=t[].lmax[i];
t[k].rmax[i]=t[].rmax[i];
}
} inline void chg(int k,int v){ //懒人change
if(v<){
t[k].sum=t[k].len*v,t[k].tag=v,t[k].rev=;
t[k].max[v]=t[k].lmax[v]=t[k].rmax[v]=t[k].len;
t[k].max[v^]=t[k].lmax[v^]=t[k].rmax[v^]=;
} else if(v==){
t[k].sum=t[k].len-t[k].sum;
if(t[k].tag!=-) t[k].tag^=;
else t[k].rev^=;
swap(t[k].max[],t[k].max[]);
swap(t[k].lmax[],t[k].lmax[]);
swap(t[k].rmax[],t[k].rmax[]);
}
} inline void pushdown(int k){ //pushdown可以非常短
if(t[k].tag!=-)
t[k].rev=,chg(ls,t[k].tag),
chg(rs,t[k].tag),t[k].tag=-;
else if(t[k].rev)
chg(ls,),chg(rs,),t[k].rev=;
} void build(int k,int l,int r){ /* 然后都是线段树常规操作 */
t[k].l=l,t[k].r=r,t[k].len=r-l+,t[k].tag=-;
if(l==r){ int c=v[l]; t[k].sum=c;
t[k].max[c]=t[k].lmax[c]=t[k].rmax[c]=; return ;
} int mid=l+r>>; build(ls,l,mid),build(rs,mid+,r),pushup(k);
} void update(int k,int L,int R,int opt){
if(L<=t[k].l&&t[k].r<=R) return chg(k,opt);
int mid=t[k].l+t[k].r>>; pushdown(k);
if(L<=mid) update(ls,L,R,opt);
if(R>mid) update(rs,L,R,opt); pushup(k);
} int query(int k,int L,int R){
if(L>t[k].r||t[k].l>R) return ;
if(L<=t[k].l&&t[k].r<=R) return t[k].sum;
pushdown(k); int mid=t[k].l+t[k].r>>;
return query(ls,L,R)+query(rs,L,R);
} node query_mx(int k,int L,int R){
if(L>t[k].r||t[k].l>R) return zero; //zero作用和他的名字一样,merge的时候就不算贡献了
if(L<=t[k].l&&t[k].r<=R) return t[k]; pushdown(k);
return merge(query_mx(ls,L,R),query_mx(rs,L,R));
} int main(){ n=read(),m=read();
for(int i=;i<=n;++i) v[i]=read();
build(,,n);
for(int opt,l,r;m;--m){ //处理各种操作
opt=read(),l=read()+,r=read()+;
if(opt<) update(,l,r,opt);
else if(opt==) print(query(,l,r));
else if(opt==) print(query_mx(,l,r).max[]);
} return Ot(),;
}
不压行也就一百一二十行吧。