目录
  1. 1. 题目大意
  2. 2. 题解(思路)
  3. 3. AC代码
[题解] HDU6703 array

题目大意

这是CCPC2019网络预选赛的题目,题目传送门

给你一个数组aa,初始是[1,n][1, n]的某个排列,有mm个操作,操作分为两种:

  1. (1,pos)(1, pos):将aposa_{pos}修改为apos+10,000,000a_{pos} + 10,000,000
  2. (2,r,k)(2, r, k):询问一个a1,a2,,ar{a_1, a_2, ……, a_r}之中未出现的最小正整数AnsAns且满足AnskAns \geq k

这些给出的操作将经过加密,你需要解密,解密方式如下:

  • 每组测试数据的第一个操作前定义一个LastAnsLastAns初始化为00
  • 若给出两个数(1,t1)(1, t1),代表这次操作是操作11,最终的pos=t1LastAnspos = t1 \bigoplus LastAns
  • 若给出三个数(2,t2,t3)(2, t2, t3),代表这次操作是操作22,最终的r=t2LastAns,k=t3LastAnsr = t2 \bigoplus LastAns, k = t3 \bigoplus LastAns
  • 对于每个操作22得出的答案AnsAns,令LastAns=AnsLastAns = Ans
  • 其中\bigoplus代表的是逻辑运算中的XORXOR(喜闻乐见的按位异或)。

数据范围

T(1T10)T(1 \leq T \leq 10)组测试数据,保证每组测试数据给出的n(1n100,000)n(1 \leq n \leq 100,000)m(1m100,000)m(1 \leq m \leq 100,000),经解密过的pos,r,k[1,n]pos, r, k \in [1, n]。对于所有的测试数据保证n510,000\sum n \leq 510,000m510,000\sum m \leq 510,000

时间、空间限制

时间:4000/2000 MS (Java/Others),空间:262144/262144 K (Java/Others)

题解(思路)

这个题目是队友在最后四十分钟想出来的做法……可惜我Debug的时间太长,差2秒左右时间提交,赛后补题我第一时间提交,一遍AC。只是CCPC分站赛注定与我无瓜啦(觉得有一点点对不起队友)。

首先想到,如果操作没有经过加密,我们可以使用类似莫队的算法将操作离线,然后用一个数据结构(如STL里的set,需要修改)维护当前a1ara_1……a_r中有什么值,然后对于每个操作2,只要在[k,n+1][k, n + 1]中二分答案,然后找到满足条件的值即可。时间复杂度大概在O(mn(log2n)2)O(m \cdot {\sqrt n} \cdot {(\log_2n)^2}),貌似勉强可以?

此处收回上述做法,答案并不符合单调性,不能二分(逃

当然……出题人显然不想让你用离线操作,于是对操作进行加密。

观察到数组aa是某个[1,n][1, n]的排列,且1n100,0001 \leq n \leq 100,000,所以实际上每次操作11实际上是将aposa_{pos}变成操作22可能的答案之一。再者,对于每次操作22的询问,实际上ar+1ana_{r+1}……a_n的值都是可以取的答案。如果没有过操作11,且本次操作22给出的r=nr = n,由于保证原数组是个排列,不会出现重复元素,所以答案则是n+1n + 1

最终得出,先将给出的初始序列aa丢入一个数据结构,使得其在O(log2n)O(\log_2n)的时间复杂度下支持查询某个数在某个区间内所在位置(显然主席树或划分树可用)。对于每次操作11,将aposa_{pos}丢到一个在O(log2n)O(\log_2n)的时间复杂度下支持插入、查询的数据结构setset中(没错就是可以用STL里的set)。对于每次操作22,查询setset中的第一个k\geq k的数字,再找到ar+1ana_{r+1}……a_n中第一个k\geq k的数字,答案就是较小的那个。如果找不到?那答案自然就是n+1n + 1

以上做法时间复杂度大概在O(m(log2n)2)O(m \cdot {(\log_2n)^2}),如果是用主席树做的,可能可以压缩到O(mlog2n)O(m \cdot {\log_2 n}),但对于本题来说,时间是很充裕的啦。

AC代码

注意:这份代码用的是划分树的做法,对操作2的判断部分过分繁琐导致我的Debug时间很长,其实很多没有必要判断,大家可以优化一下。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//
// Created by Jeson Vendetta Xie on 2019-08-23.
//

#include <bits/stdc++.h>
using namespace std;
#define mm (l + r) >> 1
#define lson l, mid, dep + 1
#define rson mid + 1, r, dep + 1
const int MAX_N = 1e5 + 10;

int n, tree[32][MAX_N], a[MAX_N], b[MAX_N], c[MAX_N];
set<int> st;
set<int>::iterator it;
void build(int l, int r, int dep) {
if(l == r) {
tree[dep][l] = a[l];
return ;
}
int mid = mm;
build(lson), build(rson);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r) {
if(a[i] < a[j])
tree[dep][k++] = a[i++];
else tree[dep][k++] = a[j++];
}
while(i <= mid) tree[dep][k++] = a[i++];
while(j <= r) tree[dep][k++] = a[j++];
for(i = l; i <= r; ++i) a[i] = tree[dep][i];
}
int query(int l, int r, int dep, int L, int R, int k) {
if(L > R) return n + 1;
if(L <= l && r <= R) {
int i = lower_bound(tree[dep]+l, tree[dep]+r+1, k) - tree[dep];
if(i == r+1) return n + 1;
else return tree[dep][i];
}
int mid = mm, ret = n + 1, tmp;
if(L <= mid) {
tmp = query(lson, L, R, k);
ret = min(ret, tmp);
}
if(R > mid) {
tmp = query(rson, L, R, k);
ret = min(ret, tmp);
}
return ret;
}
int main() {
int T, m, k, r, ans, o;
scanf("%d", &T);
while(T --) {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[a[i]] = i;
c[i] = a[i];
}
build(1, n, 1);
ans = 0;
while(m --) {
scanf("%d", &o);
if(o == 1) {
scanf("%d", &k);
k ^= ans;
st.insert(c[k]);
} else {
scanf("%d %d", &r, &k);
r ^= ans, k ^= ans;
if(k > n) {
ans = k;
} else {
it = st.lower_bound(k);
if(it != st.end() && *it == k) {
ans = k;
} else {
if(b[k] <= r) {
int tmp = ((it != st.end()) ? *it : n + 1);
tmp = min(tmp, query(1, n, 1, r + 1, n, k));
ans = tmp;
} else {
ans = k;
}
}
}
printf("%d\n", ans);
}
}
st.clear();
}
return 0;
}
文章作者: Jeson Vendetta Xie
文章链接: http://jvxie.com/2019/08/26/题解-HDU6703-array/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 JVxie's Blog
打赏
  • 微信
  • 支付宝

评论