HDU 3308 最长上升连续子序列 （线段树）
题意不用说了，此题是传说中的 “傻仔哥” 出的，虽然不知教主真名，但是还是看着他的线段树长大的....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 100050using 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); } } }}