题目描述 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
2
数据范围及提示 Data Size & Hint
一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)：
XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4
题意：中文题意
题解：裸的线段树 区间更新 区间查询求和 如果直接更新到叶子节点 线段树就会退化
lazy 延迟标记 因为只有开灯与关灯两种状态 所以可以%2处理 将累计起来的add %2处理
只有当add%2==1时间 才需要向下延迟 并更新下一层的add
卡这里卡了很久ORZZZZ
//code by drizzle
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define ll __int64
#define PI acos(-1.0)
#define mod 1000000007
using namespace std;
int n,m;
int flag,x,y;
struct node
{
int l;
int r;
int add;
int sum;
}tree[];
void buildtree(int root,int left,int right)
{
tree[root].l=left;
tree[root].r=right;
tree[root].add=;
if(left==right)
{
tree[root].sum=;
return;
}
int mid=(left+right)>>;
buildtree(root<<,left,mid);
buildtree(root<<|,mid+,right);
tree[root].sum=tree[root<<].sum+tree[root<<|].sum;
}
void pushdown(int root,int m)
{
tree[root<<].add++;
tree[root<<].add=tree[root<<].add%;
tree[root<<|].add++;
tree[root<<|].add=tree[root<<|].add%;
tree[root<<].sum=(m-(m>>))-tree[root<<].sum;
tree[root<<|].sum=(m>>)-tree[root<<|].sum;
tree[root].add=;
}
void updata(int c,int left,int right,int root)
{
if(tree[root].l==left&&tree[root].r==right)
{
tree[root].add++;
tree[root].add=tree[root].add%;
tree[root].sum=right-left+-tree[root].sum;
return ;
}
if(tree[root].l==tree[root].r)
return ;
if(tree[root].add)
pushdown(root,tree[root].r-tree[root].l+);
int mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
updata(c,left,right,root<<);
else
{
if(left>mid)
updata(c,left,right,root<<|);
else
{
updata(c,left,mid,root<<);
updata(c,mid+,right,root<<|);
}
}
tree[root].sum=tree[root<<].sum+tree[root<<|].sum;
}
int query(int root ,int left,int right)
{
if(tree[root].l==left&&tree[root].r==right)
{
return tree[root].sum;
}
if(tree[root].add)
pushdown(root,tree[root].r-tree[root].l+);
int mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
return query(root<<,left,right);
else
{
if(left>mid)
return query(root<<|,left,right);
else
return (query(root<<,left,mid)+query(root<<|,mid+,right));
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
buildtree(,,n);
for(int i=;i<=m;i++)
{
scanf("%d %d %d",&flag,&x,&y);
if(flag==)
{
updata(,x,y,);
}
else
{
printf("%d\n",query(,x,y));
}
}
}
return ;
}