LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9713 Accepted Submission(s): 4215
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<=10).
The next line has n integers(0<=val<=10).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10)
OR
Q A B(0<=A<=B< n).
Each case starts with two integers n , m(0<n,m<=10).
The next line has n integers(0<=val<=10).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10)
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
题意：求区间连续递增的最大个数，Q是询问区间内最大的LCIS
U是更新节点
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + ;
int llen[maxn << ], rlen[maxn << ], len[maxn << ], tree[maxn];
void pushup(int l, int r, int id)
{
int m = (l + r) >> ;
llen[id] = llen[id << ];
rlen[id] = rlen[id << | ];
if (tree[m + ] > tree[m])
{
if (llen[id << ] == m - l + )
llen[id] += llen[id << | ];
if (rlen[id << | ] == r - m)
rlen[id] += rlen[id << ];
len[id] = max(max(len[id << ], len[id << | ]), rlen[id << ] + llen[id << | ]);
}
else
len[id] = max(len[id << ], len[id << | ]);
}
void build(int l, int r, int id)
{
if (l == r)
{
scanf("%d", &tree[l]);
len[id] = llen[id] = rlen[id] = ;
return;
}
int m = (l + r) >> ;
build(l,m,id<<);
build(m+,r,id<<|);
pushup(l, r, id);
}
int query(int ll, int rr, int l, int r, int id)
{
if (ll <= l && r <= rr)
return len[id];
int m = (l + r) >> ;
if (ll <= m && m < rr)
{
int l1 = query(ll, rr, l,m,id<<);
int l2 = query(ll, rr, m+,r,id<<|);
if (tree[m] < tree[m + ])
{
int le = max(ll, m - rlen[id << ] + );
int ri = min(rr, m + llen[id << | ]);
return max(max(l1, l2), ri - le + );
}
return max(l1, l2);
}
else if (rr <= m)
return query(ll, rr, l,m,id<<);
else
return query(ll, rr, m+,r,id<<|);
} void update(int a, int b, int l, int r, int id)
{
if (a == l && a == r)//找到要更新的位置
{
tree[a] = b;
return;
}
int m = (l + r) >> ;
if (m >= a)
update(a, b, l,m,id<<);
else
update(a, b, m+,r,id<<|);
pushup(l, r, id);
}
int main()
{
int t;
scanf("%d\n", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
build(, n - , ); while (m--)
{
char c[];
int a, b;
scanf("%s %d %d", c, &a, &b);
if (c[] == 'Q')
printf("%d\n", query(a, b, , n - , ));
else
update(a, b, , n - , );
}
}
return ;
}