codevs 1690 开关灯 线段树+延迟标记

1690 开关灯

 时间限制: 1 s

 空间限制: 128000 KB

题目描述 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

思路：线段树成段更新，每次一个区间改变为关灯的数量，每次模2即可；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=4e3+,M=1e6+,inf=1e9+;
int sum[M];
int flag[M];
void pushdown(int pos,int len)
{
    int lson=pos*;
    int rson=pos*+;
    if(flag[pos])
    {
        flag[lson]+=flag[pos];
        flag[lson]%=;
        flag[rson]+=flag[pos];
        flag[rson]%=;
        flag[pos]=;
        sum[lson]=(len-(len>>))-sum[lson];
        sum[rson]=(len>>)-sum[rson];
    }
}
void buildtree(int l,int r,int pos)
{
    if(l==r)
    {
        sum[pos]=;
        flag[pos]=;
        return;
    }
    int mid=(l+r)>>;
    buildtree(l,mid,pos*);
    buildtree(mid+,r,pos*+);
}
int query(int L,int R,int l,int r,int pos)
{
    if(L<=l&&r<=R)
    return sum[pos];
    pushdown(pos,(r-l+));
    int mid=(l+r)>>;
    int ans=;
    if(L<=mid)ans+=query(L,R,l,mid,pos*);
    if(mid<R)ans+=query(L,R,mid+,r,pos*+);
    return ans;
}
void update(int L,int R,int change,int l,int r,int pos)
{
    if(L<=l&&r<=R)
    {
        flag[pos]+=change;
        flag[pos]%=;
        sum[pos]=(r-l+)-sum[pos];
        return;
    }
    pushdown(pos,r-l+);
    int mid=(l+r)/;
    if(L<=mid)update(L,R,change,l,mid,pos*);
    if(R>mid)update(L,R,change,mid+,r,pos*+);
    sum[pos]=sum[pos*]+sum[pos*+];
}
int main()
{
    int x,y,z,i,t;
    while(~scanf("%d%d",&x,&y))
    {
        for(i=;i<y;i++)
        {
            int flag,l,r;
            scanf("%d%d%d",&flag,&l,&r);
            if(flag)
            {
                printf("%d\n",query(l,r,,x,));
            }
            else
            {
                update(l,r,,,x,);
            }
        }
    }
    return ;
}