|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3308
  /**//*
 題意：
給出一個長度為N(N <= 100000)的數列，然后是兩種操作：
U A B: 將第A個數替換為B (下標從零開始)
Q A B: 輸出區間[A, B]的最長連續遞增子序列
注意：操作的數目m <= 100000。
解法：
線段樹
思路：
做慣了區間最值、求和、修改、染色的等問題，這題算比較新穎
的了，由這題可以看出線段樹的一般解法，因為這題要求保存的信息
比較多，每個線段樹的結點要求保存的信息有以下幾個：
int lMax; // 包含結點左端點的最長連續遞增子序列的長度
int rMax; // 包含結點右端點的最長連續遞增子序列的長度
int Max; // 當前結點的最長連續遞增子序列的長度
int lVal, rVal; // 當前結點管轄的區間左右端點的數值
int l, r; // 當前結點管轄的區間
我們用以下函數從左右兒子中得到當前結點的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數是因為這里的處理比較麻煩，很容易出錯，并且需要
調用多次，這個函數的作用就是通過左右兒子的信息填充本身的信息。
lVal、rVal、l、r等信息比較容易求得。
lMax和rMax的值就比較麻煩了，需要分情況討論（下面的len表示區間長度）：
1. 左兒子最右邊的值 < 右兒子最左邊的值
lMax = (左兒子的lMax == 左兒子的len) ? 左兒子的len + 右兒子的lMax : 左兒子的lMax;
rMax = (右兒子的rMax == 右兒子的len) ? 右兒子的len + 左兒子的rMax : 右兒子的rMax;
Max = MAX(左兒子的rMax + 右兒子的lMax, 左兒子的Max, 右兒子的Max, lMax, rMax);
2. 左兒子最右邊的值 >= 右兒子最左邊的值
lMax = 左兒子的lMax;
rMax = 右兒子的rMax;
Max = MAX(左兒子的Max, 右兒子的Max);
一開始讀入的時候有一連串數字，需要建樹，建樹的時候每次回歸時需要
將兒子的信息傳遞給父親，調用UpdateBy(Tree* ls, Tree* rs)函數，每
次插入完畢后回歸時，信息會更新，也需要調用。詢問時，返回的也是一
個線段樹結點，并且需要將答案合并，還是需要調用UpdateBy函數，所以
總的來說需要調用三次，把它寫成一個函數還是勢在必行的。
 */
#include <iostream>
using namespace std;
#define maxn 100010
struct Tree  {
int lMax; // 包含結點左端點的最長連續遞增子序列
int rMax; // 包含結點右端點的最長連續遞增子序列
int Max; // 當前結點的最長連續遞增子序列
int lVal, rVal; // 當前區間左右端點的值
int l, r; // 當前結點管轄的區間
int son[2];
  void clear() {
son[0] = son[1] = -1;
 }
void UpdateBy(Tree* ls, Tree* rs);
void Unit(int nl, int nr, int nv);
int len() {
return r - l + 1;
}
}T[maxn*4];
int root, tot;
int val[ maxn ];
int MAX(int a, int b) {
return a > b ? a : b;
}
int MAX(int a, int b, int c) {
return MAX(MAX(a, b), c);
}
int MAX(int a, int b, int c, int d) {
return MAX( MAX(a, b), MAX(c, d) );
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
lVal = ls->lVal;
rVal = rs->rVal;
l = ls->l;
r = rs->r;
if(ls->rVal < rs->lVal) {
lMax = (ls->lMax == ls->len()) ? ls->len() + rs->lMax : ls->lMax;
rMax = (rs->rMax == rs->len()) ? rs->len() + ls->rMax : rs->rMax;
Max = MAX(ls->rMax + rs->lMax, ls->Max, rs->Max);
Max = MAX(Max, lMax, rMax);
}else {
lMax = ls->lMax;
rMax = rs->rMax;
Max = MAX(ls->Max, rs->Max);
}
}
void Tree::Unit(int nl, int nr, int nv) {
lMax = rMax = 1; Max = 1;
lVal = rVal = nv;
l = nl; r = nr;
}
int GetID(int& root) {
if(root == -1) {
root = tot++;
T[root].clear();
}
return root;
}
void Build(int& root, int l, int r) {
GetID(root);
if(l == r) {
T[root].Unit(l, r, val[l]);
return ;
}
int mid = (l + r) >> 1;
Build(T[root].son[0], l, mid);
Build(T[root].son[1], mid+1, r);
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
void Insert(int root, int nPos, int val) {
if(nPos < T[root].l || nPos > T[root].r)
return ;
if(T[root].l == nPos && nPos == T[root].r) {
T[root].Unit(nPos, nPos, val);
return ;
}
Insert(T[root].son[0], nPos, val);
Insert(T[root].son[1], nPos, val);
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
Tree Query(int root, int nl, int nr) {
if(nl > T[root].r || nr < T[root].l) {
Tree tmp;
tmp.Max = -1;
return tmp;
}
if(nl <= T[root].l && T[root].r <= nr) {
return T[root];
}
Tree A, B;
A = Query(T[root].son[0], nl, nr);
B = Query(T[root].son[1], nl, nr);
if(A.Max == -1)
return B;
else if(B.Max == -1)
return A;
else {
Tree X;
X.UpdateBy(&A, &B);
return X;
}
}
int n, m;
int main() {
int t, i;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
tot = 0;
root = -1;
Build(root, 1, n);
while(m--) {
char str[10];
int A, B;
scanf("%s %d %d", str, &A, &B);
if(!strcmp(str, "U")) {
Insert(root, A+1, B);
}else {
Tree tmp = Query(root, A+1, B+1);
printf("%d\n", tmp.Max);
}
}
}
return 0;
}
|