位运算

拆位贡献

题目链接：https://ac.nowcoder.com/acm/contest/22754/H

题意

给定一个长度为n的正整数数组，计算的值.

数据范围

▶　题解

    对于数字间的异或值的和，显然可以拆位对每个位进行单独的考虑；两个数之间异或，如果可以对答案产生贡献，那么两个位必然不相等，即.
    而本题是平方形式的，显然不能直接用数值的平方来计算，因为位是独立存在的，应该将平方的两个式子都进行枚举讨论，即.
    由上式可知，只有当同时满足时，才能产生的贡献，否则贡献为零；所以最终化简得到的式子为.
    因此，设dp[i][j][x][y]表示二进制的第i位为x，第j位为y的数量，预处理过后外面枚举a[i]和a[j]的位数，内层只需要枚举各个a[i]，通过dp数组就能找到符合条件的数量，最终以O()的复杂度通过此题.

▶　Code：

#include
#define int long long
#define endl "\n"
#define INF 1e15
using namespace std;
typedef pairpii;
int dp[35][35][3][3];
//dp[i][j][x][y]表示二进制的第i位为x，第j位为y的数量
const int p=1e9+7;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;cin >> n;
    vector< int>a(n+1);
    for(int i = 1; i <= n; i++)
        cin >> a[i]; 
    for(int i = 0; i <= 31; i++)
        for(int j = 0; j <= 31; j++)
            for(int k = 1; k <= n; k++)
                dp[i][j][(a[k] >> i) & 1][(a[k] >> j)& 1]++;
    int ans = 0;
    for(int i = 0; i <= 31; i++)
        for(int j = 0; j <= 31 ;j++)
            for(int k = 1; k <= n; k++)
                ans+=((1LL << (i+j)) %p * dp[i][j][((a[k]>>i) &1) ^ 1][((a[k] >> j) &1 ) ^1] %p ) %p;
    cout << ans << endl;    
    return 0;
}

题目链接：https://ac.nowcoder.com/acm/contest/86639/D

题意

    有组询问，每次给定两个数字,计算出区间中所有整数在二进制下1的个数之和。由于结果特别大，对结果取模998244353后输出。

数据范围

……

数据结构+位运算

线段树

题目链接：https://codeforces.com/contest/242/problem/E

题意

有一个长度为n的数组a，可以对数组执行两个操作：

• 1 l r:查询区间[l,r]的总和
• 2 l r x:对区间[l,r]每个数与x异或,即

对原数组执行m次操作，输出每次查询的结果.

数据范围

▶　题解

    由题意得，修改操作是位运算，所以我们拆开对每个位单独考虑；又因为a[i]的范围不超过1e6，所以只需要进行20位的讨论即可，我们通过二维的结构体建立约20课线段树,tree[i][x]表示从右往左第i位的线段树数组.
    对于异或操作，我们只需要对输入的x进行拆位，如果第i位为1，则区间内每个数的第i位都要进行取反操作，反之则没有任何影响；所以这题就演变成了线段树区间取反的模板题！其中，结构体变量ans表示该位上区间二进制值的和，size表示区间长度，lazy则表示该区间是否需要取反操作.
    对于区间查询总和的操作，因为线段树维护的信息是一个位上的区间"1"和"0"的总和需要将每一位查询到的区间二进制和乘以位的权值，即.

▶　Code:

#include 
#define ll long long
#define endl '\n'
#define INF 1e15
using namespace std;
typedef pair pii;
struct segment_tree{
    int L, R ,size;
    int lazy, ans;
} tree[21][400010];
int a[100010];
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    auto up = [&](int x, int idx) -> void
    {
        tree[idx][x].ans = tree[idx][x << 1].ans + tree[idx][(x << 1) + 1].ans;
    };
    auto down = [&](int x, int idx) -> void
    {
        if (!tree[idx][x].lazy)
            return;
        tree[idx][x].ans = tree[idx][x].size - tree[idx][x].ans;
        if (tree[idx][x].L!=tree[idx][x].R){
            tree[idx][x << 1].lazy ^= 1;
            tree[idx][(x << 1) + 1].lazy ^= 1;
        }
        tree[idx][x].lazy = 0;
    };
    auto build = [&](auto bulid, int x, int L, int R, int idx) -> void
    {
        tree[idx][x].L = L, tree[idx][x].R = R, tree[idx][x].size = R - L + 1;
        if (L == R)
        {
            tree[idx][x].ans = ((a[L] >> idx) & 1);
            return;
        }
        const int mid = L + R >> 1;
        bulid(bulid, x << 1, L, mid, idx);
        bulid(bulid, (x << 1) + 1, mid + 1, R, idx);
        up(x, idx);
    };
    auto change = [&](auto change, int x, int L, int R, int idx) -> void
    {
        down(x, idx);
        if (tree[idx][x].L > R || tree[idx][x].R < L)
            return;
        if (tree[idx][x].L >= L && tree[idx][x].R <= R)
        { 
            tree[idx][x].lazy ^= 1;
            down(x, idx);
            return;
        }
        change(change, x << 1, L, R, idx);
        change(change, (x << 1) + 1, L, R, idx);
        up(x, idx);
    };
    auto query = [&](auto query, int x, int L, int R, int idx) -> int
    {
        down(x, idx);
        if (tree[idx][x].L > R || tree[idx][x].R < L)
            return 0;
        if (tree[idx][x].L >= L && tree[idx][x].R <= R)
            return tree[idx][x].ans;
        return query(query, x << 1, L, R, idx) + query(query, (x << 1) + 1, L, R, idx);
    };
    for (int i = 0; i <= 20;i++)
        build(build, 1, 1, n, i);
    cin >> m;
    while (m--){
        int opt, L, R;
        cin >> opt >> L >> R;
        if (opt == 1){
            ll sum = 0;
            for (int i = 0; i <= 20;i++)
                sum += (1LL << i) * query(query, 1, L, R, i);
            cout << sum << endl;
        }
        else{
            int x;
            cin >> x; 
            for (int i = 0; i <= 20;i++)
                if ((x >> i) & 1)
                    change(change, 1, L, R, i);
        }
    }
    return 0;
}