安吉D6-T4 - Jerry's blog

原题呈现

题目描述#

你需要维护一个序列，初始长度为 $n$ ．序列中的每个元素带有两个标记：权值 $a_i$ 和颜色 $c_i$ ．

本题要求强制在线．

接下来有 $m$ 次操作：

1 l r x：仅关注下标在 $[l, r]$ 内的元素．把其中权值不大于 $x$ 的元素按原下标递增顺序取出来，形成一个子序列．对于这个子序列，若相邻两个元素颜色相同，则认为它们属于同一段．求这个子序列共有多少段．
2 x y：在序列尾部插入一个新的元素，其权值为 $x$ ，颜色为 $y$ ．

例如：某次查询得到的颜色序列为

[1,4,4,6,6,6,2,5,5]

那么会被分成

[1], [4,4], [6,6,6], [2], [5,5]

共 $5$ 段．

输入格式#

从文件 subsequence.in 中读入数据．

第一行三个整数 $n, m, k$ ，分别表示序列的初始长度、操作次数和是否强制在线．

接下来两行，第一行 $n$ 个整数，表示 $a_i$ ；第二行 $n$ 个整数，表示 $b_i$ （即颜色 $c_i$ ）．

接下来 $m$ 行，每行首先一个整数 $t$ ，表示本次操作的种类．

若 $t=1$ ，接下来三个整数 $l, r, x$ ，描述一次查询．
若 $t=2$ ，接下来两个整数 $x, y$ ，描述一次插入．

对于 $k=0$ ，不要求强制在线．对于 $k=1$ ，要求输入的 $l, r, x, y$ 均对上一次查询的结果按位异或，即 $l' = l \oplus ans$ ，若上一次查询不存在，则 ans = 0．

解码方式示例：

1
int n, m, k;
2
cin >> n >> m >> k;
3
for (int i = 1 ; i <= m ; i++) {
4
    cin >> t;
5
    if (t == 1) {
6
        int l, r, x;
7
        cin >> l >> r >> x;
8
        l ^= ans * k;
9
        r ^= ans * k;
10
        x ^= ans * k;
11
    } else {
12
        int x, y;
13
        cin >> x >> y;
14
        x ^= ans * k;
15
        y ^= ans * k;
16
    }
17
}

输出格式#

输出到文件 subsequence.out 中．

对于每个操作 $1$ ，每行输出一个整数表示查询的结果．

样例#

样例输入 #1#

1
10 10 0
2
6 8 5 9 6 10 2 4 8 9
3
2 4 3 3 4 1 2 3 3 2
4
1 7 9 7
5
1 1 4 4
6
2 2 8
7
2 1 6
8
2 10 2
9
2 10 8
10
2 8 4
11
2 3 10
12
1 5 16 5
13
1 4 14 7

样例输出 #1#

样例输入 #2#

1
10 20 0
2
2 19 13 20 7 19 17 8 15 12
3
1 2 4 3 5 3 2 4 2 2
4
2 9 3
5
1 1 9 15
6
2 17 3
7
1 1 12 3
8
2 15 5
9
1 6 13 6
10
2 7 1
11
2 20 3
12
2 10 1
13
1 5 9 4
14
1 1 7 15
15
2 12 1
16
2 7 5
17
2 12 4
18
1 3 18 6
19
1 12 12 14
20
1 7 7 1
21
2 8 5
22
1 6 8 10
23
1 14 18 4

样例输出 #2#

数据范围#

对于 $100\%$ 的数据，保证：

$1 \le n, m \le 3 \times 10^5$ ；
$0 \le k \le 1$ ；
$1 \le op \le 2$ ；
$1 \le l, r \le n$ （解码后）；
$1 \le a_i, c_i, x, y \le 10^9$ ．

子任务#

本题采用捆绑测试，你必须通过子任务内所有测试点才能获得该子任务分数．

测试点编号	$n, m \le$	特殊性质
$1 \sim 10$	$10^3$	无
$11 \sim 20$	$10^5$	无
$21 \sim 30$	$3\times10^5$	$k=0$
$31 \sim 40$	$3\times10^5$	操作 $1$ 的 $l=1$
$41 \sim 50$	$3\times10^5$	无

涉及到区间查询，单点修改，考虑使用树状数组或是线段树，但这道题并非简单的求区间和，于是选择使用线段树．

