欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6406 Taotao Picks Apples

程序员文章站 2022-05-27 15:18:06
...

题意:给出一个序列,随意的修改他,让我们求这个序列以第一个元素为起点的最长的递增序列

思路:因为修改的次数过多那么无法暴力,那么可以用到线段树来优化查询的时间

线段树维护一个区间最大值,和一个当前区间的最优解,那么一个父节点的最优解由两部分组成,第一部分:一定是左子树的最哟姐,第二部分:思考左子树的最大值与右子树的关系我们可以知道,如果右子树的最大值小于左子树那么右子树的贡献为0,若干右子树的最大值大于左子树的最大值那么一定是有贡献的,但是贡献是多少呢?可以在考虑右子树的左子树的最大值如果大于V,那么答案就是Query(右子树的左子树)+右子树的贡献减去右子树的右子树的贡献,如果右子树的左子树的最大值小于左子树的最大值,那么就直接Query(右子树)  重复以上过程即可

 

#include <stdio.h>
#include<string.h>
#include<algorithm>
typedef long long ll;
#define maxn 100001
using namespace std;
int a[maxn];
struct node{
	int max1;
	int cnt;
}ans[maxn*4];
int Query(int rt,int V,int l,int r)
{
/*
	if(rt==9)
	printf("%d %d\n",l,r);*/
	if(l==r)
	{
		return ans[rt].max1>V;
	}
	if(ans[rt<<1].max1<V)
	{
		
		return Query(rt<<1|1,V,(l+r)/2+1,r);
	}	
	else
	{
		return (ans[rt].cnt-ans[rt<<1].cnt)+Query(rt<<1,V,l,(l+r)/2);
	}
}
void PushUp(int rt,int l,int r)
{
	//printf("->%d %d %d\n",rt,l,r);
	int ans1=0;
	ans1+=ans[rt<<1].cnt;
	if(ans[rt<<1].max1<ans[rt<<1|1].max1)
	ans1+=Query(rt<<1|1,ans[rt<<1].max1,(l+r)/2+1,r);
	//if(rt==4)printf("ans1=%d\n",ans1);
	
	ans[rt].cnt=ans1;
	ans[rt].max1=max(ans[rt<<1].max1,ans[rt<<1|1].max1);
}
void Build(int l,int r,int rt)
{ 
	if(l==r) 
	{
		ans[rt].max1=a[l];
		ans[rt].cnt=1;
		return ;
	}
	int m=(l+r)/2;
	Build(l,m,rt<<1);
	Build(m+1,r,rt<<1|1);
	PushUp(rt,l,r);
}
void Update(int L,int c,int l,int r,int rt)
{	
	//printf("-?>%d %d %d\n",rt,l,r);
	if(l==r)
	{
		ans[rt].max1=c;
		return ;
	}
	int m=(l+r)/2;
	if(L<=m)
	{
		Update(L,c,l,m,rt<<1);	
		
	}
	else
	{
		Update(L,c,m+1,r,rt<<1|1);
	}
		PushUp(rt,l,r);
}
int main(int argc, char *argv[])
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(a,0,sizeof(a));
		memset(ans,0,sizeof(ans));
		int n,m;
		scanf("%d %d",&n,&m);
		int i;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		Build(1,n,1);
	 /*
	for(i=1;i<=9;i++)
	 	{
	 		printf("%d %d %d\n",i,ans[i].max1,ans[i].cnt);
	 	}*/	
		while(m--)
		{
			int L,C;
			scanf("%d %d",&L,&C);	
			int next=a[L];
			Update(L,C,1,n,1);
			
	/*
	for(i=1;i<=9;i++)
	 	{
	 		printf("%d %d %d\n",i,ans[i].max1,ans[i].cnt);
	 	}*/	
			printf("%d\n",ans[1].cnt);
			Update(L,next,1,n,1); 
		}
	}
	return 0;
}