|
给定10^5个数,区间查询严格上升的最长连续序列长度,点更新某个数. |
线段树，区间合并 有三个数组,msum, lsum, rsum,分别存总最长,左端串长,右端串长 一直错的一个地方是:query中,合并的时候,若左右儿子可以合并,应该取max{min[左儿子右长,实际右长],min[右儿子左长,实际左长]},而不是max{min[左儿子最大长,实际右长],min[右儿子最大长,实际左长]}.因为有可能儿子最大长并不是由中间接上的那一段产生的 这种细节非常复杂的题分析清楚算法很重要.靠Debug实在很难找.其实是原理性错误... |
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 100005;
int num[maxn];
int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];
void PushUp(int l, int r,int rt) {
lsum[rt] = lsum[rt<<1];
rsum[rt] = rsum[rt<<1|1];
int m = (l+r)>>1;
if(num[m]<num[m+1])
{
if (lsum[rt] == m - l + 1) lsum[rt] += lsum[rt<<1|1];
if (rsum[rt] == r - m) rsum[rt] += rsum[rt<<1];
msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));
}
else
{
msum[rt] = max(msum[rt<<1] , msum[rt<<1|1]);
}
}///总最长为左和 or 右和 or 左右拼接中间的段
void build(int l,int r,int rt) {
msum[rt] = lsum[rt] = rsum[rt] = 1;//区间长度
if (l == r) return ;
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(l,r,rt);
}
void update(int p,int c,int l,int r,int rt) {
if (l==r) {
msum[rt] = lsum[rt] = rsum[rt] = 1;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(p , c , lson);
if (m < p) update(p , c , rson);
PushUp(l,r,rt);
}
int query(int L,int R,int l,int r,int rt) {
if(L==l&&r==R)//?
{
return msum[rt];
}
int m = (l+r)>>1;
if(R<=m)
{
return query(L, R, lson);
}
else if(L>m)
{
return query(L, R, rson);
}
else if(num[m]>=num[m+1])
{
return max(query(L, m, lson),query(m+1, R, rson));
}
else
{
int a = query(L,m,lson), b = query(m+1, R, rson);
int ls = min(rsum[rt<<1],m - L + 1), rs = min(lsum[rt<<1|1], R - m);
return max(max(a,b),ls+rs);
}
}
int main() {
int n , m, T;
scanf("%d",&T);
while (T--) {
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",num+i);
}
build(0 , n-1 , 1);
int a , b;
char op[2];
while(m--)
{
scanf("%s",op);
if (op[0] == 'U') {
scanf("%d %d",&a,&b);
num[a] = b;
update(a , b , 0 , n-1 , 1);
}
else {
scanf("%d %d",&a,&b);
printf("%d\n",query(a , b , 0 , n-1 , 1));
}
}
}
return 0;
}