3489: A simple rmq problem
Time Limit: 40 Sec Memory Limit: 600 MB
Submit: 1594 Solved: 520
[Submit][Status][Discuss]
Description
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
Input
第一行为两个整数N,M。M是询问数，N是序列的长度（N<=100000，M<=200000)
第二行为N个整数，描述这个序列{ai}，其中所有1<=ai<=N
再下面M行，每行两个整数x，y，
询问区间[l,r]由下列规则产生（OIER都知道是怎样的吧>_<)：
l=min(（x+lastans)mod n+1,(y+lastans）mod n+1);
r=max(（x+lastans)mod n+1,(y+lastans）mod n+1);
Lastans表示上一个询问的答案，一开始lastans为0
Output
一共M行，每行给出每个询问的答案。
Sample Input
10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
Sample Output
4
10
10
0
0
10
0
4
0
4
10
10
0
0
10
0
4
0
4
HINT
注意出题人为了方便，input的第二行最后多了个空格。
2015.6.24新加数据一组，2016.7.9放至40S,600M,但未重测
Source
参考了网上的一些做法，可持久化树套树什么的实在吃不消，于是采用了KD-Tree的方法。
考虑一个点，在哪个区间内它是唯一出现的呢？
设prev[i]为上一个和i处权值相同的位置，next[i]为下一个和i处权值相同的位置，显然在(prev[i],next[i])这个区间内，i点是该权值唯一出现的位置。
对于一个询问(ql,qr)，我们可以转换为：找出满足 prev[i] < ql 且 next[i] > qr 且 ql <= i <= qr 的i中，权值最大的i。这个就是KD-Tree维护三维的区间最值问题。
#include <bits/stdc++.h>
inline int getC(void) {
static const int siz = ;
static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz;
if (hd == tl)
fread(hd = buf, , siz, stdin);
return int(*hd++);
}
inline int getI(void) {
register int ret = ;
register int neg = false;
register int bit = getC();
for (; bit < ; bit = getC())
if (bit == '-')neg ^= true;
for (; bit > ; bit = getC())
ret = ret * + bit - '';
return neg ? -ret : ret;
}
template <class T>
inline T min(const T &a, const T &b) {
return a < b ? a : b;
}
template <class T>
inline T max(const T &a, const T &b) {
return a > b ? a : b;
}
const int maxn = ;
int n, m;
int answer;
int num[maxn];
int next[maxn];
int prev[maxn];
int last[maxn];
int value[maxn][];
int pos[maxn];
int maxv[maxn];
int lson[maxn];
int rson[maxn];
int mini[maxn][];
int maxi[maxn][];
int qryL, qryR;
int cmpK;
inline bool cmp(const int &a, const int &b) {
return value[a][cmpK] < value[b][cmpK];
}
int build(int l, int r, int k) {
int mid = (l + r) >> ; cmpK = k;
std::nth_element(
pos + l, pos + mid, pos + r + , cmp);
maxv[mid] = num[pos[mid]];
for (int i = ; i < ; ++i)
mini[mid][i] = maxi[mid][i] = value[pos[mid]][i];
if (l < mid) {
lson[mid] = build(l, mid - , (k + ) % );
maxv[mid] = max(maxv[mid], maxv[lson[mid]]);
for (int i = ; i < ; ++i) {
mini[mid][i] = min(mini[mid][i], mini[lson[mid]][i]);
maxi[mid][i] = max(maxi[mid][i], maxi[lson[mid]][i]);
}
}
if (r > mid) {
rson[mid] = build(mid + , r, (k + ) % );
maxv[mid] = max(maxv[mid], maxv[rson[mid]]);
for (int i = ; i < ; ++i) {
mini[mid][i] = min(mini[mid][i], mini[rson[mid]][i]);
maxi[mid][i] = max(maxi[mid][i], maxi[rson[mid]][i]);
}
}
return mid;
}
inline bool check(int t) {
if (mini[t][] > qryR || maxi[t][] < qryL)return false;
if (mini[t][] >= qryL || maxi[t][] <= qryR)return false;
return true;
}
void query(int t) {
if (mini[t][] >= qryL && maxi[t][] <= qryR && maxi[t][] < qryL && mini[t][] > qryR)
{ answer = max(answer, maxv[t]); return; }
if (pos[t] >= qryL && pos[t] <= qryR && prev[pos[t]] < qryL && next[pos[t]] > qryR)
answer = max(answer, num[pos[t]]);
if (maxv[lson[t]] > maxv[rson[t]]) {
if (lson[t] && maxv[lson[t]] > answer && check(lson[t]))query(lson[t]);
if (rson[t] && maxv[rson[t]] > answer && check(rson[t]))query(rson[t]);
}
else {
if (rson[t] && maxv[rson[t]] > answer && check(rson[t]))query(rson[t]);
if (lson[t] && maxv[lson[t]] > answer && check(lson[t]))query(lson[t]);
}
}
signed main(void) {
n = getI();
m = getI();
for (int i = ; i <= n; ++i)
num[i] = getI();
for (int i = ; i <= n; ++i)
last[i] = ;
for (int i = ; i <= n; ++i)
prev[i] = last[num[i]], last[num[i]] = i;
for (int i = n; i >= ; --i)
last[i] = n + ;
for (int i = n; i >= ; --i)
next[i] = last[num[i]], last[num[i]] = i;
for (int i = ; i <= n; ++i) {
pos[i] = i;
value[i][] = i;
value[i][] = prev[i];
value[i][] = next[i];
}
int root = build(, n, );
for (int i = ; i <= m; ++i) {
int x = getI();
int y = getI();
qryL = (x + answer) % n + ;
qryR = (y + answer) % n + ;
if (qryL > qryR)
qryL ^= (qryR ^= (qryL ^= qryR));
answer = ; query(root); printf("%d\n", answer);
}
}
@Author: YouSiki