[Ynoi2004] rsxc

ID: 7406

远端评测题

2000ms

512MiB

尝试: 0

已通过: 0

难度: 7

上传者:

root

标签>

2004

O2优化

Ynoi

题目描述

给定一个长为 $n$ （ $1\le n\le 6\times 10^5$ ）的非负整数序列 $a_0,a_1,\dots,a_{n-1}$ （ $0\le a_i<2^{30}$ ）。

有 $q$ 个询问（ $1\le q\le 10^6$ ）。

每次询问给出两个整数 $l,r$ （ $0\le l\le r<n$ ），求有多少对整数 $(x,y)$ 满足：

$l\le x\le y\le r$ ；
$\forall i,j\in S\ :i\oplus j\in S$ ，其中 $S:=\{a_k\}_{k=x}^y$ 。

输入格式

由于本题数据较多，您不需要输入输出，请完善以下程序中的 init(int, int, vector<int>) 和 solve(int, int) 函数，并提交。正解不依赖于其模板。

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

void init(int n, int q, vector<int> a) {
  // implement...
}

long long solve(int l, int r) {
  // implement...
}

int main() {
  int n, q;
  uint64_t s;
  cin >> n >> q >> s;
  string r;
  cin >> r;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    for (int s = 5 * i; s < 5 * i + 5; s++)
      a[i] = (a[i] * 64 + (int)(r[s]) - (int)('0'));
  init(n, q, a);
  uint64_t state = 0;
  auto splitmix64 = [&](uint64_t v) {
    uint64_t z = (v + 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
  };
  mt19937_64 rng(s);
  for (int i = 0; i < q; i++) {
    int l = (rng() ^ state) % n;
    int r = (rng() ^ state) % n;
    long long ans = solve(min(l, r), max(l, r));
    state = splitmix64(state + ans);
    if ((i + 1) % (1 << 15) == 0)
      cout << state << endl;
  }
  cout << state << endl;
}

输入数据 1

5 10 2
0000000001000020000300004

输出数据 1

4834712607666044912

输入数据 2

20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>

输出数据 2

5449866856465492064

提示

Idea：Powerless，Solution：ccz181078&nzhtl1477&w33z，Code：w33z，Data：w33z

对于 $100\%$ 的数据， $1\leq n\le 6\times 10^5,1\le q\leq 10^6$ ， $0 \le a_i < 2^{30}$ ， $0 \le l \le r < n$ 。

#P8337. [Ynoi2004] rsxc