「CQOI 2006」简单题

简单题

题目背景

CQOI2006 T1

题目描述

有一个 n 个元素的数组,每个元素初始均为 0 。有 m 条指令,要么让其中一段连续序列数字反转——0 变 1,1 变 0(操作1),要么询问某个元素的值(操作2)。例如当 n=20 时,10 条指令如下:

输入格式

输入文件第一行包含两个整数 n,m,表示数组的长度和指令的条数,以下 m 行,每行的第一个数 t 表示操作的种类。若 t=1,则接下来有两个数 L, R (L<=R),表示区间 [L, R] 的每个数均反转;若 t=2,则接下来只有一个数 I,表示询问的下标。

输出格式

每个操作 2 输出一行(非0即1),表示每次操作 2 的回答。

样例数据 1

输入

1
2
3
4
5
6
7
8
9
10
11
20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

输出

1
2
3
4
5
6
1
0
0
0
1
1

备注

【数据范围】

50% 的数据满足:1 \leq n \leq 1,000,1 \leq m \leq 10,000
100% 的数据满足:1 \leq n \leq 100,000,1 \leq m \leq 500,000

分析

线段树裸题,同前一道题(系列操作II)。
这里附上我的线段树模板…

源码+模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#define MAX_N 100010
using namespace std;
char ch_buffer;
bool signum;
inline void readInt(int &l) {
l = 0;
do
ch_buffer = cin.get();
while ((ch_buffer < '0' || ch_buffer > '9') && ch_buffer != '0' &&
ch_buffer != '-');
if (ch_buffer == '-') ch_buffer = cin.get(), signum = true;
while (ch_buffer <= '9' && ch_buffer >= '0')
l = (l << 3) + (l << 1) + ch_buffer - '0', ch_buffer = cin.get();
if (signum) l = -l, signum = false;
}
/*************************SegmentTree***************************/
/**
*SegmentTree
*created by xehoth 19/07/2016
*@author xehoth
*/
template <class T>
class SegmentTree {
public:
int capacity;
struct node {
T sum_val;
int tag;
node() : sum_val(0), tag(0) {}
};
node *segNode;
inline void updata(int v) {
segNode[v].sum_val =
segNode[v << 1].sum_val + segNode[v << 1 | 1].sum_val;
}
inline void downtag(int v, int s, int t) {
segNode[v << 1].tag += segNode[v].tag;
segNode[v << 1 | 1].tag += segNode[v].tag;
int mid = (s + t) >> 1;
segNode[v << 1].sum_val += segNode[v].tag * (mid - s + 1);
segNode[v << 1 | 1].sum_val += segNode[v].tag * (t - mid);
segNode[v].tag = 0;
}
void modify(int v, int s, int t, int l, int r, T x) {
if (s >= l && t <= r) {
segNode[v].tag += x;
segNode[v].sum_val += x * (t - s + 1);
return;
}
int mid = (s + t) >> 1;
downtag(v, s, t);
if (mid >= l) modify(v << 1, s, mid, l, r, x);
if (mid + 1 <= r) modify(v << 1 | 1, mid + 1, t, l, r, x);
updata(v);
}
inline T get(int v, int s, int t, int l, int r) {
return getSum(v, s, t, l, r);
}
T getSum(int v, int s, int t, int l, int r) {
if (s >= l && t <= r) return segNode[v].sum_val;
int mid = (s + t) >> 1;
T ans = 0;
downtag(v, s, t);
if (mid >= l) ans += getSum(v << 1, s, mid, l, r);
if (mid + 1 <= r) ans += getSum(v << 1 | 1, mid + 1, t, l, r);
updata(v);
return ans;
}
SegmentTree(int n) : capacity(n << 2), segNode(new node[capacity]){};
~SegmentTree() { delete[] segNode; };
};
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
readInt(n), readInt(m);
SegmentTree<int> st(n + 10);
int l, r, p;
while (m--) {
if (cin.get() ^ '2') {
readInt(l), readInt(r);
st.modify(1, 1, n, l, r, 1);
} else {
readInt(p);
cout << st.get(1, 1, n, p, p) % 2 << "\n";
}
}
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×