DDOSvoid's Blog

2021 Hubei Provincial Collegiate Programming Contest K Chtholly and World-End Battle

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/gym/103104/problem/K

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定 $l,r,v$，然后我们从 $a_l$ 开始到 $a_r$，每次将 $v$ 置成 $|v-a_l|$，求最终 $v$ 的值

$n,m\le 10^5$

Solution

我们考虑分块，对于每一块求出进入这块之前的值为 $v$ 时，离开这块的值是多少，这样我们询问的复杂度就是 $O(\sqrt n)$，我们考虑如何预处理这个东西

注意到一开始这个东西是一个 $y=x$ 的函数，每有一个 $a_i$，都相当于将其从某个点对折，这样是一个对称，我们可以用并查集来维护取值相同的位置

具体的，我们存储当前直线 $x=ky+b$ 以及 $x$ 的范围 $[l,r]$，对于一条 $y=a$ 的直线，我们求其与直线交点的横坐标 $x_0=ka+b$，根据这个我们来缩短 $l,r$ 以及求新的 $k,b$

时间复杂度 $O(n\sqrt n\alpha(a))$

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
#include <iostream>
#include <cmath>
#define maxn 100010
#define maxb 400
using namespace std;

const int N = 100000;

int n, m, a[maxn];

int fa[maxn];
void init_fa(int n) { for (int i = 0; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy; 
}

int blo, num, l[maxb], r[maxb], bl[maxn], d[maxb][maxn];
void init_blo(int n) {
    blo = sqrt(n); num = (n + blo - 1) / blo; 
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n;
    for (int o = 1; o <= num; ++o) {
        int l = 0, r = N, k = 1, b = 0, v; init_fa(N); 
        for (int i = ::l[o]; i <= ::r[o]; ++i) {
            v = k * a[i] + b;
            if (2 * v > l + r) {
                k = -1, b = v;
                for (int i = v; i <= r; ++i) merge(i, 2 * v - i);
                r = min(r, v); 
            }
            else {
                k = 1, b = v;
                for (int i = l; i <= v; ++i) merge(i, 2 * v - i);
                l = max(l, v); 
            }
        }
        for (int i = 0; i <= N; ++i) d[o][i] = k * (find(i) - b);
    }
}

int query(int L, int R, int v) {
    int Bl = bl[L], Br = bl[R];
    if (Bl == Br) {
        for (int i = L; i <= R; ++i) v = abs(v - a[i]);
        return v;
    }
    for (int i = L; i <= r[Bl]; ++i) v = abs(v - a[i]);
    for (int i = Bl + 1; i < Br; ++i) v = d[i][v];
    for (int i = l[Br]; i <= R; ++i) v = abs(v - a[i]);
    return v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_blo(n);
    for (int i = 1, lans = 0; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        x ^= lans; y ^= lans; z ^= lans;
        cout << (lans = query(x, y, z)) << "\n";
    }
    return 0;
}