https://loj.ac/problem/10117

题目描述

??给出一个长度为\(n\)的\(0、1\)数组，要求维护两个操作：\(①\)翻转区间\([l,r]\);\(②\)求这个序列第\(i\)个位置的值。

思路

??这里询问是单点询问，所以我们不用写线段树来维护\(reverse\)操作。考虑一个更简单的方法，我们维护一个数组\(a\)，\(a_i\&1\)就是实际的\(0、1\)序列，由于我们知道一个数加\(1\)奇偶性必定改变，所以我们只要对区间\([l,r]\)整体加\(1\)就行了，用前缀和维护区间修改即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}

int c[N],n;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int w)
{
    while(x<=n)
    {
        c[x]+=w;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

int main() 
{
    int m;
    n=read();m=read();
    while(m--)
    {
        int t=read();
        if(t==1)
        {
            int l=read(),r=read();
            add(l,1);add(r+1,-1);
        }
        else
        {
            int i=read();
            putchar((query(i)&1)+'0');
            putchar('\n');
        }
    }
}

简单题

原文：https://www.cnblogs.com/fangbozhen/p/11755362.html