651 字

3 分钟

修改

2023-10-04

oi

/

qbxt

/

dtoj

题目#

给定一个长度为 $n$ 的序列，第 $i$ 个元素的下标为 $i$ ，值为 $a_i$

现有 $q$ 次操作，每次给定一个区间 $[l,r]$ ，求该区间的元素和，并将区间内的所有元素值修改为 $0$

需要你输出所有操作答案的异或和

由于 $n, q$ 很大，我们提供另外一种读入方式

给定一个 $z$ ，注意其类型为 unsigned int，你需要调用 $n$ 次 $gen()$ 函数获得序列，再调用 $2n$ 次获得每次操作的 $l,r$ ，具体代码如下：

1
const int N = 1e9;
2
const int maxn = 1e7 + 10;
3
unsigned int x = 123456789, y = 362436069, z, a[maxn];
4
int n, q;
5
unsigned int gen()
6
{
7
    unsigned int t;
8
    x ^= x << 16; x ^= x >> 5; x ^= x << 1;
9
    t = x; x = y; y = z; z = t ^ x ^ y;
10
    return z % N + 1;
11
}
12

13
int main()
14
{
15
    scanf("%d%d%u", &n, &q, &z);
16
    for ( int i = 1; i <= n; ++ i )
17
        a[i] = gen();
18
    for ( int i = 1; i <= q; ++ i )
19
    {
20
        int l = gen() % n + 1, r = gen() % n + 1;
21
        if ( l > r ) swap(l, r);
22
        // do your things ...
23
    }
24
}

对于 $40\%$ 的数据，满足 $n, q\le 10^6$

对于 $100\%$ 的数据，满足 $n, q\leq 10^7$

题解#

~~我才不会告诉你考场上我想了1个小时还没想出来~~

开始想到线段树，看数据范围，妥妥超时

~~然后就不知道怎么做了~~

既然查询完接着删除，那么一个数查询完之后接着就可以不用管了

考虑用并查集维护不用管的数，开始的时候开 $n$ 个并查集树

查询的时候，顺便维护一下（把 $l$ 到 $r$ 的fa都指向fa[r + 1]）

（其实用链表维护也可以过）

~~我好菜~~

代码#

1
#include<bits/stdc++.h>
2
#define ll long long
3

4
using namespace std;
5

6
const int N = 1e9;
7
const int maxn = 1e7 + 10;
8
unsigned int x = 123456789, y = 362436069, z, a[maxn];
9
int n, q;
10
int fa[maxn];
11
unsigned int gen()
12
{
13
    unsigned int t;
14
    x ^= x << 16; x ^= x >> 5; x ^= x << 1;
15
    t = x; x = y; y = z; z = t ^ x ^ y;
16
    return z % N + 1;
17
}
18

19
int getfa(int u)
20
{
21
  if(fa[u] == u) return u;
22
  return fa[u] = getfa(fa[u]);
23
}
24

25
void merge(int x, int y)
26
{
27
  int xfa = getfa(x), yfa = getfa(y);
28
  fa[xfa] = yfa;
29
}
30

31
int main()
32
{
33
    scanf("%d%d%u", &n, &q, &z);
34
    for (int i = 1;i <= n;i++)
35
        a[i] = gen(), fa[i] = i;
36
    fa[n + 1] = n + 1;
37
    unsigned ll ans = 0;
38
    for (int i = 1;i <= q;i++)
39
    {
40
        int l = gen() % n + 1, r = gen() % n + 1;
41
        if (l > r) swap(l, r);
42
        unsigned ll b = 0;
43
        int g;
44
    for(int i = getfa(l);i <= r;i = g)
45
    {
46
      b += a[i];
47
      g = getfa(i + 1);
48
      merge(i, i + 1);
49
    }
50
    ans ^= b;
51

52
    }
53
    cout << ans;
54
}

修改

https://blog.histcat.top/posts/change/

作者

Histcat

发布于

2023-10-04

许可协议

CC BY-NC-SA 4.0

[JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)

染色