[Bzoj4942][Noi2017]整数（线段树）

4942: [Noi2017]整数

Time Limit: 50 Sec Memory Limit: 512 MB
Submit: 363 Solved: 237
[Submit][Status][Discuss]

Description

http://www.lydsy.com/JudgeOnline/upload/Noi2017D1.pdf

Input

Output

Sample Input

Sample Output

HINT

分析：

如果维护一个3*10^7次方的数组表示这个数，只有加法是很好办的，但是有减法的话就不好办了。所以维护两个3*10^7次方的数组，表示加法每一位是否是1减法每一位是否是1.

查询的时候高位是不关乎当前位的事，只关心当前位的加减法和低位中最高位加减法数组不同的两个位置，加减法不同的位置可以用线段树维护。

AC代码：

# include <iostream>

# include <cstdio>

using namespace std;

const int N =  << ;

const int mx =  << ;

bool Inc[N],Dec[N],t[N << ];

int l,r,n;

int read()

{

    int x = ,f = ;char i = getchar();

    while(!isdigit(i))f = i == '-' ? - : f,i = getchar();

    while(isdigit(i))x = x *  + i - '',i = getchar();

    return x * f;

}

void add(bool *c,int x)

{

    for(;c[x];c[x++] = );

    c[x] = ;

    if(x > r)r = x;

}

int find(int x)

{

    for(x += mx;x;x >>= )if(x &  & t[x ^ ])

    {

        for(x ^= ;x < mx;x = x <<  ^ t[x <<  | ]);

        return x - mx;

    }

    return -;

}

int main()

{

      int tp,x,y;n = read();read();read();read();

      while(n--)

      {

          tp = read();

          if(tp & )

          {

              x = read();y = read();

              if(!x)continue;

              l = r = y;tp = x >  ?  : ;x = x >  ? x : -x;

              if(tp){for(int i = ;i < ;i++)if(x >> i & )add(Inc,y + i);}

              else {for(int i = ;i < ;i++)if(x >> i & )add(Dec,y + i);}

              for(int i = l;i <= r;i++)t[i + mx] = Inc[i] ^ Dec[i];

              for(l = (l + mx) >> ,r = (r + mx) >> ;l;l >>= ,r >>= )

              for(int i = l;i <= r;i++)t[i] = t[i << ] | t[i <<  | ];

          }

          else

          {

              x = read();y = find(x);

              printf("%d\n",t[x + mx] ^ (~y && Inc[y] < Dec[y]) ?  : );

          }

      }

}

巴特西