对于线段树的每一个节点，我们记录一个 vector，vector 中的每一个元素是一个四元组 [x, lcol, rcol, cnt]，

x 为选择的权值．
lcol 是选择权值为 x 时，该区间最左端有效元素的颜色．
rcol 是选择权值为 x 时，该区间最右端有效元素的颜色．
cnt 是选择权值为 x 时，该区间所有有效元素一共能组成多少段．

将这个四元组类型定义为结构体 Node．将包含 Node 的 vector 定义为类 Nodes．Nodes 即为线段树中每一个端点的数据类型．

对于该区间内每一个可能的 x，都建一个 Node，保存在该区间节点的 Nodes 中．

对于两个 Node $a,b$ 之间的合并，可以表示为：

对于 x，取 $\max\{a.x,b.x\}$ ．
对于 lcol，取 $a.lcol$ ．
对于 rcol，取 $b.rcol$ ．
对于 cnt，
- 若 $a.rcol = b.lcol$ ，即两个节点中间部分的颜色可以合并成一大段，答案取 $a.cnt + b.cnt-1$ ．
- 否则，取 $a.cnt + b.cnt$ ．

1
friend Node operator+(const Node a, const Node b) {
2
  // 对于所有权值为 0 的点，我们定义它为空 (null)，一个 Node 加上空还是该 Node
3
  if (a.x == 0)
4
    return b;
5
  if (b.x == 0)
6
    return a;
7
  Node ans;
8
  ans.x = max(a.x, b.x);
9
  ans.lcol = a.lcol;
10
  ans.rcol = b.rcol;
11
  ans.cnt = a.cnt + b.cnt - (a.rcol == b.lcol);
12
  return ans;
13
}

对于两个 Nodes $m,n$ （显然， $m,n$ 中的元素按照 $.x$ 升序排列）需要合并到 $k$ ，可以采用类似归并排序的方法．其宗旨为：

对于每一个存在于 $m$ 中的四元组 $i$ ，查找 $n$ 中最后一个四元组 $j$ 满足 $i.x \geq j.x$ ．此时 $j$ 中统辖的所有元素权值是节点 $n$ 所代表区间中所有小于等于 $i.x$ 的元素．将这两个四元组合并，加入到 $k$ 中，对于每一个存在于 $n$ 中的四元组也是如此．

在程序中，我们使用双指针，指针 $i$ 指向 $m$ ，指针 $j$ 指向 $n$ ．初始时， $i,j$ 都指向 $m,n$ 第一个元素的前一个位置．在每一次循环时，我们需要决定主场节点：

检查两个指针是否指向了两个 vector 的最后一个元素．
- 若都指向，结束循环．
- 若指针 $i$ 指向了 $m$ 的最后一个元素，则主场节点为 $n$ ．
- 若指针 $j$ 指向了 $n$ 的最后一个元素，则主场节点为 $m$ ．
- 若以上情况都不满足，则比较指针 $i$ $i$ 指向的下一个元素 $p$ $p$ 和指针 $j$ $j$ 指向的下一个元素 $q$ $q$ 的大小
  - 若 $p<q$ 则主场节点为 $n$ ．
  - 若 $p>q$ 则主场节点为 $m$ ．
  - 否则，主场节点同时为 $m,n$ ．
在决定主场节点之后，将主场节点对应的指针向后移动一次．
最后，将 $i$ 指向的元素和 $j$ 指向的元素合并，加入节点 $k$ ．

1
friend Nodes operator+(const Nodes a, const Nodes b) {
2
  Nodes ans;
3
  ans.l = a.l;
4
  ans.r = b.r;
5
  int i = -1, j = -1;
6
  while (true) {
7
    Node tmp;
8
    bool isInEndA = i + 1 >= a.size();
9
    bool isInEndB = j + 1 >= b.size();
10
    if (isInEndA && isInEndB)
11
      break;
12
    if (isInEndB || (!isInEndA && a[i + 1].x < b[j + 1].x)) {
13
      i++;
14
      tmp = a[i];
15
      if (j != -1) {
16
        tmp = tmp + b[j];
17
      }
18
    } else if (isInEndA || a[i + 1].x > b[j + 1].x) {
19
      j++;
20
      tmp = b[j];
21
      if (i != -1) {
22
        tmp = a[i] + tmp;
23
      }
24
    } else {
25
      i++;
26
      j++;
27
      tmp = a[i] + b[j];
28
    }
29
    ans.push_back(tmp);
30
  }
31
  return ans;
32
}

