题目内容

P5051

大意:维护一个初始为 0 的 0-1 序列,支持单点查询和区间取反操作

解题思路

这题可以使用线段树,但是为了减少码量可以使用树状数组,具体的思路是这样的:

由于每对一个区间取反一次,就相当于在这个区间加了 1,然后查询的时候相当于这个点是偶数就是 0,是奇数就是 1,这就将问题转化为了树状数组的区间修改单点查询——维护一个差分序列即可。

然后就过去了,跑的速度也是比较快的,而且比线段树好写简直不要太多

#include <cstdio>
#define lowbit(x) (x&-x)

const int maxn=1e5+5;
int n,m;
int t[maxn];

void add(int x,int d)
{
    while(x<=n)
    {
        t[x]+=d;
        x+=lowbit(x);
    }
    return;
}

bool query(int x)//查询操作,单点查询区间和并转化为 0-1 值
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans&1;//在这里转化
}

int main()
{
    scanf("%d %d",&n,&m);
    int c,x,y;
    while(m--)
    {
        scanf("%d %d",&c,&x);
        if(c==1)
        {
            scanf("%d",&y);
            add(x,1);
            add(y+1,-1);
        }
        else
            printf("%d\n",query(x));
    }
    return 0;
}
最后修改日期:2020年3月10日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。