Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma 线段树

题目链接

题目大意

给你一个1-n的区间 你要完成以下两种操作

1 将某个数改为某个数

2 判断l到r范围内有 多少个连续的不下降区间 如 345这个区间里有6个区间 （单个数字也算）

题目思路

两个区间合并后的答案数量变化 可以很轻易地想到只与两个区间相连部分是不是能相接组成一个更大的区间有关 可以很轻易想到用线段树操作

线段树里面 设 sum lm rm

sum代表这个区间里的答案数量

lm代表当前区间里从最左边开始最长的不下降子序列长度

rm代表当前区间里从最右边开始最长的不下降子序列长度

对于pushup操作

父节点的所有节点全部继承子节点

除非 左孩子的最右节点小于等于右节点的最左节点 我们姑且称这里为交界处

意味着 lm和rm有可能更新 sum一定会更新

更新条件取决于 例如： 左孩子节点的lm有没有到达交界处 右孩子也是如此

void pushup(ll x,ll l,ll r)
{
	ans[x].sum=ans[ls(x)].sum+ans[rs(x)].sum;
	ans[x].lm=ans[ls(x)].lm;
	ans[x].rm=ans[rs(x)].rm;
	ll mid=(l+r)/2;
	if(a[ans[ls(x)].r]<=a[ans[rs(x)].l])
	{
		if(ans[ls(x)].lm==mid-l+1)
		{
			ans[x].lm+=ans[rs(x)].lm;
		}
		if(ans[rs(x)].rm==r-mid)
		{
			ans[x].rm+=ans[ls(x)].rm;
		}
		ans[x].sum+=ans[ls(x)].rm*ans[rs(x)].lm;
	}
}

注意在query函数中 对于部分情况要特判

即当前覆盖范围 不严格包含于目标范围

但是交界处仍符合题意 仍需要计算部分的sum

注意这里的rm和lm不要超过目标范围长度

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,q;
ll a[maxn];
struct node{
	ll l,r,lm,rm;
	ll sum;
}ans[maxn*4];
ll ls(ll x)
{
	return x<<1;
}
ll rs(ll x)
{
	return x<<1|1;
}
void pushup(ll x,ll l,ll r)
{
	ans[x].sum=ans[ls(x)].sum+ans[rs(x)].sum;
	ans[x].lm=ans[ls(x)].lm;
	ans[x].rm=ans[rs(x)].rm;
	ll mid=(l+r)/2;
	if(a[ans[ls(x)].r]<=a[ans[rs(x)].l])
	{
		if(ans[ls(x)].lm==mid-l+1)
		{
			ans[x].lm+=ans[rs(x)].lm;
		}
		if(ans[rs(x)].rm==r-mid)
		{
			ans[x].rm+=ans[ls(x)].rm;
		}
		ans[x].sum+=ans[ls(x)].rm*ans[rs(x)].lm;
	}
}
void build(ll x,ll l,ll r)
{
	ans[x].l=l;
	ans[x].r=r;
	
	if(l==r)
	{
		ans[x].lm=1;
		ans[x].rm=1;
		ans[x].sum=1;
		return ;
	}
	ll mid=(l+r)/2;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x,l,r);
}
void updata(ll l,ll r,ll nl,ll nr,ll x,ll k)
{
	if(nl>=l&&nr<=r)
	{
		a[nl]=k;
		return ;
	}
	ll mid=(nl+nr)/2;
	if(mid>=l)updata(l,r,nl,mid,ls(x),k);
	if(mid<r)updata(l,r,mid+1,nr,rs(x),k);
	pushup(x,nl,nr);
}
ll query(ll l,ll r,ll nl,ll nr,ll x)
{
	if(nl>=l&&nr<=r)
	{
		return ans[x].sum;
	}
	//pushup(x,nl,nr);
	ll mid=(nl+nr)/2;
	ll num=0;
	if(mid>=l)
	{
		num+=query(l,r,nl,mid,ls(x));
	}
	if(mid<r)
	{
		num+=query(l,r,mid+1,nr,rs(x));
	}
	pushup(x,nl,nr);
	if(a[ans[ls(x)].r]<=a[ans[rs(x)].l])
	{
		ll lt=min(mid-l+1,ans[ls(x)].rm);
		ll rt=min(r-mid,ans[rs(x)].lm);
		if(lt>0&&rt>0)
		{
			num+=lt*rt;
		}
	}
	
	return num;
}
int main()
{
	//cin>>n>>q;
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		//cin>>a[i];
	} 
	build(1,1,n);
	ll t,l,r;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld %lld %lld",&t,&l,&r);
		if(t==1)
		{
			//cin>>l>>r;
			updata(l,l,1,n,1,r);
		}
		else 
		{
			//cin>>l>>r;
			//cout<<query(l,r,1,n,1)<<endl;
			printf("%lld\n",query(l,r,1,n,1));
		}
	} 
	return 0;
}