Luogu P5057 [CQOI2006]简单题

解析

• 简单的用树状数组或线段树处理，每次被修改的区间里的元素 +1 即可，最后判断这个点被修改奇数次还是偶数次即可

Code

法一(树状数组)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n,m,ctr[100005];
int lowbit(int u)
{
    return u&(-u);
}
void update(int u,int v)
{
    for(;u<=n;u+=lowbit(u)) ctr[u]+=v;
    return;
}
int query(int u)
{
    int res=0;
    for(;u;u-=lowbit(u)) res+=ctr[u];
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            update(x,1);
            update(y+1,-1);
        }
        if(opt==2)
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",query(x)&1);
        }
    }
    return 0;
}

法二(线段树)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int n,m;
struct Tree
{
    struct tree
    {
        int val,tag;
    }tr[400005];
    void pushup(int root)
    {
        tr[root].val=tr[root*2].val+tr[root*2+1].val;
        return;
    }
    void build(int root,int l,int r)
    {
        if(l==r)
        {
            tr[root].val=0;
            return;
        }
        int mid=(l+r)>>1;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        pushup(root);
        return;
    }
    void pushdown(int root,int l,int r)
    {
        if(tr[root].tag)
        {
            int mid=(l+r)>>1;
            tr[root*2].val+=(mid-l+1)*tr[root].tag;
            tr[root*2+1].val+=(r-mid)*tr[root].tag;
            tr[root*2].tag+=tr[root].tag;
            tr[root*2+1].tag+=tr[root].tag;
            tr[root].tag=0;
        }
        return;
    }
    void update(int root,int l,int r,int ll,int rr,int s)
    {
        if(ll<=l&&r<=rr)
        {
            tr[root].val+=(r-l+1)*s;
            tr[root].tag+=s;
            return;
        }
        pushdown(root,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll) update(root*2,l,mid,ll,rr,s);
        if(mid<rr) update(root*2+1,mid+1,r,ll,rr,s);
        pushup(root);
        return;
    }
    int query(int root,int l,int r,int ll,int rr)
    {
        if(ll<=l&&r<=rr) return tr[root].val;
        pushdown(root,l,r);
        int res=0,mid=(l+r)>>1;
        if(mid>=ll) res+=query(root*2,l,mid,ll,rr);
        if(mid<rr) res+=query(root*2+1,mid+1,r,ll,rr);
        return res;
    }
}str;
int main()
{
    scanf("%d%d",&n,&m);
    str.build(1,1,n);
    while(m--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            str.update(1,1,n,x,y,1);
        }
        if(opt==2)
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",str.query(1,1,n,x,x)&1);
        }
    }
    return 0;
}