Luogu P2574 XOR的艺术 P3870 [TJOI2009]开关 P2846 [USACO08NOV]光开关Light Switching SP7259 LITE - Light Switching

四倍经验题

简单线段树qwq（那你怎么还调了好几个小时）

修改：\(ans[cur]=(r-l+1-ans[cur]);\)

点表示的区间有多长就是有多少盏灯 亮着的关掉 暗的开启 就是上述语句了。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

#define MAXN 200233

#define leftson cur<<1

#define rightson cur<<1|1

#define mid ((l+r)>>1)

#define ll long long

#define push_up ans[cur]=ans[leftson]+ans[rightson]

#define push_down add(cur,leftson,l,mid); add(cur,rightson,mid+1,r); tag[cur]=0

ll ans[MAXN<<2]={};

int tag[MAXN<<2]={};

//char c;

//void build(int cur,int l,int r)

//{

//	if (l==r)

//	{

//		cin>>c;

//		ans[cur]=c-'0';

////		printf("\n??::%lld",ans[cur]);

//		return;

//	}

//	build(leftson,l,mid);

//	build(rightson,mid+1,r);

//	push_up;

//}

inline void add(int delta,int cur,int l,int r)

{

	if (tag[delta])

	{

//		if(l==r)

//		{

//			printf("\n:::::::::%d's %lld\n",l,ans[cur]);

//		}

		ans[cur]=(r-l+1-ans[cur]);

		tag[cur]^=1;

	}

//	if (tag[cur]!=tag[delta])

//	{

//		printf("\n::%lld  %lld\n",(r-l+1),ans[cur]);

//		ans[cur]=(r-l+1-ans[cur]);

//		tag[cur]=tag[delta];

//	}

}

inline void change(int cur,int l,int r,int adl,int adr)

{

//	printf("\nm%d~~%d 's tag::%d\n",l,r,tag[cur]);

	if (adl<=l&&r<=adr)

	{

		ans[cur]=(r-l+1-ans[cur]);

		tag[cur]^=1;

		return;

	}

	push_down;

	if (adl<=mid) change(leftson,l,mid,adl,adr);

	if (adr>mid) change(rightson,mid+1,r,adl,adr);

	push_up;

}

ll query(int ql,int qr,int cur,int l,int r)

{

	if (ql<=l&&r<=qr)

	{

//		printf("sum::%d %d %lld\n",l,r,ans[cur/2]);

		return ans[cur];

//		printf("\n\n\n ONE::%lld\n\n\n",ans[cur]);

	}

	push_down;

	ll answer=0;

	if (ql<=mid)

	{

//		printf("\n\n\n TWO::%d\n\n\n",query(ql,qr,leftson,l,mid));

		answer+=query(ql,qr,leftson,l,mid);

	}

	if (qr>mid)

	{

//		printf("\n\n\n THREE::%d\n\n\n",query(ql,qr,rightson,mid+1,r));

		answer+=query(ql,qr,rightson,mid+1,r);

	}

	return answer;

}

int main()

{

	int n,m;

	int p,l,r;

	scanf("%d%d",&n,&m);

	getchar();

//	build(1,1,n);

	for (int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&p,&l,&r);

		if (!p)

		{

			change(1,1,n,l,r);

/*			printf("\ntree1::\n%lld\n",ans[1]);

			for (int j=2;j<=3;j++)

			{

				printf("%lld ",ans[j]);

			}

			printf("\n");

			for (int j=4;j<=7;j++)

			{

				printf("%lld ",ans[j]);

			}

			printf("\n\n");

			*/

//			printf("\ntree2::\n%lld\n",tag[1]);

//			for (int j=2;j<=3;j++)

//			{

//				printf("%lld ",tag[j]);

//			}

//			printf("\n");

//			for (int j=4;j<=7;j++)

//			{

//				printf("%lld ",tag[j]);

//			}

//			printf("\n\n");

//

//			for (int j=100;j<=200;j++)

//			{

//				printf("%d ",ans[j]);

//			}

			continue;

		}

		printf("%lld\n",query(l,r,1,1,n));

	}

	return 0;

}

Luogu P2574 XOR的艺术 P3870 [TJOI2009]开关 P2846 [USACO08NOV]光开关Light Switching SP7259 LITE - Light Switching的相关教程结束。