【悬赏关注】动态开店线段树全输出n求调
查看原帖
【悬赏关注】动态开店线段树全输出n求调
999274
CNS_5t0_0r2楼主2023/11/17 15:22
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int read(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c))
		c = getchar();
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x;
}
int n,q;
struct node{
	int val,tag,lchild,rchild;
} tree[N << 4];
int cnt;
void push_up(int root){
	tree[root].val = tree[tree[root].lchild].val + tree[tree[root].rchild].val;
}
int new_node(int val = 0,int tag = -1){
	cnt++;
	tree[cnt] = (node){val,tag,0,0};
	return cnt;
}
int len(int l,int r){
	return r - l + 1;
}
bool in_range(int l,int r,int now_l,int now_r){
	return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
	return now_l < l || now_r > r;
}
void make_tag(int root,int tag,int l,int r){
	tree[root].tag = tag;
	tree[root].val = tag * len(l,r);
}
void push_down(int root,int l,int r){
	if(tree[root].tag == -1)
		return;
	int mid = (l + r) >> 1;
	make_tag(tree[root].lchild,tree[root].tag,l,mid);
	make_tag(tree[root].rchild,tree[root].tag,mid + 1,r);
	tree[root].tag = -1;
}
void update(int root,int l,int r,int now_l,int now_r,int v){
	if(in_range(l,r,now_l,now_r)){
		make_tag(root,v,now_l,now_r);
		return;
	}
	int mid = (now_l + now_r) >> 1;
	if(!out_range(l,r,now_l,now_r)){
		if(!tree[root].lchild)
			tree[root].lchild = new_node();
		if(!tree[root].rchild)
			tree[root].rchild = new_node();
		push_down(root,now_l,now_r);
		update(tree[root].lchild,l,r,now_l,mid,v);
		update(tree[root].rchild,l,r,mid + 1,now_r,v);
		push_up(root);
	}
}
int main(){
	n = read();q = read();
	new_node(n);
	for(;q;q--){
		int l = read(),r = read(),k = read();
		if(k == 1)
			update(1,l,r,1,n,0);
		else
			update(1,l,r,1,n,1);
		printf("%d\n",tree[1].val);
	}
	return 0;
}
2023/11/17 15:22
加载中...