分块是一种优雅的暴力。

题目描述

现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，......，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

原题链接

Slove

1. 将n盏灯的状态分块。1表示开着，0表示关着。
2. tg[]表示每个块的修改状态。
3. 通过“^”操作快速修改。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#define N 100001
using namespace std;
int n,m;
int t;
int ans;
int cnt,x,y;
struct note{
	int l,r,sum;
}d[N];
int num[N],tg[N];
int ln[N];
void ch(int l,int r){
	if(ln[l]==ln[r]){
		for(int i=l;i<=r;i++){
			d[ln[i]].sum-=(num[i]^tg[ln[i]]);
			num[i]=1-num[i];
			d[ln[i]].sum+=(num[i]^tg[ln[i]]);
		}
	}
	else{
		for(int i=l;i<=d[ln[l]].r;i++){
			d[ln[i]].sum-=(num[i]^tg[ln[i]]);
			num[i]=1-num[i];
			d[ln[i]].sum+=(num[i]^tg[ln[i]]);
		}
		for(int i=d[ln[r]].l;i<=r;i++){
			d[ln[i]].sum-=(num[i]^tg[ln[i]]);
			num[i]=1-num[i];
			d[ln[i]].sum+=(num[i]^tg[ln[i]]);
		}
		for(int i=ln[l]+1;i<=ln[r]-1;i++){
			tg[i]=1-tg[i];
			d[i].sum=(d[i].r-d[i].l+1)-d[i].sum;
		}
	}
}
int qu(int l,int r){
	if(ln[l]==ln[r]){
		for(int i=l;i<=r;i++) ans+=(num[i]^tg[ln[i]]);
		return ans;
	}
	else{
		for(int i=l;i<=d[ln[l]].r;i++) ans+=(num[i]^tg[ln[l]]);
		for(int i=d[ln[r]].l;i<=r;i++) ans+=(num[i]^tg[ln[r]]);
		for(int i=ln[l]+1;i<=ln[r]-1;i++){
			ans+=d[i].sum;
		}
		return ans;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	t=sqrt(n);
	for(int i=1;i<=t;i++){
		d[i].l=(i-1)*t+1;
		d[i].r=i*t;
	}
	if(d[t].r<n){
		t++;
		d[t].l=d[t-1].r+1;
		d[t].r=n;
	}
	int s=1;
	for(int i=1;i<=n;i++){
		if(d[s].r<i) s++;
		ln[i]=s;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&cnt,&x,&y);
		if(cnt){
			ans=0;
			printf("%d\n",qu(x,y));
		}
		else ch(x,y);
	}
	return 0; 
}

关于分块

没有学过分块的朋友可以康康hzw大神的分块九讲