洛谷P3870题解

传送锚点

摸鱼环节

[TJOI2009] 开关

题目描述

现有 \(n\) 盏灯排成一排，从左到右依次编号为：\(1\)，\(2\)，……，\(n\)。然后依次执行 \(m\) 项操作。

操作分为两种：

1. 指定一个区间 \([a,b]\)，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 \([a,b]\)，要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

输入格式

第一行有两个整数 \(n\) 和 \(m\)，分别表示灯的数目和操作的数目。

接下来有 \(m\) 行，每行有三个整数，依次为：\(c\)、\(a\)、\(b\)。其中 \(c\) 表示操作的种类。

• 当 \(c\) 的值为 \(0\) 时，表示是第一种操作。
• 当 \(c\) 的值为 \(1\) 时，表示是第二种操作。

\(a\) 和 \(b\) 则分别表示了操作区间的左右边界。

输出格式

每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

样例 #1

样例输入 #1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

样例输出 #1

1
2

提示

数据规模与约定

对于全部的测试点，保证 \(2\le n\le 10^5\)，\(1\le m\le 10^5\)，\(1\le a,b\le n\)，\(c\in\{0,1\}\)。

又是一年春好处，在下不会线段树。

窝又写题解了。由于考虑到线段树的暴力骗分性实用性，于是我决定好好写棵线段树。(不得不说代码还是挺长的)

正片开始

1.建树。

当然不是所有题都需要建树的环节，但咱当模板来练就建一下。

1. 需要递归的元素(根节点\(rt\)，左端点\(l\)，右端点\(r\))。
2. 递归过程非常简单，在\(l==r\)时递归出口，其他的取中点对两边递归即可。

code：

void build(int rt,int l,int r)
{
    if(l==r){tree[rt]=0;return;}
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    up(rt);//向上更新
}

2.向上更新

对于每次的修改，我们都需要对线段树进行更新。于是：

code：

void up(int rt){ tree[rt]=tree[rt<<1]+tree[rt<<1|1];}

3.标记下传

懒标记是线段树很重要的一部分，也是线段树的核心部分，在标记下传的时候我们处理区间维护值的更新：

code：

void down(int rt,int l,int r)
{
    if(lazy[rt]==0) return;//无需更新
    lazy[rt<<1]^=1,lazy[rt<<1|1]^=1;//标记更新
    int mid=(l+r)>>1;
    tree[rt<<1]=(mid-l+1)-tree[rt<<1];
    tree[rt<<1|1]=(r-mid)-tree[rt<<1|1];//处理树上维护数值的更新
    lazy[rt]=0;//标记清空
}

4.更新处理

对于更新操作，我们需要找到一个区间\([l,r]\)刚好与区间\([L,R]\)重合，同样也是分为左右两个子区间进行递归处理。

code：

void update(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){tree[rt]=(r-l+1)-tree[rt];lazy[rt]^=1;return;}//找到合法区间
    down(rt,l,r);//标记下传
    int mid=(l+r)>>1;
    if(L<=mid) update(rt<<1,l,mid,L,R);
    if(R>mid) update(rt<<1|1,mid+1,r,L,R);//递归处理两个区间
    up(rt);//更新树
}

5.询问操作

和更新操作类似，这里不做说明。

code：

int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){ return tree[rt];}//找到结果
    down(rt,l,r);//下传标记
    int mid=(l+r)>>1,a=0,b=0;
    if(L<=mid) a=query(rt<<1,l,mid,L,R);
    if(R>mid) b=query(rt<<1|1,mid+1,r,L,R);
    return a+b;
}

警钟敲爆：不要忘记标记下传和向上更新。

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int tree[N<<2],lazy[N<<2],n,m,a[N];
void up(int rt){ tree[rt]=tree[rt<<1]+tree[rt<<1|1];}
void build(int rt,int l,int r)
{
    if(l==r){tree[rt]=0;return;}
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    up(rt);
}
void down(int rt,int l,int r)
{
    if(lazy[rt]==0) return;
    lazy[rt<<1]^=1,lazy[rt<<1|1]^=1;
    int mid=(l+r)>>1;
    tree[rt<<1]=(mid-l+1)-tree[rt<<1];
    tree[rt<<1|1]=(r-mid)-tree[rt<<1|1];
    lazy[rt]=0;
}
void update(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){tree[rt]=(r-l+1)-tree[rt];lazy[rt]^=1;return;}
    down(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) update(rt<<1,l,mid,L,R);
    if(R>mid) update(rt<<1|1,mid+1,r,L,R);
    up(rt);
}
int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){ return tree[rt];}
    down(rt,l,r);
    int mid=(l+r)>>1,a=0,b=0;
    if(L<=mid) a=query(rt<<1,l,mid,L,R);
    if(R>mid) b=query(rt<<1|1,mid+1,r,L,R);
    return a+b;
}
int main()
{
    int n,m;
    cin>>n>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int c,a,b;cin>>c>>a>>b;
        if(c==0) update(1,1,n,a,b);
        else cout<<query(1,1,n,a,b)<<endl;
    }
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)