【题解】LOJ 2302 「NOI2017」整数

Problem

给定一个整数 $x$ ,刚开始是 $0$ ,有 $n$ 个操作:

  1. 1 a b :$x = x+a*2^b$
  2. 2 k :查询二进制下 $x$ 第 $k$ 位的值

Thought

法一

发现 $b$ 很大,达到 $3*10^7$ 级别,而 $a$ 仅有 $10^9$ 级别,也就是说不超过 $30$ 位

显然不能直接维护 $x$ 的
但是注意到每次新加数字有意义的仅有 $a$ ,而 $b$ 仅仅用来确定加的位置

考虑将 $a$ 拆成 $30$ 个形似于 $2^k$ 的数,分别加入
那么只需要维护 $x$ 中 $1$ 的位置

由于可能有连续的一段 $1$ ,这会导致插入的时候进位次数过多
那么直接维护一段连续的 $1$

利用有序的 map 即可(需要使用奇技淫巧保证 $log$ 次插入均摊 $O(1)$)

常数略大

法二

每一个位置压 $30$ 位,暴力就完事了

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
typedef unsigned int ui;
const int N = 1000020;

ui A[N], B[N];

ui ad[N];
ui bin[32];

int n;

set <int> S;
set <int> :: iterator it;

void add(int x) {
    A[x] += ad[x]; ad[x] = 0;
    while(A[x] >= bin[30]) {
        A[x] -= bin[30];
        ++ ad[x - 1];
    }
    if(A[x] != B[x]) 
        S.insert(x);
    if(A[x] == B[x])
        S.erase(x);
    -- x;
    while(ad[x]) {
        A[x] += ad[x]; ad[x] = 0;
        while(A[x] >= bin[30]) {
            A[x] -= bin[30];
            ++ ad[x - 1];
        }
        if(A[x] != B[x]) 
            S.insert(x);
        if(A[x] == B[x])
            S.erase(x);
        -- x;
    }
}
void del(int x) {
    B[x] += ad[x]; ad[x] = 0;
    while(B[x] >= bin[30]) {
        B[x] -= bin[30];
        ++ ad[x - 1];
    }
    if(A[x] != B[x]) 
        S.insert(x);
    if(A[x] == B[x])
        S.erase(x);
    -- x;
    while(ad[x]) {
        B[x] += ad[x]; ad[x] = 0;
        while(B[x] >= bin[30]) {
            B[x] -= bin[30];
            ++ ad[x - 1];
        }
        if(A[x] != B[x]) 
            S.insert(x);
        if(A[x] == B[x])
            S.erase(x);
        -- x;
    }
}
void solve(int a, int b) {
    int flag = 1;
    if(a < 0) {
        flag = 0;
        a = - a;
    }

    int k = 1000010;
    k -= b / 30; b %= 30;
    ad[k - 1] = (a >> (30 - b));
    ad[k] = ((a - (ad[k - 1] << (30 - b))) << b);

    if(flag)
        add(k);
    else
        del(k);
}
void query(int x) {
    int k = 1000010;
    k -= (x / 30);
    x %= 30;

    int num = 0;
    it = S.lower_bound(k + 1);

    if(it != S.end())
        if(A[*it] < B[*it])
            num = - 1;
    
    if((A[k] % bin[x + 1] + num - B[k] % bin[x + 1]) & bin[x])
        puts("1");
    else
        puts("0");
}

int main() {
    bin[0] = 1;
    for(int i = 1; i <= 30; ++ i)
        bin[i] = bin[i - 1] << 1;
    n = read(); read(); read(); read();
    for(int i = 1; i <= n; ++ i) {
        int opt = read();
        if(opt == 1) {
            int a = read(), b = read();
            solve(a, b);
        }
        else {
            int k = read();
            query(k);
        }
    }
    return 0;
}
Comments

添加新评论