2019.9.4 简单题

qxds 2019-09-04 原文

没错你没看错它真的叫简单题

不信你看

题目描述

有一个 n 个元素的数组，每个元素初始均为 0。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1 变 0（操作 1），要么询问某个元素的值（操作 2）。例如当 n = 20 时，10 条指令如下：

输入格式

第一行包含两个整数 n, m，表示数组的长度和指令的条数；以下 m 行，每行的第一个数 t 表示操作的种类：

若 t = 1，则接下来有两个数 L, R，表示区间 [L, R] 的每个数均反转；若 t = 2，则接下来只有一个数 i，表示询问的下标。

输出格式

每个操作 2 输出一行（非 0 即 1），表示每次操作 2 的回答。

输入输出样例

输入 #1

输出 #1

说明/提示

对于 50% 的数据，1 ≤ n ≤ $10^3103, 1 ≤ m ≤ 10^4104；对于 100% 的数据，1 ≤ n ≤ 10^5105, 1 ≤ m ≤ 5 × 10^5105，保证 L ≤ R。$

题源CQOI2006/洛谷P5057

和那个校门外的树一个原理只不过这个题是区间修改单点查询

同样用括号序列的方法对于每个点看作长度为1的区间即可

注意修改一次变成1 两次变成0

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
int n,m,t,ll,rr,xx,l[1000050],r[1000050];
void updatal(int i,int x)
{
    while(i<=n)
    {
        l[i]+=x;
        i+=lowbit(i);
    }
}
void updatar(int i,int x)
{
    while(i<=n)
    {
        r[i]+=x;
        i+=lowbit(i);
    }
}
int queryl(int i)
{
    int res=0;
    while(i>=1)
    {
        res+=l[i];
        i-=lowbit(i);
    }
    return res;
}
int queryr(int i)
{
    int res=0;
    while(i>=1)
    {
        res+=r[i];
        i-=lowbit(i);
    }
    return res;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&t);
        if(t==1)
        {
            scanf("%lld%lld",&ll,&rr);
            updatal(ll,1);
            updatar(rr,1);
        }
        if(t==2)
        {
            scanf("%lld",&xx);
            printf("%lld\n",(queryl(xx)-queryr(xx-1))%2);
        }
    }
    return 0;
}