分块萌新错了,求帮忙差错qwq
查看原帖
分块萌新错了,求帮忙差错qwq
117662
那一条变阻器楼主2020/6/11 20:44

才学分块,做的第一道题,错了,求dalao帮忙查下错啊qwq

#include <bits/stdc++.h>
using namespace std;
int n , m , sq;
int a[100010] , f[100010] , tag[10010] , ans[10010];
void work(int x , int y){
	for(int i = x; i <= min(y , f[x] * sq); i++){
		if(a[i] % 2) ans[f[x]]--;
		else ans[f[x]]++;
		a[i]++;
	}
	if(f[x] != f[y]) 
		for(int i = (f[y] - 1) * sq + 1; i <= y; i++){
			if(a[i] % 2) ans[f[y]]--;
			else ans[f[y]]++;
			a[i]++;
		}
	for(int i = f[x] + 1; i <= f[y] - 1; i++){
		ans[i] -= sq;
		ans[i] = abs(ans[i]);
		tag[i]++;
	}
}
int sum(int x , int y){
	int k = 0;
	for(int i = x; i <= min(y , f[x] * sq); i++) if((a[i] + tag[f[x]]) % 2) k++;
	if(f[x] != f[y]) for(int i = (f[y] - 1) * sq + 1; i <= y; i++) if((a[i] + tag[f[y]]) % 2) k++;
	for(int i = f[x] + 1; i <= f[y] - 1; i++) k += ans[i];
	return k;
}
int main(){
	cin >> n >> m;
	sq = sqrt(n);
	for(int i = 1; i <= n; i++) f[i] = (i - 1) / sq + 1;
	while(m--){
		int x , y;
		cin >> x;
		if(!x){
			cin >> x >> y;
			work(x , y);
		}else{
			cin >> x >> y;
			cout << sum(x , y) << endl;
		}
	}
	return 0;
}
/*
11 5
0 3 8
0 5 10
1 6 11
0 1 5
1 3 10
2
3
110 101 001 10
*/
2020/6/11 20:44
加载中...