M_sea

洛谷3870 [TJOI2009]开关
题目描述现有N(2 ≤ N ≤ 100000)盏灯排成一排,从左到右依次编号为:1,2,......,N。然后依次...
扫描右侧二维码阅读全文
31
2018/07

洛谷3870 [TJOI2009]开关

题目描述

现有N(2 ≤ N ≤ 100000)盏灯排成一排,从左到右依次编号为:1,2,......,N。然后依次执行M(1 ≤ M ≤ 100000)项操作,操作分为两种:第一种操作指定一个区间[a, b],然后改变编号在这个区间内的灯的状态(把开着的灯关上,关着的灯打开),第二种操作是指定一个区间[a, b],要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

传送门

算法

维护一颗线段树。

首先将关闭定为0,打开定为1,那么一个区间内打开的灯的个数就是这个区间的和。

然后考虑修改。考虑打标记。对于一个区间,取反后再次取反等于没变,所以该标记只有两种状态,每次修改时^=1即可。

然而我把sum开成了bool,调了半天没调出来。。。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Segment_Tree {
    int sum[N<<2];
    bool rev[N<<2];
    
#define lson (o<<1)
#define rson (o<<1|1)
    
    inline void pushup(int o) { sum[o]=sum[lson]+sum[rson]; }
    inline void pushdown(int o,int L,int R) {
        if (rev[o]) {
            rev[lson]^=1;
            rev[rson]^=1;
            int mid=(L+R)>>1;
            sum[lson]=(mid-L+1)-sum[lson];
            sum[rson]=(R-mid)-sum[rson];
            rev[o]=0;
        }
    }
    
    inline void build(int o,int l,int r) {
        if (l==r) { sum[o]=rev[o]=0; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(o); rev[o]=0;
    }
    
    inline void update(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) {
            rev[o]^=1;
            sum[o]=(r-l+1)-sum[o];
            return;
        }
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        if (ql<=mid) update(lson,l,mid,ql,qr);
        if (mid<qr) update(rson,mid+1,r,ql,qr);
        pushup(o);
    }
    
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sum[o];
        pushdown(o,l,r);
        int mid=(l+r)>>1,rt=0;
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr);
        if (mid<qr) rt+=query(rson,mid+1,r,ql,qr);
        pushup(o);
        return rt;
    }
    
#undef lson
#undef rson

};

Segment_Tree SGT;

int main() {
    int n=read(),m=read();
    SGT.build(1,1,n);
    for (re int i=1;i<=m;i++) {
        int opt=read(),a=read(),b=read();
        if (opt==0) SGT.update(1,1,n,a,b);
        else if (opt==1) printf("%d\n",SGT.query(1,1,n,a,b));
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 53 PM

发表评论