HDU 3308 线段树 最长连续上升子序列 单点更新 区间查询
题意：
T个测试数据
n个数 q个查询
n个数 ( 下标从0开始)
Q u v 查询 [u, v ] 区间最长连续上升子序列
U u v 把u位置改成v
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define N 101010#define L(x) (x<<1)#define R(x) (x<<1|1)inline int Max(int a,int b){return a>b?a:b;}inline int Min(int a,int b){return a<b?a:b;}struct node{int l,r;int mid(){ return (l+r)>>1; }int len(){ return r-l+1; }int Llen, Rlen, maxlen;}tree[4*N];int a[N];void updata_up(int id){tree[id].Llen = tree[L(id)].Llen;tree[id].Rlen = tree[R(id)].Rlen;tree[id].maxlen = Max( tree[L(id)].maxlen, tree[R(id)].maxlen);if( a[ tree[L(id)].r ] < a[ tree[R(id)].l ] ){if( tree[L(id)].Llen == tree[L(id)].len()){tree[id].Llen += tree[R(id)].Llen;tree[id].maxlen = Max( tree[id].maxlen, tree[id].Llen);}if( tree[R(id)].Rlen == tree[R(id)].len() ){tree[id].Rlen += tree[L(id)].Rlen;tree[id].maxlen = Max( tree[id].maxlen, tree[id].Rlen);}tree[id].maxlen = Max( tree[id].maxlen, tree[L(id)].Rlen + tree[R(id)].Llen );}}void build(int l, int r, int id){tree[id].l = l, tree[id].r = r;if(l==r){ tree[id].Llen = tree[id].Rlen = tree[id].maxlen =1; return ; }int mid = (l+r)>>1;build(l, mid, L(id));build(mid+1, r, R(id));updata_up(id);}void updata(int pos,int id){if(tree[id].l == tree[id].r)return ;int mid = tree[id].mid();if( pos <= mid ) updata(pos, L(id));else updata(pos, R(id));updata_up(id);}int query(int l, int r, int id){if( l == tree[id].l && tree[id].r == r)return tree[id].maxlen;int mid = tree[id].mid();if(r <= mid)return query(l, r, L(id));else if(mid < l) return query(l, r, R(id));int L = query(l, mid, L(id)), R = query(mid+1, r, R(id));if( a[mid] < a[mid+1] ){int LL = Min( mid - l + 1, tree[L(id)].Rlen);int RR = Min( r - mid, tree[R(id)].Llen);return Max( Max(L,R), LL+RR);}else return Max(L, R);}int main(){int T,n,q,i; scanf("%d",&T);while(T--){scanf("%d %d", &n, &q);for(i=1;i<=n;i++)scanf("%d",&a[i]);build(1, n, 1);while(q--){char c = '-';while(c!='Q' && c!='U') c = getchar();int u,v; scanf("%d %d", &u, &v);if(c == 'Q')printf("%d\n", query(u+1, v+1, 1));else if(c == 'U'){ a[u+1] = v; updata(u+1, 1); }}}return 0;}/*9910 107 7 3 3 5 9 9 8 1 8 Q 6 6U 3 4Q 0 1Q 0 5Q 4 7Q 3 5Q 0 2Q 4 6U 6 10Q 0 910 991 2 3 4 5 6 7 8 9 10Q 4 7U 0 8Q 0 9U 8 8Q 0 9*/