BZOJ4355: Play with sequence

https://lydsy.com/JudgeOnline/problem.php?id=4355

分析:

模板题。
把\(2\)操作看成先区间加再区间取\(max\)。
查询转化成求最小值个数。
需要维护\(3\)个标记。
这里我比较naive地维护了三个标记，多维护了一个最小值需要加的值。
然后下传的时候对左右儿子判断是否应该下传。
实际上不需要，直接修改最小值即可。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

using namespace std;

#define N 1200050

#define ls p<<1

#define rs p<<1|1

typedef long long ll;

const ll inf = 1ll<<60;

int n,m;

ll a[N],mn[N],ci[N],tag1[N],tag2[N],tag3[N];

int cnt[N],len[N];

void giv1(int p,ll v) {

	tag1[p]=v;

	tag2[p]=0;

	tag3[p]=0;

	mn[p]=v;

	ci[p]=inf;

	cnt[p]=len[p];

}

void giv2(int p,ll v) {

	tag2[p]+=v;

	mn[p]+=v;

	ci[p]+=v;

}

void giv3(int p,ll v) {

	tag3[p]+=v;

	mn[p]+=v;

}

void pushdown(int p) {

	if(tag1[p]!=-1) giv1(ls,tag1[p]),giv1(rs,tag1[p]),tag1[p]=-1;

	if(tag2[p]) giv2(ls,tag2[p]),giv2(rs,tag2[p]),tag2[p]=0;

	if(tag3[p]) {

		if(mn[ls]+tag3[p]==mn[p]) giv3(ls,tag3[p]);

		if(mn[rs]+tag3[p]==mn[p]) giv3(rs,tag3[p]);

		tag3[p]=0;

	}

}

void pushup(int p) {

	mn[p]=min(mn[ls],mn[rs]);

	if(mn[ls]==mn[rs]) ci[p]=min(ci[ls],ci[rs]),cnt[p]=cnt[ls]+cnt[rs];

	else {

		if(mn[ls]<mn[rs]) ci[p]=min(ci[ls],mn[rs]),cnt[p]=cnt[ls];

		else ci[p]=min(ci[rs],mn[ls]),cnt[p]=cnt[rs];

	}

}

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

	tag1[p]=-1;

	len[p]=r-l+1;

	if(l==r) {

		mn[p]=a[l];

		ci[p]=inf;

		cnt[p]=1;

		return ;

	}

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

	build(l,mid,ls); build(mid+1,r,rs);

	pushup(p);

}

void updadd(int l,int r,int x,int y,int v,int p) {

	if(x<=l&&y>=r) {

		giv2(p,v); return ;

	}

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

	pushdown(p);

	if(x<=mid) updadd(l,mid,x,y,v,ls);

	if(y>mid) updadd(mid+1,r,x,y,v,rs);

	pushup(p);

}

void updcov(int l,int r,int x,int y,int v,int p) {

	if(x<=l&&y>=r) {

		giv1(p,v); return ;

	}

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

	pushdown(p);

	if(x<=mid) updcov(l,mid,x,y,v,ls);

	if(y>mid) updcov(mid+1,r,x,y,v,rs);

	pushup(p);

}

void updmax(int l,int r,int x,int y,int p) {

	if(mn[p]>=0) return ;

	if(x<=l&&y>=r&&ci[p]>0) {

		giv3(p,-mn[p]); return ;

	}

	if(l==r) {giv1(p,0); return ;}

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

	pushdown(p);

	if(x<=mid) updmax(l,mid,x,y,ls);

	if(y>mid) updmax(mid+1,r,x,y,rs);

	pushup(p);

}

int query(int l,int r,int x,int y,int p) {

	if(x<=l&&y>=r) return (mn[p]==0)*cnt[p];

	int mid=(l+r)>>1,re=0;

	pushdown(p);

	if(x<=mid) re+=query(l,mid,x,y,ls);

	if(y>mid) re+=query(mid+1,r,x,y,rs);

	return re;

}

int main() {

	scanf("%d%d",&n,&m);

	int i,opt,x,y,z;

	for(i=1;i<=n;i++) scanf("%lld",&a[i]);

	build(1,n,1);

	while(m--) {

		scanf("%d%d%d",&opt,&x,&y);

		if(opt==1) {

			scanf("%d",&z);

			updcov(1,n,x,y,z,1);

		}else if(opt==2) {

			scanf("%d",&z);

			updadd(1,n,x,y,z,1);

			updmax(1,n,x,y,1);

		}else {

			printf("%d\n",query(1,n,x,y,1));

		}

	}

}

巴特西

BZOJ4355: Play with sequence

BZOJ4355: Play with sequence

最新文章

热门文章