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;
}
上一篇: 命题公式与真值表的应用
下一篇: 1026. 程序运行时间
推荐阅读
-
HDU6406 Taotao Picks Apples(2018HDU多校联赛第八场,线段树)
-
2018HDU多校8-1010-Taotao Picks Apples(hdu 6406)-线段树+预处理
-
【hdu 6406】Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples (线段树)
-
HDU 6406 Taotao Picks Apples
-
Taotao Picks Apples HDU - 6406
-
HDU 6406 Taotao Picks Apples
-
hdu 6406 Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples