题目链接：
题目很好懂，就是单点更新，然后求区间的最长上升子序列。
线段树区间合并问题，注意合并的条件是a[mid + 1] > a[mid]，写的细心点就好了。
1 #include2 #include 3 #include 4 using namespace std; 5 const int MAXN = 1e5 + 5; 6 struct SegTree { 7 int l , r , lsum , sum , rsum; 8 }T[MAXN << 2]; 9 int a[MAXN];10 11 void pushup(int p) {12 int ls = p << 1 , rs = (p << 1)|1 , mid = (T[p].r + T[p].l) >> 1;13 T[p].lsum = T[ls].lsum , T[p].rsum = T[rs].rsum;14 if(T[p].lsum == T[ls].r - T[ls].l + 1) {15 T[p].lsum += (a[mid + 1] > a[mid] ? T[rs].lsum : 0);16 }17 if(T[p].rsum == T[rs].r - T[rs].l + 1) {18 T[p].rsum += (a[mid + 1] > a[mid] ? T[ls].rsum : 0);19 }20 T[p].sum = max(T[ls].sum , T[rs].sum);21 int temp = (a[mid + 1] > a[mid] ? T[ls].rsum + T[rs].lsum : 1);22 T[p].sum = max(temp , T[p].sum);23 }24 25 void build(int p , int l , int r) {26 int mid = (l + r) >> 1;27 T[p].l = l , T[p].r = r;28 if(l == r) {29 T[p].lsum = T[p].rsum = T[p].sum = 1;30 return ;31 }32 build(p << 1 , l , mid);33 build((p << 1)|1 , mid + 1 , r);34 pushup(p);35 }36 37 void updata(int p , int pos , int num) {38 int mid = (T[p].l + T[p].r) >> 1;39 if(T[p].l == T[p].r && T[p].l == pos) {40 a[pos] = num;41 return ;42 }43 if(pos <= mid) {44 updata(p << 1 , pos , num);45 }46 else {47 updata((p << 1)|1 , pos , num);48 }49 pushup(p);50 }51 52 int query(int p , int l , int r) {53 int mid = (T[p].l + T[p].r) >> 1;54 if(l == T[p].l && T[p].r == r) {55 return T[p].sum;56 }57 if(r <= mid) {58 return query(p << 1 , l , r);59 }60 else if(l > mid) {61 return query((p << 1)|1 , l , r);62 }63 else {64 return max((a[mid + 1] > a[mid] ? min(mid - l + 1 , T[p << 1].rsum) + min(T[(p << 1)|1].lsum , r - mid) : 1) ,65 max(query(p << 1 , l , mid) , query((p << 1)|1 , mid + 1 , r) ) );66 }67 }68 69 int main()70 {71 int t , n , m;72 scanf("%d" , &t);73 while(t--) {74 scanf("%d %d" , &n , &m);75 for(int i = 1 ; i <= n ; ++i) {76 scanf("%d" , a + i);77 }78 build(1 , 1 , n);79 char q[5];80 int l , r;81 while(m--) {82 scanf("%s %d %d" , q , &l , &r);83 if(q[0] == 'Q') {84 printf("%d\n" , query(1 , l + 1 , r + 1));85 }86 else {87 updata(1 , l + 1 , r);88 }89 }90 }91 return 0;92 }