发现区间合并总之就那点套路,无非就是另开2个数组多记录区间左值和右值,再注意合并即可。
#include<cstdio> int si[500000],li[500000],ri[500000],l[500000],r[500000]; struct node { int le; int re; int se; }; int max(int a,int b) { return a>b?a:b; } void up(int i,int m) { l[i]=l[2*i]; r[i]=r[2*i+1]; li[i]=li[2*i]; ri[i]=ri[2*i+1]; if(si[2*i]==(m-(m>>1))&&r[2*i]<l[2*i+1])li[i]=(m-(m>>1))+li[2*i+1]; if(si[2*i+1]==((m>>1))&&r[2*i]<l[2*i+1])ri[i]=((m>>1))+ri[2*i]; si[i]=max(si[2*i],si[2*i+1]); if(r[2*i]<l[2*i+1]) si[i]=max(si[i],ri[2*i]+li[2*i+1]); } void build(int i,int a,int b) { if(a==b) { scanf("%d",l+i); r[i]=l[i]; li[i]=ri[i]=si[i]=1; return; } int m=(a+b)>>1; build(2*i,a,m); build(2*i+1,m+1,b); up(i,b-a+1); } void ud(int i,int in,int a,int b,int x) { if(a==b) { r[i]=l[i]=x; li[i]=ri[i]=si[i]=1; return; } int m=(a+b)>>1; if(m>=in) ud(2*i,in,a,m,x); else ud(2*i+1,in,m+1,b,x); up(i,b-a+1); } node qu(int i,int it,int ot,int a,int b) { if(it==a&&ot==b) { node c; c.le=li[i]; c.re=ri[i]; c.se=si[i]; return c; } int m=(a+b)>>1; if(m>=ot) return qu(2*i,it,ot,a,m); else if(m<it) return qu(2*i+1,it,ot,m+1,b); else { node c=qu(2*i,it,m,a,m); node d=qu(2*i+1,m+1,ot,m+1,b); node e; e.le=c.le; e.re=d.re; if(c.se==(m-a+1)&&r[2*i]<l[2*i+1]) e.le=(m-a+1)+d.le; if(d.se==(b-m)&&r[2*i]<l[2*i+1]) e.re=(b-m)+c.re; e.se=max(c.se,d.se); if(r[2*i]<l[2*i+1]) { e.se=max(e.se,c.re+d.le); } return e; } } int t,n,m; int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { char str[2]; int a,b; scanf("%s%d%d",str,&a,&b); if(*str=='U') { a++; ud(1,a,1,n,b); } else { a++; b++; node qw=qu(1,a,b,1,n); printf("%d\n",qw.se); } } } return 0; }