给n个数字 U表示第A个数改为B。A是从0开始。
Q输出最大的递增序列个数。
考虑左边，右边，和最大的。
#include<stdio.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 100010 int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2]; int num[maxn]; int max(int x,int y) { return x>y?x:y; } int min(int x,int y) { return x<y?x:y; } void pushup(int l,int r,int rt) { int m=(l+r)/2; lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; msum[rt]=max(msum[rt<<1],msum[rt<<1|1]); if(num[m]<num[m+1]) { if(lsum[rt<<1]==m-l+1) lsum[rt]=lsum[rt<<1]+lsum[rt<<1|1]; if(rsum[rt<<1|1]==r-m) rsum[rt]=rsum[rt<<1|1]+rsum[rt<<1]; msum[rt]=max(msum[rt],lsum[rt<<1|1]+rsum[rt<<1]); } } void build(int l,int r,int rt) { if(l==r) { lsum[rt]=rsum[rt]=msum[rt]=1; return; } int m=(l+r)/2; build(lson); build(rson); pushup(l,r,rt); } void updata(int p,int c,int l,int r,int rt) { if(l==r) { num[l]=c; return ; } int m=(l+r)/2; if(m>=p) updata(p,c,lson); else updata(p,c,rson); pushup(l,r,rt); } int query(int L,int R,int l,int r,int rt) { if(l>=L&&R>=r) return msum[rt]; int ret=0; int m=(l+r)/2; if(m>=L) ret=max(ret,query(L,R,lson)); if(R>m) ret=max(ret,query(L,R,rson)); if(num[m]<num[m+1]) { ret=max(ret,min(m-L+1,rsum[rt<<1])+min(R-m,lsum[rt<<1|1])); } return ret; } int main() { int n,t,m,i; char s[10]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&num[i]); build(1,n,1); int a,b; while(m--) { scanf("%s %d %d",s,&a,&b); if(s[0]=='U') updata(a+1,b,1,n,1); else if(s[0]=='Q') printf("%d ",query(a+1,b+1,1,n,1)); } } }