线段树上的一种dp
using namespace std;ll;read(){int x=0,f=1;char ch=getchar();while(ch>’9’||ch<‘0′){if(ch==’-‘)f=-1;ch=getchar();}while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0′;ch=getchar();}return x*f;}#define N 100010int n,m,a[N];Segment_Tree{int lz,len;int lv,rv;//len from left,len from rightint lenl,lenr;int maxl;Segment_Tree(){};}tree[N<<2];void pullup(Segment_Tree &treeid,Segment_Tree &treelch,Segment_Tree &treerch){//tree[id] is not leaftreeid.lv=treelch.lv;treeid.lenl=treelch.lenl;if(treelch.lenl==treelch.len && treelch.rv<treerch.lv) treeid.lenl=treelch.len+treerch.lenl;treeid.rv=treerch.rv;treeid.lenr=treerch.lenr;if(treerch.lenr==treerch.len && treelch.rv<treerch.lv) treeid.lenr=treelch.lenr+treerch.len;treeid.maxl=max(treelch.maxl , treerch.maxl);treeid.maxl=max(treeid.maxl , treelch.lenl);treeid.maxl=max(treeid.maxl , treerch.lenr);if(treelch.rv<treerch.lv) treeid.maxl=max(treeid.maxl , treelch.lenr+treerch.lenl);}void plant_tree(int id,int l,int r){tree[id].lz=0;tree[id].len=r-l+1;if(l==r){tree[id].lv = tree[id].rv = a[l];tree[id].lenl = tree[id].lenr = tree[id].maxl = 1;return;}plant_tree(lch,l,mid);plant_tree(rch,mid+1,r);pullup(tree[id],tree[lch],tree[rch]);}void pushdown(int id){if(tree[id].lz){tree[lch].lz = tree[id].lz;tree[lch].lv = tree[lch].rv = tree[id].lz;tree[lch].lenl = tree[lch].lenr = tree[lch].maxl=1;tree[rch].lz = tree[id].lz;tree[rch].lv = tree[rch].rv = tree[id].lz;tree[rch].lenl = tree[rch].lenr = tree[rch].maxl=1;tree[id].lz=0;}}void update(int id,int l,int r,int ql,int qr,int v){if(ql==l && qr==r){tree[id].lz = v;tree[id].lv = tree[id].rv = v;tree[id].lenl = tree[id].lenr = tree[id].maxl=1;return;}pushdown(id);if(qr<=mid) update(lch,l,mid,ql,qr,v);else if(mid<ql) update(rch,mid+1,r,ql,qr,v);else update(lch,l,mid,ql,mid,v),update(rch,mid+1,r,mid+1,qr,v);pullup(tree[id],tree[lch],tree[rch]);}int ans;void query(int id,int l,int r,int ql,int qr,Segment_Tree &node){if(ql==l && qr==r){ans=max(ans,tree[id].maxl);node=tree[id];return;}pushdown(id);if(qr<=mid) query(lch,l,mid,ql,qr,node);else if(mid<ql) query(rch,mid+1,r,ql,qr,node);else{Segment_Tree lson,rson;query(lch,l,mid,ql,mid,lson);query(rch,mid+1,r,mid+1,qr,rson);pullup(node,lson,rson);ans=max(ans,node.maxl);}pullup(tree[id],tree[lch],tree[rch]);}int main(){//input;n=read(),m=read();for(int i=1;i<=n;i++){a[i]=read();}plant_tree(1,1,n);for(int i=1;i<=m;i++){char s[5];scanf(“%s”,s);if(s[0]==’Q’){int l,r;l=read(),r=read();ans=1;Segment_Tree now;query(1,1,n,l,r,now);printf(“%d\n”,ans);}else{int l,r,yi;l=read(),r=read(),yi=read();update(1,1,n,l,r,yi);}}return 0;}
，有一些穿高跟鞋走不到的路，