建树和修改的代码和普通线段树大差不差，因为没有区间修改，所以都不需要 pushup．

由于最多会有 $m$ 次插入操作，所以要预留出这些空间．线段树的大小要开 $m+n$ ．

1
void build(int t, int l, int r) {
2
  f[t].l = l, f[t].r = r;
3
  if (l == r) {
4
    if (l > n) { // 大于 n 的点当前还是空的
5
      return;
6
    }
7
    Node nd;
8
    nd.x = a[l];
9
    nd.lcol = b[l];
10
    nd.rcol = b[l];
11
    nd.cnt = 1;
12
    f[t].push_back(nd);
13
    return;
14
  }
15
  int mid = (l + r) / 2;
16
  build(t * 2, l, mid);
17
  build(t * 2 + 1, mid + 1, r);
18
  pushup(t);
19
}
20
void pushup(int t) { f[t] = f[t * 2] + f[t * 2 + 1]; }
21
void Modify(int t, int pos, int a, int b) {
22
  if (f[t].l == pos && f[t].r == pos) {
23
    f[t].push_back({a, b, b, 1});
24
    return;
25
  }
26
  if (f[t].l > pos || f[t].r < pos) {
27
    return;
28
  }
29
  Modify(t * 2, pos, a, b);
30
  Modify(t * 2 + 1, pos, a, b);
31

32
  pushup(t);
33
}

至于查询操作，需要注意：

若当前区间被查询区间完全覆盖，则需要使用 upper_bound 找到当前 Nodes 中所有的 Node，满足权值 $x$ 小于等于查询权值 $qx$ ，其中权值最大的一个．将这个节点返回．
若当前区间和查询区间完全没有交集，则返回一个空的 Node（在本程序中，权值为 0 的 Node 为空的 Node，权值默认为 0），表示什么都没有．

1
Node Query(int t, int x, int y, int tgt) {
2
  if (f[t].l >= x && f[t].r <= y) {
3
    auto it = upper_bound(f[t].begin(), f[t].end(), tgt);
4
    if (it == f[t].begin())
5
      return Node();
6
    return *(it - 1);
7
  }
8
  if (f[t].l > y || f[t].r < x) {
9
    return Node();
10
  }
11
  return Query(t * 2, x, y, tgt) + Query(t * 2 + 1, x, y, tgt);
12
}

这样线段树就建完了．

在处理查询时，调用线段树的 Query 方法，收到节点中的 cnt 即为答案．

在处理插入时，直接调用线段树的 Modify 方法即可．

但是这样每次插入一个节点，每一层都会调用一次 pushup，pushup 复杂度最高 $O(n)$ ，每一次查询的复杂度为 $O(n\log n)$ ． $q$ 次查询的复杂度为 $O(nq\log n)$ ，不如暴力．

仔细想想，对于一个区间，只有其中的全部元素都被插入之后，这个区间才会被访问到．因此，只需要在 $pos=r$ 的时候执行一次 pushup 即可．

1
void Modify(int t, int pos, int a, int b) {
2
  if (f[t].l == pos && f[t].r == pos) {
3
    f[t].push_back({a, b, b, 1});
4
    return;
5
  }
6
  if (f[t].l > pos || f[t].r < pos) {
7
    return;
8
  }
9
  Modify(t * 2, pos, a, b);
10
  Modify(t * 2 + 1, pos, a, b);
11

12
  if (f[t].r == pos) {
13
    pushup(t);
14
  }
15
}

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 3e5 + 100;
4
const int INF = 0x3f3f3f3f;
5
int n, m, k, a[2 * N], b[2 * N];
6
int l, r, x, y, ans;
7

