Submit: 2579 Solved: 888
[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
网上又没有代码，自己yy了一上午才写出来
对于这道题目，我们记$pre_i$表示$i$号位置的元素前一次出现的位置
记$nxt_i$表示$i$号位置的元素后一次出现的位置
假设询问区间为$l,r$
那么$i$号位置满足条件，当且仅当$l<=i<=r, pre_i < l, nxt_i > r$
这样我们把$i, pre_i, nxt_i$看成一个三元组
然后用K-D tree加剪纸就行了
剪纸的时候考虑三种情况
- 询问区间完全包含该节点及其左右儿子，直接通过打标记统计出最大值
- 询问区间包含该节点但不包含其左右儿子，直接统计该节点对答案的贡献
- 询问区间与该节点及其左右儿子不重合，直接return
有了这三种剪枝，而且此题没有插入，因此复杂度为$O(mnsqrt{n})$
#include<cstdio> #include<cstring> #include<algorithm> #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)? EOF : *p1++) using namespace std; const int MAXN = 1e6 + 10; char buf[1 << 21], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, root, WD; int Ql, Qr, lastans = 0; struct Point { int x[4]; bool operator < (const Point &rhs) const{ return x[WD] < rhs.x[WD]; } }P[MAXN]; #define ls(x) T[x].ls #define rs(x) T[x].rs struct KDTree { int ls, rs, mn[3], mx[3], val; Point tp; }T[MAXN]; int a[MAXN], pre[MAXN], nxt[MAXN], happen[MAXN]; void update(int k) { for(int i = 0; i <= 2; i++) { T[k].mn[i] = T[k].mx[i] = T[k].tp.x[i]; if(ls(k)) T[k].mn[i] = min(T[ls(k)].mn[i], T[k].mn[i]), T[k].mx[i] = max(T[ls(k)].mx[i], T[k].mx[i]); if(rs(k)) T[k].mn[i] = min(T[rs(k)].mn[i], T[k].mn[i]), T[k].mx[i] = max(T[rs(k)].mx[i], T[k].mx[i]); } T[k].val = max(T[k].tp.x[3], T[ls(k)].val); T[k].val = max(T[k].val, T[rs(k)].val); } int Build(int l, int r, int wd) { if(l > r) return 0; int mid = l + r >> 1; WD = wd; nth_element(P + l, P + mid, P + r + 1); T[mid].tp = P[mid]; ls(mid) = Build(l, mid - 1, (wd + 1) % 3); rs(mid) = Build(mid + 1, r, (wd + 1) % 3); update(mid); return mid; } bool CheckInclude(int k) { if(T[k].mn[0] >= Ql && T[k].mx[0] <= Qr && T[k].mx[1] < Ql && T[k].mn[2] > Qr) return 1; return 0; } bool CheckCross(int k) { if(T[k].tp.x[0] >= Ql && T[k].tp.x[0] <= Qr && T[k].tp.x[1] < Ql && T[k].tp.x[2] > Qr) return 1; return 0; } bool CheckNotCross(int k) { if(T[k].mn[1] >= Ql || T[k].mx[2] <= Qr || T[k].mx[0] < Ql || T[k].mn[0] > Qr) return 1; return 0; } void Query(int k) { if(CheckInclude(k)) { lastans = max(lastans, T[k].val); return ; //矩形完全包含在查询区间内 } if(CheckCross(k)) lastans = max(lastans, T[k].tp.x[3]); //相交 if(CheckNotCross(k)) return ; // 没有重合的地方 int disl = T[ls(k)].val, disr = T[rs(k)].val; if(disl > disr) { if(disl > lastans) Query(ls(k)); if(disr > lastans) Query(rs(k)); } else { if(disr > lastans) Query(rs(k)); if(disl > lastans) Query(ls(k)); } } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif N = read(); M = read(); for(int i = 1; i <= N; i++) a[i] = read(); for(int i = 1; i <= N; i++) pre[i] = happen[a[i]], happen[a[i]] = i; for(int i = 1; i <= N; i++) happen[a[i]] = N + 1; for(int i = N; i >= 1; i--) nxt[i] = happen[a[i]], happen[a[i]] = i; for(int i = 1; i <= N; i++) P[i] = (Point) {i, pre[i], nxt[i], a[i]}; root = Build(1, N, 0); for(int i = 1; i <= M; i++) { int x = read(), y = read(); Ql = min((x + lastans) % N + 1,(y + lastans) % N + 1); Qr = max((x + lastans) % N + 1,(y + lastans) % N + 1); lastans = 0; Query(root); printf("%d ", lastans); } return 0; }