[题解]CCPC网络赛2019 B - array

Posted on In ,

[CCPC网络赛2019] B - array

题意

给出一个数列\(\{a_i\}\),维护两种操作:

  • 1 pos : 把\(a_{pos}\)加上\(10^7\)
  • 2 r k: 找到一个不小于\(k\)且不等于\(a_1,...,a_r\)的最小值\(x\)

共有\(m\)组询问,强制在线.

\(1 \leq n,m \leq 10^5\),\(1 \leq a_i \leq n\). 保证\(1 \leq pos,r,k\leq n\)

解法

建一棵权值线段树,每个点存储该数原来的位置.维护\(Set\)操作和\(minv\).

对于操作1,由限制易得等同于删除\(a_{pos}\).

对于操作2,我们搜索权值线段树里\([k,n]\)中大于\(r\)的第一个最小值,若不存在则答案为\(n+1\).

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
//HDU6703 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int INF = 1e9+7;
struct segtree{
	const int NO_OPT = INT_MAX;
	int size = 1;
	vector<int>setv,maxv;
	void init(int n){
		while(size < n)size *= 2;
		setv.assign(size*2,NO_OPT);
		maxv.assign(size*2,0);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		if(NO_OPT != setv[x]){
			setv[ls(x)] = setv[rs(x)] = setv[x];
			maxv[ls(x)] = maxv[rs(x)] = setv[x];
			setv[x] = NO_OPT;
		}
	}
	void pushup(int x){
		maxv[x] = max(maxv[ls(x)],maxv[rs(x)]);
	}
	void Set(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			setv[x] = v;
			maxv[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		Set(l,r,v,ls(x),lx,m);
		Set(l,r,v,rs(x),m,rx);
		pushup(x);
	}
	void Set(int l,int r,int v){
		r++;
		Set(l,r,v,0,0,size);
	}
	int kth(int l,int v,int x,int lx,int rx){
		pushdown(x,lx,rx);
		if(l >= rx or maxv[x] < v)return NO_OPT;
		if(rx - lx == 1){
			if(setv[x] != NO_OPT){
				maxv[x] = setv[x];
				setv[x] = NO_OPT;
			}
			if(maxv[x] >= v)return lx;
			else return NO_OPT;
		}
		int m = (lx+rx)/2;
		int idx1 = kth(l,v,ls(x),lx,m),idx2 = NO_OPT;
		if(idx1 == NO_OPT)idx2 = kth(l,v,rs(x),m,rx);
		return min(idx1,idx2);
	}
	int kth(int l,int v){
		return kth(l,v,0,0,size); 
	}
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int lstans = 0;
		segtree seg;
		int n,m;
		cin >> n >> m;
		vector<int>raw(n+10);
		seg.init(1e5+10);
		seg.Set(0,0,INF);
		for(int i = 1;i <= n;i++){
			cin >> raw[i];
			seg.Set(raw[i],raw[i],i);
		}
		while(m--){
			int opt,l,r;
			cin >> opt >> l;
			l ^= lstans;
			if(opt == 1){
				seg.Set(raw[l],raw[l],INF);
			}
			else{
				cin >> r;
				r ^= lstans;
				lstans = seg.kth(r,l+1);
				if(lstans == INT_MAX)lstans = n+1;
				cout << lstans << endl;
			}
		}
	}
	return 0;
}