题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308
题意：给你n个数，m个操作。操作有两种：1.U x y 将数组第x位变为y 2. Q x y 问数组第x位到第y位连续最长子序列的长度。对于每次询问，输出一个答案
题解：一道简单的线段树区间合并，一般线段树的区间合并都会设lsum,rsum，表示左连续和右连续还有sum表示总共的连续。
转移比较复杂那这题为例
int L = T[i << 1].r , R = T[(i << 1) | 1].l;
T[i].l = T[i << 1].l , T[i].r = T[(i << 1) | 1].r;
T[i].lsum = T[i << 1].lsum , T[i].rsum = T[(i << 1) | 1].rsum;
T[i].sum = max(T[i << 1].sum , T[(i << 1) | 1].sum);
if(a[L] < a[R] && R - L == 1) {
if(T[i << 1].lsum == T[i << 1].r - T[i << 1].l + 1) {
T[i].lsum += T[(i << 1) | 1].lsum;
}//注意看是否可以合并
if(T[(i << 1) | 1].rsum == T[(i << 1) | 1].r - T[(i << 1) | 1].l + 1) {
T[i].rsum += T[i << 1].rsum;
}//注意看是否可以合并
T[i].sum = max(T[i].sum , T[i << 1].rsum + T[(i << 1) | 1].lsum);
}
区间合并注意T[i].lsum的更新和T[i].rsum的更新，sum的更新比较简单。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1e5 + 10;
int a[M];
struct TnT {
int l , r , lsum , rsum , sum;
}T[M << 2];
void push_up(int i) {
int L = T[i << 1].r , R = T[(i << 1) | 1].l;
T[i].l = T[i << 1].l , T[i].r = T[(i << 1) | 1].r;
T[i].lsum = T[i << 1].lsum , T[i].rsum = T[(i << 1) | 1].rsum;
T[i].sum = max(T[i << 1].sum , T[(i << 1) | 1].sum);
if(a[L] < a[R] && R - L == 1) {
if(T[i << 1].lsum == T[i << 1].r - T[i << 1].l + 1) {
T[i].lsum += T[(i << 1) | 1].lsum;
}
if(T[(i << 1) | 1].rsum == T[(i << 1) | 1].r - T[(i << 1) | 1].l + 1) {
T[i].rsum += T[i << 1].rsum;
}
T[i].sum = max(T[i].sum , T[i << 1].rsum + T[(i << 1) | 1].lsum);
}
}
void build(int l , int r , int i) {
int mid = (l + r) >> 1;
T[i].l = l , T[i].r = r , T[i].lsum = 1 , T[i].rsum = 1 , T[i].sum = 1;
if(l == r) return ;
build(l , mid , i << 1);
build(mid + 1 , r , (i << 1) | 1);
push_up(i);
}
void updata(int pos , int ad , int i) {
int mid = (T[i].l + T[i].r) >> 1;
if(T[i].l == pos && T[i].r == pos) {
a[pos] = ad;
return ;
}
if(mid < pos) updata(pos , ad , (i << 1) | 1);
else updata(pos , ad , i << 1);
push_up(i);
}
int query(int l , int r , int i) {
int mid = (T[i].l + T[i].r) >> 1;
if(T[i].l == l && T[i].r == r) {
return T[i].sum;
}
push_up(i);
if(mid < l) {
return query(l , r , (i << 1) | 1);
}
else if(mid >= r) {
return query(l , r , i << 1);
}
else {
int ans = max(query(l , mid , i << 1) , query(mid + 1 , r , (i << 1) | 1));
ans = max(ans , 1);
if(a[T[i << 1].r] < a[T[(i << 1) | 1].l] && T[i].l != T[i].r) {
return max(ans , min(T[i << 1].rsum , mid - l + 1) + min(T[(i << 1) | 1].lsum , r - mid));
}
else {
return ans;
}
}
}
int main() {
int t , n , m , x , y;
scanf("%d" , &t);
while(t--) {
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < n ; i++) {
scanf("%d" , &a[i]);
}
char cp[10];
build(0 , n , 1);
while(m--) {
scanf("%s" , cp);
scanf("%d%d" , &x , &y);
if(cp[0] == 'U') {
updata(x , y , 1);
}
else {
printf("%d
" , query(min(x , y) , max(x , y) , 1));
}
}
}
return 0;
}