【codevs1690】开关灯
2014年2月15日4930
题目描述 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<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int M = 2e5+;
int lazy[M<<],sum[M<<];
void pushup(int rt){
sum[rt] = sum[rt<<] + sum[rt<<|];
} void pushdown(int rt,int m){
if(lazy[rt]){
lazy[rt<<] += lazy[rt];
lazy[rt<<]%=;
lazy[rt<<|] += lazy[rt];
lazy[rt<<|]%=;
sum[rt<<] = (m-(m>>))-sum[rt<<];
sum[rt<<|] = (m>>)-sum[rt<<|];
lazy[rt] = ;
}
} void build(int l,int r,int rt){
lazy[rt] = ;
if(l == r){
sum[rt] = ;
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
pushup(rt);
} void update(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
lazy[rt]++;
lazy[rt]%=;
sum[rt] = (r-l+)-sum[rt];
return;
}
pushdown(rt,r-l+);
int m = (l + r)>>;
if(L <= m) update(L,R,lson);
if(R > m) update(L,R,rson);
pushup(rt);
} int query(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
return sum[rt];
}
pushdown(rt,r-l+);
int m = (l + r) >> ;
int ret = ;
if(L <= m) ret+=query(L,R,lson);
if(R > m) ret += query(L,R,rson);
return ret;
} int main()
{
ios::sync_with_stdio();
cin.tie();
cout.tie();
int n,m,x,y,f;
cin>>n>>m;
build(,n,);
while(m--){
cin>>f>>x>>y;
if(f==) update(x,y,,n,);
else cout<<query(x,y,,n,)<<endl;
}
}