[CodeForces1000]F. One Occurrence

2018-06-28

lolifamily

题解

线段树

一道有意思的线段树题目，维护一个 pair 值（下一个元素的位置，权值）对其维护最大值（就是影响越持久）。

把问题离线处理，按照问题的右端点排序，这样就能满足单调性。

输出的时候一定要判断一下 first 的值是否符合要求。

注意：

这棵线段树维护的是最大值，不管是修改还是查询都需要取 max
如果没有 nxt，数组的值要赋值为 n+1

F. One Occurrence

time limit per test: 3 secondsmemory limit per test: 768 megabytesinput: standard inputoutput: standard output

You are given an array $𝑎$ consisting of $𝑛$ integers, and $𝑞$ queries to it. $𝑖$ -th query is denoted by two integers $𝑙 𝑖$ and $𝑟 𝑖$ . For each query, you have to find any integer that occurs exactly once in the subarray of $𝑎$ from index $𝑙 𝑖$ to index $𝑟 𝑖$ (a subarray is a contiguous subsegment of an array). For example, if $𝑎 = [1, 1, 2, 3, 2, 4]$ , then for query $(𝑙 𝑖 = 2, 𝑟 𝑖 = 6)$ the subarray we are interested in is $[1, 2, 3, 2, 4]$ , and possible answers are $1$ , $3$ and $4$ ; for query $(𝑙 𝑖 = 1, 𝑟 𝑖 = 2)$ the subarray we are interested in is $[1, 1]$ , and there is no such element that occurs exactly once.

Can you answer all of the queries?

Input

The first line contains one integer $𝑛$ ( $1 \leq 𝑛 \leq 5 \cdot 105$ ).

The second line contains $𝑛$ integers $𝑎 1, 𝑎 2, \dots, 𝑎 𝑛$ ( $1 \leq 𝑎 𝑖 \leq 5 \cdot 105$ ).

The third line contains one integer $𝑞$ ( $1 \leq 𝑞 \leq 5 \cdot 105$ ).

Then $𝑞$ lines follow, $𝑖$ -th line containing two integers $𝑙 𝑖$ and $𝑟 𝑖$ representing $𝑖$ -th query ( $1 \leq 𝑙 𝑖 \leq 𝑟 𝑖 \leq 𝑛$ ).

Output

Answer the queries as follows:

If there is no integer such that it occurs in the subarray from index $𝑙 𝑖$ to index $𝑟 𝑖$ exactly once, print $0$ . Otherwise print any such integer.

Example

input

1
6
2
1 1 2 3 2 4
3
2
4
2 6
5
1 2

output

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define inf 0x3F3F3F3F
6
using namespace std;
7
typedef pair<int,int>pii;
8
struct Node
9
{
10
  int L,R,id;
11
}b[500005];
12
struct Tree
13
{
14
  int L,R;
15
  pii val;
16
}T[2000005];
17
int a[500005],pre[500005],nxt[500005],h[500005],ans[500005];
18
inline void Modify(int L,int R,pii val,int v)
19
{
20
  if(L>T[v].R||R<T[v].L)return;
21
  if(L<=T[v].L&&R>=T[v].R)
22
  {
23
    T[v].val=max(T[v].val,val);return;
24
  }
25
  Modify(L,R,val,v<<1);
26
  Modify(L,R,val,(v<<1)|1);
27
  return;
28
}
29
inline pii Query(int x,int v)
30
{
31
  if(x>T[v].R||x<T[v].L)return make_pair(-inf,0);
32
  if(T[v].L==T[v].R)return T[v].val;
33
  return max(T[v].val,max(Query(x,v<<1),Query(x,(v<<1)|1)));
34
}
35
inline void Build(int L,int R,int v)
36
{
37
  T[v].L=L;T[v].R=R;
38
  T[v].val=make_pair(-inf,0);
39
  if(L==R)return;
40
  int mid=(L+R)>>1;
41
  Build(L,mid,v<<1);
42
  Build(mid+1,R,(v<<1)|1);
43
  return;
44
}
45
inline bool cmp(const Node& a,const Node& b)
46
{
47
  return a.R<b.R;
48
}
49
int main(void)
50
{
51
  int i,j=1,n,m;
52
  scanf("%d",&n);
53
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
54
  for(i=1;i<=n;++i)
55
  {
56
    if(!h[a[i]])pre[i]=0;
57
    else pre[i]=h[a[i]];
58
    h[a[i]]=i;
59
  }
60
  memset(h,0,sizeof(h));
61
  for(i=n;i>=1;--i)
62
  {
63
    if(!h[a[i]])nxt[i]=n+1;
64
    else nxt[i]=h[a[i]];
65
    h[a[i]]=i;
66
  }
67
  scanf("%d",&m);
68
  for(i=1;i<=m;++i)
69
  {
70
    scanf("%d%d",&b[i].L,&b[i].R);
71
    b[i].id=i;
72
  }
73
  sort(b+1,b+m+1,cmp);
74
  Build(1,n+1,1);
75
  for(i=1;i<=m;++i)
76
  {
77
    while(j<=b[i].R)Modify(pre[j]+1,j,make_pair(nxt[j],a[j]),1),++j;
78
    pii tmp=Query(b[i].L,1);
79
    if(tmp.first>=j)ans[b[i].id]=tmp.second;
80
  }
81
  for(i=1;i<=m;++i)printf("%d\n",ans[i]);
82
  return 0;
83
}