[题解] HDU6703 array

题目大意

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

给你一个数组$a$，初始是$[1, n]$的某个排列，有$m$个操作，操作分为两种：

1. $(1, pos)$：将$a_{pos}$修改为$a_{pos} + 10,000,000$；
2. $(2, r, k)$：询问一个${a_1, a_2, ……, a_r}$之中未出现的最小正整数$Ans$且满足$Ans \geq k$。

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

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

数据范围：

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

时间、空间限制：

时间：4000/2000 MS (Java/Others)，空间：262144/262144 K (Java/Others)

题解（思路）

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

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

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

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

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

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

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

AC代码

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

//
// 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;
}