LCIS（线段树区间合并）

时间：2023-03-08 15:49:58

LCIS

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5912    Accepted Submission(s): 2563

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].
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).
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
题解：

给你n个数组成的序列（序列中编号从0到n-1），有q次操作。

操作1——Q a  b，让你输出区间[a, b]里面最长的连续递增序列的长度；

操作2——U a  b，修改序列第a个数为b。

出了点小问题错了半天；

刚开始理解错了，是单调上升序列；1 3 5 7也算；

区间合并

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define SD(x,y) scanf("%lf%lf",&x,&y)

#define P_ printf(" ")

#define ll root<<1

#define rr root<<1|1

#define lson ll,l,mid

#define rson rr,mid+1,r

typedef long long LL;

const int MAXN=100010;

struct Node{

	int len,lv,rv,lsum,rsum,sum;

	 Node init(int l,int r){

		scanf("%d",&lv);rv=lv;

		lsum=sum=rsum=1;

	}

};

Node tree[MAXN<<2];

/*void print(int root,int l,int r){

	int mid=(l+r)>>1;

	if(l==r){

		printf("%d %d\n",tree[root].lv,tree[root].rv);return;

	}

	print(lson);print(rson);

}*/

void pushup(int root){

	tree[root].lsum=tree[ll].lsum;

	tree[root].rsum=tree[rr].rsum;

	tree[root].lv=tree[ll].lv;

	tree[root].rv=tree[rr].rv;

	tree[root].sum=max(tree[ll].sum,tree[rr].sum);

	if(tree[ll].rv<tree[rr].lv){

		if(tree[ll].lsum==tree[ll].len)tree[root].lsum+=tree[rr].lsum;

		if(tree[rr].rsum==tree[rr].len)tree[root].rsum+=tree[ll].rsum;

		tree[root].sum=max(tree[root].sum,tree[ll].rsum+tree[rr].lsum);

	}

}

void build(int root,int l,int r){

	tree[root].len=r-l+1;//放在里面了。。。错了

	if(l==r){

		tree[root].init(l,r);

		return ;

	}

	int mid=(l+r)>>1;

	build(lson);

	build(rson);

	pushup(root);

}

void update(int root,int l,int r,int A,int B){

	int mid=(l+r)>>1;

	if(l==A&&r==A){

		tree[root].lv=tree[root].rv=B;

		return;

	}

	if(mid>=A)update(lson,A,B);

	else update(rson,A,B);

	pushup(root);

}

int query(int root,int l,int r,int A,int B){

	if(l>=A&&r<=B)return tree[root].sum;

	int mid=(l+r)>>1;

	int ans=0;

	if(mid>=A)ans=max(ans,query(lson,A,B));//多加了return错了半天；；；；

	if(mid<B)ans=max(ans,query(rson,A,B));//

	if(tree[ll].rv<tree[rr].lv)

		ans=max(ans,min(mid-A+1,tree[ll].rsum)+min(B-mid,tree[rr].lsum));

		//以免超过查询区间；因为里面的lsum,rsum分别维护的左右最大连续上升序列；

	return ans;

}

int main(){

	int T,N,M;

	char s[5];

	int A,B;

	SI(T);

	while(T--){

		SI(N);SI(M);

		build(1,1,N);

		while(M--){

			scanf("%s%d%d",s,&A,&B);

			A++;

			if(s[0]=='Q'){

				B++;

				printf("%d\n",query(1,1,N,A,B));

			}

			else update(1,1,N,A,B);

		//	print(1,1,N);

		}

	}

	return 0;

}

　　

相关文章