[cpp] view plaincopy 題意不用說了，此題是傳說中的 “傻仔哥” 出的，雖然不知教主真名，但是還是看著他的線段樹長大的.... Code： #include<iostream> #include<cstdio> #include<string> #include<cmath> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define manx 100050 using namespace std; int root[manx<<2],lm[manx<<2],rm[manx<<2],a[manx]; void up(int l,int r,int rt){ lm[rt] = lm[rt<<1]; rm[rt] = rm[rt<<1|1]; root[rt] = max(root[rt<<1],root[rt<<1|1]); int mid = (l+r)>>1; if(a[mid+1]>a[mid]){ if(lm[rt<<1] == mid-l+1) lm[rt] += lm[rt<<1|1]; if(rm[rt<<1|1] == r-mid) rm[rt] += rm[rt<<1]; root[rt] = max(root[rt],lm[rt<<1|1]+rm[rt<<1]); } } void make(int l,int r,int rt){ if(l==r){ lm[rt] = rm[rt] = root[rt] = 1; return ; } int mid = (l+r)>>1; make(lson); make(rson); up(l,r,rt); // cout<<l<<" "<<r<<" "<<rt<<" "<<root[rt]<<endl; } int query(int l,int r,int rt,int ll,int rr){ if(ll<=l && rr>=r){ return root[rt]; } int mid=(l+r)>>1; if(rr<=mid) return query(lson,ll,rr); else if(ll>mid) return query(rson,ll,rr); else { int t1 = query(lson,ll,mid); int t2 = query(rson,mid+1,rr); int t = max(t1,t2); if(a[mid] < a[mid+1]){ t1 = min(rm[rt<<1],mid-ll+1); //// 防止越界的情況發生 t2 = min(lm[rt<<1|1],rr-mid); t1 += t2; } return max(t,t1); } } void update(int l,int r,int rt,int p,int q){ if(l==r && r==p){ a[l] = q; return ; } int mid = (l+r)>>1; if(p<=mid) update(lson,p,q); else update(rson,p,q); up(l,r,rt); } int main(){ int t,n,m; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); make(1,n,1); int p,q; char ch[5]; for(int i=1;i<=m;i++){ scanf("%s%d%d",ch,&p,&q); if(ch[0]=='Q'){ p++,q++; int flag = query(1,n,1,p,q); printf("%d\n",flag); } if(ch[0]=='U'){ p++; update(1,n,1,p,q); } } } }
