Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6593 Accepted Submission(s): 2867
Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.
Sample Input
1 10 10 7 7 3 3 5 9 9 8 1 8 Q 6 6 U 3 4 Q 0 1 Q 0 5 Q 4 7 Q 3 5 Q 0 2 Q 4 6 U 6 10 Q 0 9
Sample Output
1 1 4 2 3 1 2 5
Author
shǎ崽
Source
【题解】
题意。给你n个整数。
会有以下两种操作:
1.把某个整数替换成另外一个数。
2.求出[l,r]这个区间内的最长上升子序列的长度。
思路是。
把一个区间[l,r]分成左右两部分。
那么这个区间内的最长上升子序列分两种情况。
第一种。整个序列都在左边。
第二种。整个序列都在右边。
第三种。一部分序列在左边，一部分序列在右边。
基于第三种。我们要在做线段树的时候记录两个值。
llong[rt],rlong[rt]。
分别表示以(rt所代表的线段的)最左边和以(rt所代表的线段的)最右边为起点和终点的最长上升子序列的长度。
如果rt<<1所在区间的最右边的元素<编号为rt<<1|1的节点所代表的区间的最左边的元素。则这两部分可以串起来。
即rlong[rt<<1]+llong[rt<<1|1]；
这个可以用来更新我们记录的第3个值maxlong[rt]
即rt这个区间内不管在哪里的最长上升子序列的长度。
更具体一点,maxlong[rt] = max(maxlong[rt<<1],maxlong[rt<<1|1]);
if (左儿子最右边<右儿子最左边)
maxlong[rt] = max(maxlong[rt],rlong[rt<<1]+llong[rt<<1|1]);
记录所有节点所代表的区间的最左边和最右边的元素就可以了。
询问的时候也用类似的办法。
【代码】
#include <cstdio>
#include <algorithm>
#define lson begin,m,rt<<1
#define rson m+1,end,rt<<1|1
using namespace std;
const int MAXN = 100001;
int n, m,llong[MAXN*4],rlong[MAXN*4],maxlong[MAXN*4],lnum[MAXN*4],rnum[MAXN*4];
void push_up(int rt, int len)
{
bool flag = rnum[rt << 1] < lnum[rt << 1 | 1];
maxlong[rt] = max(maxlong[rt << 1], maxlong[rt << 1 | 1]);
if (flag) //左右两边接起来的情况
maxlong[rt] = max(maxlong[rt], rlong[rt << 1] + llong[rt << 1 | 1]);
llong[rt] = llong[rt << 1];
if (flag && llong[rt] == (len - (len >> 1)))//如果整个左儿子都是上升
llong[rt] += llong[rt << 1 | 1];//就尝试加上右儿子的左半部分作为rt的llong
rlong[rt] = rlong[rt << 1 | 1];
if (flag && rlong[rt] == (len >> 1))
rlong[rt] += rlong[rt << 1];
lnum[rt] = lnum[rt << 1];
rnum[rt] = rnum[rt << 1 | 1];
}
void build(int begin, int end, int rt)
{
llong[rt] = rlong[rt] = maxlong[rt] = 0;
if (begin == end)
{
int x;
llong[rt] = rlong[rt] = maxlong[rt] = 1;
scanf("%d", &x);
lnum[rt] = rnum[rt] = x;
return;
}
int m = (begin + end) >> 1;
build(lson);
build(rson);
push_up(rt,end-begin+1);
}
void input_data()
{
scanf("%d%d", &n, &m);
build(1, n, 1);
}
void up_data(int pos, int num, int begin, int end, int rt)
{
if (begin == end)
{
lnum[rt] = rnum[rt] = num;//修改的时候只要改最左边和最右边的元素
return;
}
int m = (begin + end) >> 1;
if (pos <= m)
up_data(pos, num, lson);
else
up_data(pos, num, rson);
push_up(rt,end-begin+1);
}
int query(int l, int r, int begin, int end, int rt)
{
if (l <= begin && end <= r)
return maxlong[rt];
int m = (begin + end) >> 1;
bool flag1 = false, flag2 = false; //用来判断是否能划分为两个区间。
int dd = 0;
if (l <= m)
{
dd = max(dd, query(l, r, lson));
flag1 = true;
}
if (m < r)
{
dd = max(dd, query(l, r, rson));
flag2 = true;
}
if (flag1 && flag2 && rnum[rt << 1] < lnum[rt << 1 | 1])
{
int temp = min(m - l + 1, rlong[rt << 1]);//如果这个节点不完全在所询问的区间内
int temp1 = min(r - m, llong[rt << 1 | 1]);//那么直接连起来是会越界的。
dd = max(dd, temp + temp1);
}
return dd;
}
void output_ans()
{
for (int i = 1; i <= m; i++)
{
int x, y;
char op[10];
scanf("%s", op);
if (op[0] == 'U')
{
scanf("%d%d", &x, &y); //我下标习惯从1开始
x++;
up_data(x, y,1, n, 1);
}
else
{
scanf("%d%d", &x, &y);
x++; y++;
printf("%d
",query(x, y, 1, n, 1));
}
}
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
//freopen("F:\rush_out.txt", "w", stdout);
int t;
scanf("%d", &t);
while (t--) //在输入的时候要递增！！！！！！！！！！！
{
input_data();
output_ans();
}
return 0;
}