蒟蒻10分求助,其他点全WA
查看原帖
蒟蒻10分求助,其他点全WA
294736
bovine__kebi楼主2020/4/30 16:52

蒟蒻最近迷上了线段树,但是做一次错一次/kk

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
int In[maxn];
struct node
{
	int l,r;
	ll sum;int flag;
}tree[maxn*4];
int n,m;
inline int ls(int i){return i<<1;}
inline int rs(int i){return i<<1|1;}
inline void pushup(int i)
{
	tree[i].sum=tree[ls(i)].sum+tree[rs(i)].sum;
}
inline void pushdown(int i)
{
	if(tree[i].flag==0)return;
	tree[ls(i)].sum=tree[ls(i)].r-tree[ls(i)].l+1-tree[i].sum;
	tree[rs(i)].sum=tree[rs(i)].r-tree[rs(i)].l+1-tree[i].sum;
	tree[ls(i)].flag^=1;
	tree[rs(i)].flag^=1;
	tree[i].flag=0;
}
inline void build(int i,int l,int r)
{
	tree[i].l=l;tree[i].r=r;
	if(l==r){tree[i].sum=In[l];return;}
	int mid=(l+r)>>1;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	pushup(i);
}
inline void change(int i,int l,int r)
{
	if(tree[i].l>r||tree[i].r<l)return;
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum=tree[i].r-tree[i].l+1-tree[i].sum;
		tree[i].flag^=1;
		return;
	}
	pushdown(i);
	if(tree[ls(i)].r>=l)change(ls(i),l,r);
	if(tree[rs(i)].l<=r)change(rs(i),l,r);
	pushup(i);
}
inline ll get(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;
	pushdown(i);
	ll ans=0;
	if(tree[ls(i)].r>=l)ans+=get(ls(i),l,r);
	if(tree[rs(i)].l<=r)ans+=get(rs(i),l,r);
	return ans; 
}
int main()
{
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int cz,l,r;
		scanf("%d %d %d",&cz,&l,&r);
		if(cz==0)change(1,l,r);
		if(cz==1)printf("%lld\n",get(1,l,r));
	}
	return 0;
}
2020/4/30 16:52
加载中...