|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3308
  /**//*
 題意：
給出一個(gè)長(zhǎng)度為N(N <= 100000)的數(shù)列，然后是兩種操作：
U A B: 將第A個(gè)數(shù)替換為B (下標(biāo)從零開(kāi)始)
Q A B: 輸出區(qū)間[A, B]的最長(zhǎng)連續(xù)遞增子序列
注意：操作的數(shù)目m <= 100000。
解法：
線段樹(shù)
思路：
做慣了區(qū)間最值、求和、修改、染色的等問(wèn)題，這題算比較新穎
的了，由這題可以看出線段樹(shù)的一般解法，因?yàn)檫@題要求保存的信息
比較多，每個(gè)線段樹(shù)的結(jié)點(diǎn)要求保存的信息有以下幾個(gè)：
int lMax; // 包含結(jié)點(diǎn)左端點(diǎn)的最長(zhǎng)連續(xù)遞增子序列的長(zhǎng)度
int rMax; // 包含結(jié)點(diǎn)右端點(diǎn)的最長(zhǎng)連續(xù)遞增子序列的長(zhǎng)度
int Max; // 當(dāng)前結(jié)點(diǎn)的最長(zhǎng)連續(xù)遞增子序列的長(zhǎng)度
int lVal, rVal; // 當(dāng)前結(jié)點(diǎn)管轄的區(qū)間左右端點(diǎn)的數(shù)值
int l, r; // 當(dāng)前結(jié)點(diǎn)管轄的區(qū)間
我們用以下函數(shù)從左右兒子中得到當(dāng)前結(jié)點(diǎn)的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫(xiě)成函數(shù)是因?yàn)檫@里的處理比較麻煩，很容易出錯(cuò)，并且需要
調(diào)用多次，這個(gè)函數(shù)的作用就是通過(guò)左右兒子的信息填充本身的信息。
lVal、rVal、l、r等信息比較容易求得。
lMax和rMax的值就比較麻煩了，需要分情況討論（下面的len表示區(qū)間長(zhǎng)度）：
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);
一開(kāi)始讀入的時(shí)候有一連串?dāng)?shù)字，需要建樹(shù)，建樹(shù)的時(shí)候每次回歸時(shí)需要
將兒子的信息傳遞給父親，調(diào)用UpdateBy(Tree* ls, Tree* rs)函數(shù)，每
次插入完畢后回歸時(shí)，信息會(huì)更新，也需要調(diào)用。詢問(wèn)時(shí)，返回的也是一
個(gè)線段樹(shù)結(jié)點(diǎn)，并且需要將答案合并，還是需要調(diào)用UpdateBy函數(shù)，所以
總的來(lái)說(shuō)需要調(diào)用三次，把它寫(xiě)成一個(gè)函數(shù)還是勢(shì)在必行的。
 */
#include <iostream>
using namespace std;
#define maxn 100010
struct Tree  {
int lMax; // 包含結(jié)點(diǎn)左端點(diǎn)的最長(zhǎng)連續(xù)遞增子序列
int rMax; // 包含結(jié)點(diǎn)右端點(diǎn)的最長(zhǎng)連續(xù)遞增子序列
int Max; // 當(dāng)前結(jié)點(diǎn)的最長(zhǎng)連續(xù)遞增子序列
int lVal, rVal; // 當(dāng)前區(qū)間左右端點(diǎn)的值
int l, r; // 當(dāng)前結(jié)點(diǎn)管轄的區(qū)間
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;
}
|