2-1 月赛 T1 分析（别看）

科技起源

2026-07-08 15:04:33

发布于：河北

4阅读

0回复

0点赞

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个0/1的值

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 个城市，初始时全部让所有城市成为了A队的球迷
允许：每次会有一个事件，事件分两种

查询某个城市是哪队的球迷
将区间 $[l,r]$ 之间的城市都变成对方的球迷（A变B，B变A）

禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一些城市，初始时所有城市都是A队的球迷，接下来的每个操作，可能让你查询某个城市是哪队的球迷，也可能让你翻转某个区间里的球迷站边

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 分情况考虑

2.4 数学

奇偶性分析：
初始每个城市翻转次数就是 $0$
每将区间 $[i,j]$ 修改一次，就会使 $a_i,a_{i+1},\cdots,a_{j-1},a_j$ 所有城市的翻转次数 $+1$
最后，如果翻转次数是奇数，那就说明支持B，否则支持A（因为初始都支持A）

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：区间修改，单点查询 $\longrightarrow$ $\huge{树状数组}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1e5 + 10;
int tree[N];
int lowbit(int num){
	return num & (-num);
}
void add(int i, int num){
	int t = i;
	while(t <= n){
		tree[t] += num;
		t += lowbit(t); 
	}
	return ;
}
int get_sum(int r){
	if (r == 0){
		return 0;
	}
	return tree[r] + get_sum(r - lowbit(r));
}

int main(){
	
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		tree[i] = 0;
	}
	while(m--){
		int op;
		cin >> op;
		if (op == 1){
			int l, r;
			cin >> l >> r;
			add(l, 1);
            add(r + 1, -1);
		} else {
			int x;
			cin >> x;
			cout << get_sum(x) % 2 << endl;
		}
	}
	
	return 0;
}