|
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3308
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给出一个长度为N(N <= 100000)的数列,然后是两种操作:
U A B: 将第A个数替换为B (下标从零开始)
Q A B: 输出区间[A, B]的最长连续递增子序列
注意:操作的数目m <= 100000。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
线段树
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
做惯了区间最值、求和、修改、染色的等问题,这题算比较新颖
的了,由这题可以看出线段树的一般解法,因为这题要求保存的信息
比较多,每个线段树的结点要求保存的信息有以下几个:
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int lMax; // 包含结点左端点的最长连续递增子序列的长度
int rMax; // 包含结点右端点的最长连续递增子序列的长度
int Max; // 当前结点的最长连续递增子序列的长度
int lVal, rVal; // 当前结点管辖的区间左右端点的数值
int l, r; // 当前结点管辖的区间
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
我们用以下函数从左右儿子中得到当前结点的信息:
void UpdateBy(Tree* ls, Tree* rs);
之所以把它写成函数是因为这里的处理比较麻烦,很容易出错,并且需要
调用多次,这个函数的作用就是通过左右儿子的信息填充本身的信息。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
lVal、rVal、l、r等信息比较容易求得。
lMax和rMax的值就比较麻烦了,需要分情况讨论(下面的len表示区间长度):
1. 左儿子最右边的值 < 右儿子最左边的值
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;
rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;
Max = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
2. 左儿子最右边的值 >= 右儿子最左边的值
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
lMax = 左儿子的lMax;
rMax = 右儿子的rMax;
Max = MAX(左儿子的Max, 右儿子的Max);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
一开始读入的时候有一连串数字,需要建树,建树的时候每次回归时需要
将儿子的信息传递给父亲,调用UpdateBy(Tree* ls, Tree* rs)函数,每
次插入完毕后回归时,信息会更新,也需要调用。询问时,返回的也是一
个线段树结点,并且需要将答案合并,还是需要调用UpdateBy函数,所以
总的来说需要调用三次,把它写成一个函数还是势在必行的。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 100010
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Tree {
int lMax; // 包含结点左端点的最长连续递增子序列
int rMax; // 包含结点右端点的最长连续递增子序列
int Max; // 当前结点的最长连续递增子序列
int lVal, rVal; // 当前区间左右端点的值
int l, r; // 当前结点管辖的区间
int son[2];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void clear() {
son[0] = son[1] = -1;
}
void UpdateBy(Tree* ls, Tree* rs);
void Unit(int nl, int nr, int nv);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) int len() {
return r - l + 1;
}
}T[maxn*4];
int root, tot;
int val[ maxn ];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int MAX(int a, int b) {
return a > b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int MAX(int a, int b, int c) {
return MAX(MAX(a, b), c);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int MAX(int a, int b, int c, int d) {
return MAX( MAX(a, b), MAX(c, d) );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Tree::UpdateBy(Tree* ls, Tree* rs) {
lVal = ls->lVal;
rVal = rs->rVal;
l = ls->l;
r = rs->r;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
lMax = ls->lMax;
rMax = rs->rMax;
Max = MAX(ls->Max, rs->Max);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Tree::Unit(int nl, int nr, int nv) {
lMax = rMax = 1; Max = 1;
lVal = rVal = nv;
l = nl; r = nr;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int GetID(int& root) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(root == -1) {
root = tot++;
T[root].clear();
}
return root;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Build(int& root, int l, int r) {
GetID(root);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Insert(int root, int nPos, int val) {
if(nPos < T[root].l || nPos > T[root].r)
return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) Tree Query(int root, int nl, int nr) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(nl > T[root].r || nr < T[root].l) {
Tree tmp;
tmp.Max = -1;
return tmp;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else {
Tree X;
X.UpdateBy(&A, &B);
return X;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n, m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int t, i;
scanf("%d", &t);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(t--) {
scanf("%d %d", &n, &m);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
tot = 0;
root = -1;
Build(root, 1, n);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(m--) {
char str[10];
int A, B;
scanf("%s %d %d", str, &A, &B);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!strcmp(str, "U")) {
Insert(root, A+1, B);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
Tree tmp = Query(root, A+1, B+1);
printf("%d\n", tmp.Max);
}
}
}
return 0;
}
|