线段树黄题10pts求调
查看原帖
线段树黄题10pts求调
342494
wxh666楼主2023/6/26 14:04
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct x_trees{
	int l,r;
	int sum,lan=-1;
	int len;
}t[500005];
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	t[k].len=t[k].r-t[k].l+1;
	if(l==r) return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
inline void down(int k)
{
	if(t[k].lan==-1) return;
	t[k<<1].sum=t[k<<1].len*t[k].lan;
	t[k<<1|1].sum=t[k<<1|1].len*t[k].lan;
	t[k<<1].lan=t[k<<1|1].lan=t[k].lan;
	t[k].lan=-1;
}
void add(int k,int x,int y)
{
	if(t[k].l>y||t[k].r<x) return;
	if(t[k].l>=x&&t[k].r<=y&&(t[k].sum==t[k].len||t[k].sum==0))
	{
		int z;
		if(t[k].sum==0)
			z=1;
		else
			z=0;
		t[k].sum=t[k].sum*z;
		t[k].lan=z;
		return;
	}
	down(k);
	add(k<<1,x,y);
	add(k<<1|1,x,y);
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
int ask(int k,int x)
{
	if(t[k].l>x||t[k].r<x) return 0;
	if(t[k].l==t[k].r) return t[k].sum;
	down(k);
	return ask(k<<1,x)+ask(k<<1|1,x);
}
int n,m;
int op,x,y;
signed main()
{
	cin>>n>>m;
	build(1,1,n);
	while(m--)
	{
		scanf("%lld",&op);
		if(op==1)
		{
			scanf("%lld%lld",&x,&y);
			add(1,x,y);
		}
		else
		{
			scanf("%lld",&x);
			printf("%lld\n",ask(1,x));
		}
	}
	return 0;
}







2023/6/26 14:04
加载中...