Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3760 【[TJOI2017]异或和】

posted on 2019-09-24 14:36:09 | under 题解 |

对于这种异或类的题目,我们可以考虑从异或运算性质下手

我们记 $sum[i] = \sum_{j = 1} ^ {i}a[j]$

不难发现,如果我们对每一位分开考虑,若我们在求第x为的答案,记所有区间的连续的和有K个该位为1,那么跟据异或的运算法则,这一位对答案有贡献当且仅当K为奇数,且对答案的贡献为 $K\ \%\ 2 * 2 ^ x$

说得更具体点,我们要求的式子变成了:

$$\sum_{k = 0} ^ {2 ^ k <= sum[n]}\ *\ ((\sum_{i = 1}^{n}\sum_{j = 1}^i(sum[i] - sum[j - 1]) >> k\ \&\ 1)\ \%\ 2)\ *\ 2 ^ k$$

我们单独看里面的柿子: $$\sum_{i = 1}^{n}\sum_{j = 1}^i(sum[i] - sum[j - 1]) >> k\ \&\ 1$$

其实问题已经转化为:给定 $sum[i]$ ,求有多少个 $j(j\in[0,\ i - 1])$ ,满足 $sum[i] - sum[j]$ 的第K位为1

这个问题看上去很好处理,貌似是只要求出有多少个 $sum[i]$ 与 $sum[j]$ 的第K位不同即可,我们只需要记录 $sum[i] >> k$ 的一个前缀和即可。

但是这道题目十分弟弟,因为异或的减法是可以进位的,所以我们并不能直接向刚刚那么算。

为了方便,我们定义 $sum[i]_k$ 表示 $sum[i]$ 的第K位, $sum[i]_{1\ -\ k}$ 表示sum的1~k位 (原谅我'~'打不出来) 的和

我们先进行分类讨论:

一、如果 $sum[i]_k = 1$ ,那么能对答案产生贡献只有两种情况:

$1.sum[j]_k = 0\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$

$2.sum[j]_k = 1\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$

二、如果 $sum[i]_k = 0$ ,那么能对答案产生贡献也只有两种情况:

$1.sum[j]_k = 1\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$

$2.sum[j]_k = 0\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$

那么现在问题来了,我们怎么判断进位呢?

注意到 $\sum a[i]$ 不会太大

我们可以把 $sum[i]_{1\ -\ k - 1}$ 扔到两颗权值树状数组内,一棵存0的,另一颗存1的

注意:树状数组的下标可能为0,所以我们要把所有下标+1

$Code:$

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define mem(k, p) memset(k, p, sizeof(k))
#define lb(x) (x)&(-(x))
#define maxn 1000005
int n, m, a[maxn], sum[maxn], ma, Ans, ans;
struct Tree {
    int t[maxn];
    il void add(int u, int v, int x) {
        while(u <= x) t[u] += v, u += lb(u);
    }
    il void Add(int u, int v, int x) {
        add(u + 1, v, x + 1);
    }
    il int query(int u) {
        int ans = 0;
        while(u) ans += t[u], u -= lb(u);
        return ans;
    }
    il int query(int l, int r) {
        return query(r + 1) - query(l);
    }
}A, B;//A表示0的树状数组,B表示1的 
signed main() {
    n = read();
    rep(i, 1, n) a[i] = read(), sum[i] = sum[i - 1] + a[i], ma = max(ma, sum[i]);
    for(re int k = 0; (1 << k) <= ma; ++ k) {
        memset(A.t, 0, sizeof(A.t)), memset(B.t, 0, sizeof(B.t)), Ans = 0;
        int pax = (1 << k) - 1;//我们只考虑1~k位 
        rep(i, 0, n) {
            int temp = sum[i] & pax;//求出sum[i]_{1-k}
            //cout << k << ' ' << temp << endl;
            if((sum[i] >> k) & 1) {
                Ans += A.query(0, temp) + B.query(temp + 1, pax), B.Add(temp, 1, pax);
            }
            else {
                Ans += B.query(0, temp) + A.query(temp + 1, pax), A.Add(temp, 1, pax);
            }
        }
        //cout << Ans << ' ' << ans << endl;
        ans += (Ans % 2) * (1 << k);
    }
    printf("%lld", ans);
    return 0;
}