传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3585
【题解】
哎好像就是上题啊
怎么权值是1e9了啊
那没关系啊把主席树调成[0,1e9]的就行啦
哎调调空间
过了
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m; int rt[M]; namespace CMT { const int M = 1e7 + 10; int s[M], ch[M][2], siz; inline void change(int &x, int y, int l, int r, int pos, int va) { x = ++siz; ch[x][0] = ch[y][0]; ch[x][1] = ch[y][1]; if(l==r) { s[x] = va; return ; } int mid = l+r>>1; if(pos <= mid) change(ch[x][0], ch[y][0], l, mid, pos, va); else change(ch[x][1], ch[y][1], mid+1, r, pos, va); s[x] = min(s[ch[x][0]], s[ch[x][1]]); } inline int mex(int x, int l, int r, int pos) { if(l == r) return l; int mid = l+r>>1; if(s[ch[x][0]] >= pos) return mex(ch[x][1], mid+1, r, pos); else return mex(ch[x][0], l, mid, pos); } } int main() { scanf("%d%d", &n, &m); for (int i=1, t; i<=n; ++i) { scanf("%d", &t); CMT::change(rt[i], rt[i-1], 0, 1e9, t, i); } while(m--) { int x, y; scanf("%d%d", &x, &y); printf("%d\n", CMT::mex(rt[y], 0, 1e9, x)); } return 0; } View Code
转载于:https://www.cnblogs.com/galaxies/p/bzoj3585.html
相关资源：JAVA上百实例源码以及开源项目