CF915E 动态开线段树

因为\(n\le10^9\)，所以动态开点，线段树维护\([1,n]\)天非工作日数量。

之前的结构体写法被卡了，只能改成函数传l,r（虽然也不难）

动态开点好写，但是太菜了线段树部分写炸了，对lazy标记理解不深，下放标记时注意不要把本来子区间的信息覆盖了，下放完标记后要把标记复原。

#include <cstdio>

#define MAXN 15001000

#define mid ((xl+xr)>>1)

using namespace std;

int n,q;

int tot;

struct nod{

	int sl,sr,val;

	int lazy;

} tre[MAXN];

void build_nod(int &x, int l, int r, bool unwork){

	x=++tot;

	if(unwork) tre[x].val=r-l+1,tre[x].lazy=1;

	else tre[x].val=0,tre[x].lazy=-1;

}

void push_down(int x, int xl, int xr){

	if(tre[x].lazy==0) return;

	if(tre[x].lazy==1){

		if(tre[x].sl==0) build_nod(tre[x].sl, xl, mid, 1);

		else tre[tre[x].sl].val=(mid)-(xl)+1,tre[tre[x].sl].lazy=1;

		if(tre[x].sr==0) build_nod(tre[x].sr, mid+1, xr, 1);

		else tre[tre[x].sr].val=(xr)-(mid+1)+1,tre[tre[x].sr].lazy=1;

	}else{

		if(tre[x].sl==0) build_nod(tre[x].sl, xl, mid, 0);

		else tre[tre[x].sl].val=0,tre[tre[x].sl].lazy=-1;

		if(tre[x].sr==0) build_nod(tre[x].sr, mid+1, xr, 0);

		else tre[tre[x].sr].val=0,tre[tre[x].sr].lazy=-1;

	}

	tre[x].lazy=0;

}

void change(int &x, int xl, int xr, int l, int r, bool unwork){

	if(x==0){

		build_nod(x, l, r, unwork);

		return;

	}

	if(l<=xl&&xr<=r){

		if(unwork) tre[x].val=xr-xl+1,tre[x].lazy=1;

		else tre[x].val=0,tre[x].lazy=-1;

		return;

	}

	push_down(x, xl, xr);

	if(l<=mid) change(tre[x].sl, xl, mid,l, r, unwork);

	if(mid<r) change(tre[x].sr, mid+1, xr, l, r, unwork);

	tre[x].val=tre[tre[x].sl].val+tre[tre[x].sr].val;

}

int main()

{

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

	int root=0;

	change(root, 1, n, 1, n, 0);

	while(q--){

		int l,r,k;

		scanf("%d %d %d", &l, &r, &k);

		if(k==1) change(root, 1, n, l, r, 1);

		else change(root, 1, n, l, r, 0);

		printf("%d\n", n-tre[root].val);

	}

	return 0;

}

巴特西

CF915E 动态开线段树

CF915E 动态开线段树

最新文章

热门文章