题解 P3870 【[TJOI2009]开关】

这个题我愣是交了好几遍没有过......
后来@_皎月半洒花dalao告诉我说要^儿子节点的tag,然后就明白了......

行吧,先上题面:

题目描述

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

输入输出格式

输入格式:

第一行有两个整数N和M,分别表示灯的数目和操作的数目。接下来有M行,每行有三个整数,依次为:c, a, b。其中c表示操作的种类,当c的值为0时,表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界(1 ≤ a ≤ b ≤ N)。

输出格式:

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

这个题比较有好处的一点是有很多题都和这个题基本一样。
然后我们看到这个题让我们统计一个线段内的某一种和和修改区间:

线段树啊!

然后我就把校门外的树的代码扒过来了......
评测记录
后果:听取WA声一片。

为啥呢?

因为儿子节点有可能比父亲节点提前改过了。
所以我们只能取反,把原先的状态反过来。
然后就成了提交记录

#include <iostream>
#include <cstdio>

using namespace std;
const int maxn=100001;
struct tree{
    int l,r,flash,dark;
    bool tag;
}segment[maxn<<2];
int n,m;

inline void update(int rt);
inline void pushdown(int rt);
inline void build_tree(int rt,int l,int r);
inline int query(int rt,int l,int r);
inline void modify(int rt,int l,int r);

int main()
{
    cin>>n>>m;
    build_tree(1,1,n);
    while (m--)
    {
        char flag;
        int l,r;
        cin>>flag>>l>>r;
        if (flag=='0')modify(1,l,r);
        else cout<<query(1,l,r)<<'\n';
    }
    return 0;
}

inline void update(int rt)
{
    int lson=rt<<1,rson=lson+1;
    segment[rt].flash=segment[lson].flash+segment[rson].flash;
    segment[rt].dark=segment[lson].dark+segment[rson].dark;
}
inline void pushdown(int rt)
{
    int lson=rt<<1,rson=lson+1;
    segment[lson].tag^=1;
    segment[rson].tag^=1;
    swap(segment[lson].dark,segment[lson].flash);
    swap(segment[rson].dark,segment[rson].flash);
    segment[rt].tag^=1;
}
inline void build_tree(int rt,int l,int r)
{
    segment[rt].l=l,segment[rt].r=r;
    if (l==r)
    {
        segment[rt].flash=0;
        segment[rt].dark=1;
        segment[rt].tag=false;
        return;
    }
    int mid=(r+l)>>1,lson=rt<<1,rson=lson+1;
    build_tree(lson,l,mid);
    build_tree(rson,mid+1,r);
    update(rt);
}
inline void modify(int rt,int l,int r)
{
    if (segment[rt].l<=l&&segment[rt].r>=r)
    {
        if (segment[rt].l==l&&segment[rt].r==r)
        {
            segment[rt].tag^=1;
            swap(segment[rt].flash,segment[rt].dark);
            return;
        }
        if (segment[rt].tag)pushdown(rt);
        int mid=(segment[rt].l+segment[rt].r)>>1,lson=rt<<1,rson=lson+1;
        if (r<=mid)modify(lson,l,r);
        else if (l>mid)modify(rson,l,r);
        else
        {
            modify(lson,l,mid);
            modify(rson,mid+1,r);
        }
        update(rt);
    }
    return ;
}
inline int query(int rt,int l,int r)
{
    if (segment[rt].l<=l&&segment[rt].r>=r)
    {
        if (segment[rt].l==l&&segment[rt].r==r)
        {
            return segment[rt].flash;
        }
        if (segment[rt].tag)pushdown(rt);
        int mid=(segment[rt].l+segment[rt].r)>>1,lson=rt<<1,rson=lson+1;
        if (r<=mid)return query(lson,l,r);
        else if (l>=mid+1)return query(rson,l,r);
        else return query(lson,l,mid)+query(rson,mid+1,r);
    }
    return 0;
}

行吧......

上一篇:反转链表


下一篇:P3868 [TJOI2009]猜数字(CRT板子)