超简单线段树求助
查看原帖
超简单线段树求助
158878
B1ade_楼主2022/12/18 22:18

RT,0pts WA 样例能过,求hack

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define MAXN 100005
using namespace std;
ll n,m;
il ll read()
{
	ll x=0,f=1;char c=getchar();
	while (!isdigit(c))
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while (isdigit(c))
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}
ll tr[MAXN<<2],tag[MAXN<<2];
il ll ls(ll x) {return x<<1;}
il ll rs(ll x) {return x<<1|1;}
il void pushup(ll x) {tr[x]=tr[ls(x)]+tr[rs(x)];}
il void change(ll x,ll l,ll r)
{
	tr[x]=(r-l+1)-tr[x];
}
il void pushdown(ll x,ll l,ll r)
{
	tag[ls(x)]=tag[x]%2;
	tag[rs(x)]=tag[x]%2;
	ll mid=(l+r)>>1;
	change(ls(x),l,mid);
	change(rs(x),mid+1,r);
	tag[x]=0;
}
il void modify(ll x,ll l,ll r,ll a,ll b)
{
	if (r<a||l>b) return;
	if (a<=l&&r<=b)
	{
		change(x,l,r);
		++tag[x];
		return;
	}
	if (tag[x]) pushdown(x,l,r);
	ll mid=(l+r)>>1;
	modify(ls(x),l,mid,a,b);
	modify(rs(x),mid+1,r,a,b);
	pushup(x);
}
il ll query(ll x,ll l,ll r,ll a,ll b)
{
	if (r<a||l>b) return 0;
	if (tag[x])
	pushdown(x,l,r);
	if (a<=l&&r<=b)
	{
		return tr[x];
	}
	ll mid=(l+r)>>1;
	return query(ls(x),l,mid,a,b)+query(rs(x),mid+1,r,a,b);
}
int main()
{
	n=read();m=read();
	for (ll i=1;i<=m;++i)
	{
		ll a=read(),b=read(),c=read();
		if (a==0) modify(1,1,n,b,c);
		else cout<<query(1,1,n,b,c)<<'\n';
	}
	return 0;
}
2022/12/18 22:18
加载中...