hyz's blog
0%

HDU 6356 Glad You Came

发表于

题意

给一个长度为n$ (1 <= n <= 10^5 $)的数组，所有元素的初始值为0，然后有m$ (1 <= m <= 5*10^6 $)个操作，更新某段区间的最大值。

分析

官方题解：如果有两个操作覆盖相同的区间，我们可以保留最大的那个。 对于每个操作$(l, r, v)$，令d等于$\lfloor log_2(r - l + 1) \rfloor$，我们可以用两个操作 $(l, l + 2^d - 1, v)$ 和$(r - 2^d + 1, r, v)$ 替换此操作。这样做之后，每个操作所覆盖的区间长度均为 2 的幂，这意味着长度仅有 $O(logn)$种。剩下的只不过是，按长度递减的顺序枚举操作，将每个操作分成两个相等长度的操作，直到区间长度为一。这样做的时间复杂度为$O(m + nlogn)$，空间复杂度为$O(nlogn)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;

unsigned X, Y, Z;
int T, Log[N], n, m, mx, l, r, v, d, a[19][N];

unsigned int rng61() {
    X ^= X << 11;
    X ^= X >> 4;
    X ^= X << 5;
    X ^= X >> 14;
    unsigned int tmp = X ^ Y ^ Z;
    X = Y;
    Y = Z;
    Z = tmp;
    return Z;
}

void upd(int &d, int v) {
    d < v && (d = v);
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    // 2^k <= i < 2^(k+1)，预处理出i对应的k
    for(int i = 2; i < N; i++)
        Log[i] = Log[i >> 1] + 1;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%u%u%u", &n, &m, &X, &Y, &Z);
        while(m--) {
            l = rng61() % n + 1, r = rng61() % n + 1;
            if(l > r) swap(l, r);
            v = rng61() % (1 << 30);
            d = Log[r - l + 1];
            // 逆用ST表
            upd(a[d][l], v);
            upd(a[d][r - (1 << d) + 1], v);
        }
        // 求出满足2^mx > n 的最小mx
        mx = 0;
        while(1 << mx <= n) mx++;
        // O(nlogn) 从大区间推到小区间，直到1
        for(int i = mx - 1; i > 0; i--) {
            for(int j = 1; j + (1 << i) - 1 <= n; j++) {
                upd(a[i - 1][j], a[i][j]);
                upd(a[i - 1][j + (1 << (i - 1))], a[i][j]);
                a[i][j] = 0;
            }
        }
        ll ans = 0;
        for(int i = 1; i <= n; i++) {
            ans ^= 1LL * i * a[0][i];
            a[0][i] = 0;
        }
        printf("%lld\n", ans);
    }

    return 0;
}