T535928

分块写炸

玄关求调

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 100005;
int n, t;
vector<bool> isNormal(MAXN, true);
vector<int> blockSize(sqrt(MAXN) + 1, 0);
int blockCount; 
int blockSizeLimit; 
void update(int x) {
	int blockIndex = (x - 1) / blockSizeLimit; 
	if (isNormal[x]) {
		blockSize[blockIndex]--;
	} 
	else {
		blockSize[blockIndex]++;
	}
	isNormal[x] = !isNormal[x]; 
}
int query(int l, int r) {
	int result = 0;
	int startBlock = (l - 1) / blockSizeLimit; 
	int endBlock = (r - 1) / blockSizeLimit; 
	for (int i = startBlock + 1; i < endBlock; ++i) {
		result += blockSize[i];
	}
	for (int i = l; i <= min(r, startBlock * blockSizeLimit + blockSizeLimit - 1); ++i) {
		if (isNormal[i]) {
			result++;
		}
	}
	for (int i = max(l, endBlock * blockSizeLimit); i <= r; ++i) {
		if (isNormal[i]) {
			result++;
		}
	}
	return result;
}
int main() {
	cin >> n >> t;
	blockSizeLimit = sqrt(n);
	int tmp=sqrt(n);
	if(n%tmp==1) blockCount++;
	blockCount = (n + blockSizeLimit - 1) / blockSizeLimit; 
	for (int i = 0; i < n; ++i) {
		int blockIndex = (i - 1) / blockSizeLimit;
		blockSize[blockIndex]++;
	}
	for (int i = 0; i < t; ++i) {
		int op;
		cin >> op;
		if (op == 1) {
			int x;
			cin >> x;
			update(x);
		} 
		else {
			int l, r;
			cin >> l >> r;
			cout << query(l, r) << endl;
		}
	}
	return 0;
}