8
struct SegmentTree {
9
    struct Node {
10
        int x = 0, lcol = 0, rcol = 0, cnt = 0;
11
        friend Node operator+(const Node a, const Node b) {
12
            if (a.x == 0)
13
                return b;
14
            if (b.x == 0)
15
                return a;
16
            Node ans;
17
            ans.x = max(a.x, b.x);
18
            ans.lcol = a.lcol;
19
            ans.rcol = b.rcol;
20
            ans.cnt = a.cnt + b.cnt - (a.rcol == b.lcol);
21
            return ans;
22
        }
23
        friend bool operator<(const int a, const Node b) { return a < b.x; }
24
    };
25
    class Nodes : public vector<Node> {
26
      public:
27
        int l, r;
28
        friend Nodes operator+(const Nodes a, const Nodes b) {
29
            Nodes ans;
30
            ans.l = a.l;
31
            ans.r = b.r;
32
            int i = -1, j = -1;
33
            while (true) {
34
                Node tmp;
35
                bool isInEndA = i + 1 >= a.size();
36
                bool isInEndB = j + 1 >= b.size();
37
                if (isInEndA && isInEndB)
38
                    break;
39
                if (isInEndB || (!isInEndA && a[i + 1].x < b[j + 1].x)) {
40
                    i++;
41
                    tmp = a[i];
42
                    if (j != -1) {
43
                        tmp = tmp + b[j];
44
                    }
45
                } else if (isInEndA || a[i + 1].x > b[j + 1].x) {
46
                    j++;
47
                    tmp = b[j];
48
                    if (i != -1) {
49
                        tmp = a[i] + tmp;
50
                    }
51
                } else {
52
                    i++;
53
                    j++;
54
                    tmp = a[i] + b[j];
55
                }
56
                ans.push_back(tmp);
57
            }
58
            return ans;
59
        }
60
    } f[N * 8];
61
    void build(int t, int l, int r) {
62
        f[t].l = l, f[t].r = r;
63
        if (l == r) {
64
            if (l > n) {
65
                return;
66
            }
67
            Node nd;
68
            nd.x = a[l];
69
            nd.lcol = b[l];
70
            nd.rcol = b[l];
71
            nd.cnt = 1;
72
            f[t].push_back(nd);
73
            return;
74
        }
75
        int mid = (l + r) / 2;
76
        build(t * 2, l, mid);
77
        build(t * 2 + 1, mid + 1, r);
78
        pushup(t);
79
    }
80
    void pushup(int t) { f[t] = f[t * 2] + f[t * 2 + 1]; }
81
    void Modify(int t, int pos, int a, int b) {
82
        if (f[t].l == pos && f[t].r == pos) {
83
            f[t].push_back({a, b, b, 1});
84
            return;
85
        }
86
        if (f[t].l > pos || f[t].r < pos) {
87
            return;
88
        }
89
        Modify(t * 2, pos, a, b);
90
        Modify(t * 2 + 1, pos, a, b);
91

92
        if (f[t].r == pos) {
93
            pushup(t);
94
        }
95
    }
96
    Node Query(int t, int x, int y, int tgt) {
97
        if (f[t].l >= x && f[t].r <= y) {
98
            auto it = upper_bound(f[t].begin(), f[t].end(), tgt);
99
            if (it == f[t].begin())
100
                return Node();
101
            return *(it - 1);
102
        }
103
        if (f[t].l > y || f[t].r < x) {
104
            return Node();
105
        }
106
        return Query(t * 2, x, y, tgt) + Query(t * 2 + 1, x, y, tgt);
107
    }
108
} sgTree;
109

110
signed main() {
111
    ios::sync_with_stdio(false);
112
    cin.tie(0);
113
    cout.tie(0);
114
    cin >> n >> m >> k;
115
    for (int i = 1; i <= n; i++) {
116
        cin >> a[i];
117
    }
118
    for (int i = 1; i <= n; i++) {
119
        cin >> b[i];
120
    }
121
    sgTree.build(1, 1, n + m);
122
    int cnt = n;
123
    for (int i = 1; i <= m; i++) {
124
        int t;
125
        cin >> t;
126
        if (t == 1) {
127
            cin >> l >> r >> x;
128
            l ^= ans * k;
129
            r ^= ans * k;
130
            x ^= ans * k;
131
            int nds = sgTree.Query(1, l, r, x).cnt;
132
            ans = nds;
133
            cout << ans << endl;
134
        } else {
135
            cin >> x >> y;
136
            x ^= ans * k;
137
            y ^= ans * k;
138
            sgTree.Modify(1, ++cnt, x, y);
139
        }
140
    }
141
}

音乐

音乐