[ABC261E] Many Operations Solution

• [ABC261E] Many Operations Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定正整数 $ X $，给定 $ n $ 条运算，每条包含 $ T_i, A_i $，代表若：

$ T_i = 1 $，则 $ X \leftarrow X \land A_i $。

$ T_i = 2 $，则 $ X \leftarrow X \lor A_i $。

$ T_i = 3 $，则 $ X \leftarrow X \oplus A_i $。

对于第 $ i $ 条运算，会顺序执行 $ [1, i] $ 的所有运算，求最终 $ X $ 的值。

Solution

发现这个执行类似前缀和，但对于不同的初始的数执行这些按位操作的时候结果是不同的，或者说其不能直接合并，所以不能一般地做前缀和。

不难发现按位运算的性质，即每一位之间都是独立的，不会像加法那样由进位操作，所以不难想到对于每一位分开考虑，显然初始时对应位只能为 $ 0 $ 或 $ 1 $，分别做一下前缀和即可。然后按位将 $ X $ 拆分并分别运算再组合即可。

同时显然我们可以通过 bitset 的构造函数来快速将十进制转二进制，并通过 bitset 的 to_ulong() 函数转为 unsigned long，并通过 bitset 加速按位运算。

最终复杂度 $ O(n\dfrac{\log X}{w}) $，因为此处 $ \log $ 最大不超过 $ 32 $，所以我们可以认为复杂度是线性的，即 $ O(n) $。

Update：复杂度还是 $ O(n\log X) $ 的，因为最后计算法案的时候还有个枚举。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;



template < typename T = int >
inline T read(void);

int X, N;
int T[210000];
bitset < 32 > A[210000];
bitset < 32 > sum0[210000], sum1[210000];

int main(){
    sum0[0].reset(), sum1[0].set();
    N = read(), X = read();
    for(int i = 1; i <= N; ++i){
        T[i] = read(), A[i] = bitset < 32 >(read());
        switch(T[i]){
            case 1:{
                sum0[i] = sum0[i - 1] & A[i];
                sum1[i] = sum1[i - 1] & A[i];
                break;
            }
            case 2:{
                sum0[i] = sum0[i - 1] | A[i];
                sum1[i] = sum1[i - 1] | A[i];
                break;
            }
            case 3:{
                sum0[i] = sum0[i - 1] ^ A[i];
                sum1[i] = sum1[i - 1] ^ A[i];
                break;
            }
            default:break;
        }
    }
    bitset < 32 > ans(X);
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j < 32; ++j)
            ans[j] = ans[j] ? sum1[i][j] : sum0[i][j];
        printf("%lu\n", ans.to_ulong());
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_24 初稿

update-2022_12_24 修改一个错误