动态开点线段树求条
查看原帖
动态开点线段树求条
926886
kind_Ygg楼主2024/10/14 08:51
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=15e6+5;
int n,q;
int x,y,k;
struct Tree
{
	int l,r,val,tag;
}tree[N];
int cnt=1;
void push_up(int s,int t,int p)
{
	tree[p].val=tree[tree[p].l].val+tree[tree[p].r].val;
	return;
}
void push_down(int s,int t,int p)
{
	if(!tree[p].l) tree[p].l=++cnt;
	if(!tree[p].r) tree[p].r=++cnt;
	if(tree[p].tag!=-1)
	{
		int mid=s+((t-s)>>1);
		tree[tree[p].l].tag=tree[p].tag;
		tree[tree[p].r].tag=tree[p].tag;
		tree[tree[p].l].val=tree[p].tag*(mid-s+1);
		tree[tree[p].r].val=tree[p].tag*(t-mid);
		tree[p].tag=-1;
	}
	return;
}
void update(int l,int r,int k,int s,int t,int p)
{
	if(l<=s and t<=r)
	{
		tree[p].tag=k;
		tree[p].val=(t-s+1)*k;
		return;
	}
	int mid=s+((t-s)>>1);
	push_down(s,t,p);
	if(l<=mid) update(l,r,k,s,mid,tree[p].l);
	if(mid+1<=r) update(l,r,k,mid+1,t,tree[p].r);
	push_up(s,t,p);
}
int query(int l,int r,int s,int t,int p)
{
	if(l<=s and t<=r) return tree[p].val;
	int mid=s+((t-s)>>1);
	push_down(s,t,p);
	int ans=0;
	if(l<=mid) ans+=query(l,r,s,mid,tree[p].l);
	if(mid+1<=r) ans+=query(l,r,mid+1,t,tree[p].r);
	return ans;
}
signed main()
{
	cin>>n>>q;
	while(q--)
	{
		cin>>x>>y>>k;
		if(k==1) update(x,y,1,1,n,1);
		else update(x,y,0,1,n,1);
		cout<<n-query(1,n,1,n,1)<<'\n';
	}
	return 0;
}
2024/10/14 08:51
加载中...