屠龙宝刀点击就送
题目描述 Description YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)
输入描述 Input Description 第 1 行: 用空格隔开的两个整数N和M 第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号(0代表按下开关，1代表询问状态), x 和 y
输出描述 Output Description 第 1..询问总次数 行:对于每一次询问，输出询问的结果
样例输入 Sample Input 4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4
样例输出 Sample Output 1 2
数据范围及提示 Data Size & Hint 一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)： XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4
线段树裸题， 代码↓
#include<iostream> #include<cstdio> using namespace std; typedef long long LL; const int MAXN = 100010; struct xds { int l, r, sum; bool add; }tree[MAXN << 2]; void update(int now) { tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum; } void pushdown(int now) { if(tree[now].add) { tree[now << 1].sum = tree[now << 1].r - tree[now << 1].l + 1 - tree[now << 1].sum; tree[now << 1].add =! tree[now << 1].add; tree[now << 1 | 1].sum = tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1 - tree[now << 1 | 1].sum; tree[now << 1 | 1].add = !tree[now << 1 | 1].add; tree[now].add = 0; } } void change(int now, int l, int r) { if(tree[now].l >= l && tree[now].r <= r) { tree[now].add = !tree[now].add; tree[now].sum = tree[now].r - tree[now].l + 1 - tree[now].sum; return ; } pushdown(now); int mid = (tree[now].l + tree[now].r) >> 1; if(l <= mid) { change(now << 1, l, r); } if(r > mid) { change(now << 1 | 1, l, r); } update(now); } int ask(int now, int l, int r) { if(tree[now].l >= l && tree[now].r <= r) { return tree[now].sum; } pushdown(now); int ans = 0; int mid = (tree[now].l + tree[now].r) >> 1; if(l <= mid) ans += ask(now << 1, l, r); if(r > mid) ans += ask(now << 1 | 1, l, r); return ans; } void build(int now, int l, int r) { tree[now].l = l; tree[now].r = r; if(l == r) return; int mid = (l + r) >> 1; build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r); } int main() { int n, m; scanf("%d%d", &n, &m); build(1, 1, n); int op, x, y; for(int i = 1; i <= m; i++) { scanf("%d%d%d", &op, &x, &y); if(op == 0) change(1, x, y); if(op == 1) printf("%d\n", ask(1, x, y)); } return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017073.html
