HDU 6703 array

Description:

You are given an array $a_1,a_2,...,a_n( \forall i \in [1,n],1 \le a_i \le n)$ . Initially, each element of the array is unique.

Moreover, there are $m$ instructions.

Each instruction is in one of the following two formats:

  1. $(1,pos)$ ,indicating to change the value of $a_{pos}$ to $a_{pos}+10,000,000$ ;
  2. $(2,r,k)$ ,indicating to ask the minimum value which is not equal to any $a_i ( 1 \le i \le r )$ and not less than $k$ .

Please print all results of the instructions in format $2$ .

Input:

The first line of the input contains an integer $T(1≤T≤10)$ , denoting the number of test cases.

In each test case, there are two integers $n(1 \le n \le 100,000)$ , $m(1 \le m \le 100,000)$ in the first line, denoting the size of array a and the number of instructions.

In the second line, there are $n$ distinct integers $a_1,a_2,...,a_n ( \forall i \in [1,n],1 \le a_i \le n)$ ,denoting the array.
For the following m lines, each line is of format $(1,t1)$ or $(2,t2,t3)$ .
The parameters of each instruction are generated by such way :

For instructions in format $1$ , we defined $pos=t1 \oplus LastAns . (It is promised that $1 le pos le n)$

For instructions in format $2$ , we defined $r=t2 \oplus LastAns$ , $k=t3 \oplus LastAns$ . (It is promised that $1 \le r \le n$ , $1 \le k \le n$ )

(Note that $\oplus$ means the bitwise XOR operator. )

Before the first instruction of each test case, $LastAns$ is equal to $0$ .After each instruction in format $2$ , $LastAns$ will be changed to the result of that instruction.

$(\sum n \le 510,000, \sum m \le 510,000 )$

Output:

For each instruction in format $2$ , output the answer in one line.

Sample Input:

3
5 9
4 3 1 2 5
2 1 1
2 2 2
2 6 7
2 1 3
2 6 3
2 0 4
1 5
2 3 7
2 4 3
10 6
1 2 4 6 3 5 9 10 7 8
2 7 2
1 2
2 0 5
2 11 10
1 3
2 3 2
10 10
9 7 5 3 4 10 6 2 1 8
1 10
2 8 9
1 12
2 15 15
1 12
2 1 3
1 9
1 12
2 2 2
1 9

Sample Output:

1
5
2
2
5
6
1
6
7
3
11
10
11
4
8
11

Hint:

note:
After the generation procedure ,the instructions of the first test case are :
2 1 1, in format 2 and r=1 , k=1
2 3 3, in format 2 and r=3 , k=3
2 3 2, in format 2 and r=3 , k=2
2 3 1, in format 2 and r=3 , k=1
2 4 1, in format 2 and r=4 , k=1
2 5 1, in format 2 and r=5 , k=1
1 3 , in format 1 and pos=3
2 5 1, in format 2 and r=5 , k=1
2 5 2, in format 2 and r=5 , k=2
the instructions of the second test case are :
2 7 2, in format 2 and r=7 , k=2
1 5 , in format 1 and pos=5
2 7 2, in format 2 and r=7 , k=2
2 8 9, in format 2 and r=8 , k=9
1 8 , in format 1 and pos=8
2 8 9, in format 2 and r=8 , k=9
the instructions of the third test case are :
1 10 , in format 1 and pos=10
2 8 9 , in format 2 and r=8 , k=9
1 7 , in format 1 and pos=7
2 4 4 , in format 2 and r=4 , k=4
1 8 , in format 1 and pos=8
2 5 7 , in format 2 and r=5 , k=7
1 1 , in format 1 and pos=1
1 4 , in format 1 and pos=4
2 10 10, in format 2 and r=10 , k=10
1 2 , in format 1 and pos=2

题目链接

对一个元素互不相同的数列支持两种操作(强制在线)

  1. 1 pos 将 $a_{pos}$ 改为 $a_{pos}+10^{7}$
  2. 2 r k 求最小的 $ans$ 使 $ans \ge k$ 和 $\forall i \in [1,r],ans \neq a_i$ 成立

建立权值线段树,将数列中所有元素出现的位置下标存入权值线段树

操作 $1$ 的修改就是其实就是删除元素 $a_i$ ,那么直接将 $a_i$ 在权值线段树中存的下标设置为 $ \infin $

操作 $2$ 的查询操作就直接在权值线段树查找元素 $[k,n+1]$ 下标 $ > r$ 的最小值

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int inf = 1e9 + 5;
struct SegTree {
  int n;
  int pos[maxn * 4];
  void Pull(int o) {
    pos[o] = std::max(pos[o * 2], pos[o * 2 + 1]);
  }
  void Build(int o, int l, int r) {
    if (l == r) {
      pos[o] = inf;
      return;
    }
    int m = (l + r) / 2;
    Build(o * 2, l, m);
    Build(o * 2 + 1, m + 1, r);
    Pull(o);
  }
  void Init(int _n) {
    n = _n;
    Build(1, 1, n);
  }
  void Modify(int o, int l, int r, int idx, int v) {
    if (l == r) {
      pos[o] = v;
      return;
    }
    int m = (l + r) / 2;
    if (idx <= m) Modify(o * 2, l, m, idx, v);
    else Modify(o * 2 + 1, m + 1, r, idx, v);
    Pull(o);
  }
  void Modify(int idx, int v) {
    Modify(1, 1, n, idx, v);
  }
  int Query(int o, int l, int r, int ll, int rr, int v) {
    if (l == r) return l;
    int m = (l + r) / 2, ret = inf;
    if (ll <= m && pos[o * 2] > v) ret = Query(o * 2, l, m, ll, rr, v);
    if (ret != inf) return ret;
    if (rr > m && pos[o * 2 + 1] > v) ret = Query(o * 2 + 1, m + 1, r, ll, rr, v);
    return ret;
  }
  int Query(int ll, int v) {
    return Query(1, 1, n, ll, n, v);
  }
};
int t;
int n, m;
SegTree tree;
int a[maxn];
int ans;
int main() {
  scanf("%d", &t);
  for (int cas = 1; cas <= t; ++cas) {
    scanf("%d%d", &n, &m);
    tree.Init(n + 1);
    ans = 0;
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      tree.Modify(a[i], i);
    }
    for (int i = 1; i <= m; ++i) {
      int op;
      scanf("%d", &op);
      if (op == 1) {
        int pos;
        scanf("%d", &pos);
        pos ^= ans;
        tree.Modify(a[pos], inf);
      }
      else if (op == 2) {
        int r, k;
        scanf("%d%d", &r, &k);
        r ^= ans; k ^= ans;
        ans = tree.Query(k, r);
        printf("%d\n", ans);
      }
    }
  }
  return 0;
}
Last modification:September 12th, 2019 at 12:35 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment