G - Smaller Sum

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Answer the following $Q$ queries. The $i$-th query is as follows:

• Find the sum of the elements among $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ that are not greater than $X_i$.

Here, you need to answer these queries online.
That is, only after you answer the current query is the next query revealed.

For this reason, instead of the $i$-th query itself, you are given encrypted inputs $\alpha_i, \beta_i, \gamma_i$ for the query. Restore the original $i$-th query using the following steps and then answer it.

• Let $B_0=0$ and $B_i =$ (the answer to the $i$-th query).
• Then, the query can be decrypted as follows:
  • $L_i = \alpha_i \oplus B_{i-1}$
  • $R_i = \beta_i \oplus B_{i-1}$
  • $X_i = \gamma_i \oplus B_{i-1}$

Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

Constraints

• All input values are integers.
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• For the encrypted inputs, the following holds:
  • $0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}$
• For the decrypted queries, the following holds:
  • $1 \le L_i \le R_i \le N$
  • $0 \le X_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
$\alpha_1$ $\beta_1$ $\gamma_1$
$\alpha_2$ $\beta_2$ $\gamma_2$
$\vdots$
$\alpha_Q$ $\beta_Q$ $\gamma_Q$

Output

Print $Q$ lines.
The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

8
2 0 2 4 0 2 0 3
5
1 8 3
10 12 11
3 3 2
3 6 5
12 0 11

Sample Output 1

9
2
0
8
5

The given sequence is $A=(2,0,2,4,0,2,0,3)$.
This input contains five queries.

• Initially, $B_0=0$.
• The first query is $\alpha = 1, \beta = 8, \gamma = 3$.
  • After decryption, we get $L_i = \alpha \oplus B_0 = 1, R_i = \beta \oplus B_0 = 8, X_i = \gamma \oplus B_0 = 3$.
  • The answer to this query is $9$. This becomes $B_1$.
• The next query is $\alpha = 10, \beta = 12, \gamma = 11$.
  • After decryption, we get $L_i = \alpha \oplus B_1 = 3, R_i = \beta \oplus B_1 = 5, X_i = \gamma \oplus B_1 = 2$.
  • The answer to this query is $2$. This becomes $B_2$.
• The next query is $\alpha = 3, \beta = 3, \gamma = 2$.
  • After decryption, we get $L_i = \alpha \oplus B_2 = 1, R_i = \beta \oplus B_2 = 1, X_i = \gamma \oplus B_2 = 0$.
  • The answer to this query is $0$. This becomes $B_3$.
• The next query is $\alpha = 3, \beta = 6, \gamma = 5$.
  • After decryption, we get $L_i = \alpha \oplus B_3 = 3, R_i = \beta \oplus B_3 = 6, X_i = \gamma \oplus B_3 = 5$.
  • The answer to this query is $8$. This becomes $B_4$.
• The next query is $\alpha = 12, \beta = 0, \gamma = 11$.
  • After decryption, we get $L_i = \alpha \oplus B_4 = 4, R_i = \beta \oplus B_4 = 8, X_i = \gamma \oplus B_4 = 3$.
  • The answer to this query is $5$. This becomes $B_5$.

解题思路

  题目大意就是每次询问区间 $i \in [l, r]$ 内不超过 $x$ 的 $a_i$ 的总和，并且由于输入的特殊性导致强行在线处理。

  可以用可持久化线段树来做。具体来说，这里的线段树是权值线段树，线段树节点维护的是对应值域内出现的数的总和，记作 $s$。然后维护出 $n$ 个版本的线段树，其中第 $i$ 个版本的线段树是指插入 $a_1 \sim a_i$ 后的线段树。那么对于询问 $(l,r,x)$，只需对第 $r$ 个和第 $l-1$ 个版本的线段树求 $[0, x]$ 范围内 $s$ 的值即可，这里的 $s$ 指第 $r$ 个和第 $l-1$ 个版本的线段树中每个节点的 $s$ 的差值，表示的只考虑在 $a_l \sim a_r$ 中某个值域范围内出现的数的总和。

  AC 代码如下，时间复杂度为 $O(n \log{A} + m \log{A})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int a[N];
struct Node {
    int l, r;
    LL s;
}tr[N * 35];
int root[N], idx;

int modify(int u, int l, int r, int x, int c) {
    int v = ++idx;
    tr[v] = tr[u];
    if (l == r) {
        tr[v].s += c;
        return v;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[v].l = modify(tr[u].l, l, mid, x, c);
    else tr[v].r = modify(tr[u].r, mid + 1, r, x, c);
    tr[v].s = tr[tr[v].l].s + tr[tr[v].r].s;
    return v;
}

LL query(int u, int v, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return tr[u].s - tr[v].s;
    int mid = l + r >> 1;
    LL ret = 0;
    if (ql <= mid) ret = query(tr[u].l, tr[v].l, l, mid, ql, qr);
    if (qr >= mid + 1) ret += query(tr[u].r, tr[v].r, mid + 1, r, ql, qr);
    return ret;
}

int main() {
    int n, m, mx = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        mx = max(mx, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        root[i] = modify(root[i - 1], 0, mx, a[i], a[i]);
    }
    scanf("%d", &m);
    LL t = 0;
    while (m--) {
        LL x, y, z;
        scanf("%lld %lld %lld", &x, &y, &z);
        int l = x ^ t, r = y ^ t, c = z ^ t;
        t = query(root[r], root[l - 1], 0, mx, 0, c);
        printf("%lld\n", t);
    }
    
    return 0;
}

参考资料

  AtCoder Beginner Contest 339：https://www.cnblogs.com/Lanly/p/18005285