Time Limits: 2000 ms Memory Limits: 131072 KB
Description
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
Input
第一行n,m。 第二行为n个数。 从第三行开始，每行一个询问l,r。
Output
一行一个数，表示每个询问的答案。
Sample Input
5 5 2 1 0 2 1 3 3 2 3 2 4 1 2 3 5
Sample Output
1 2 3 0 3
Data Constraint
对于30%的数据： 1<=n,m<=1000 对于100%的数据： 1<=n,m<=200000 0<=ai<=10^9 1<=l<=r<=n
Solution
主席树，记录每个值最晚出现的位置
Code
#include<algorithm>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std
;
const int N
=2e5+5,MX
=1e9;
int n
,m
,u
,v
,tot
,rt
[N
];
struct tree
{int l
,r
,mn
;}tr
[30*N
+N
];
void ins(int x
,int &y
,int l
,int r
,int id
)
{
y
=++tot
,tr
[y
]=tr
[x
];
if(l
==r
) {tr
[y
].mn
=id
; return;};
int mid
=(l
+r
)>>1;
if(u
<=mid
) ins(tr
[x
].l
,tr
[y
].l
,l
,mid
,id
);
else ins(tr
[x
].r
,tr
[y
].r
,mid
+1,r
,id
);
tr
[y
].mn
=min(tr
[tr
[y
].l
].mn
,tr
[tr
[y
].r
].mn
);
}
int ask(int x
,int l
,int r
)
{
if(l
==r
) return l
;
int mid
=(l
+r
)>>1;
if(tr
[tr
[x
].l
].mn
<u
) return ask(tr
[x
].l
,l
,mid
);
else return ask(tr
[x
].r
,mid
+1,r
);
}
int main()
{
scanf("%d%d",&n
,&m
);
fo(i
,1,n
)
{
scanf("%d",&u
);
ins(rt
[i
-1],rt
[i
],0,MX
,i
);
}
fo(i
,1,m
)
{
scanf("%d%d",&u
,&v
);
printf("%d\n",ask(rt
[v
],0,MX
));
}
}
