# cf1000F. One Occurrence(线段树 set)

## Sol

(真后悔没打这场EDU qwq)

```// luogu-judger-enable-o2
/*
*/
#include<bits/stdc++.h>
#define LL long long
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 2e6 + 10;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
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, a[MAXN], pre[MAXN], nxt[MAXN], ans[MAXN], date[MAXN], num = 0;
vector<Pair> q[MAXN];
void Des() {
for(int i = 1; i <= N; i++) date[i] = a[i];
sort(date + 1, date + N + 1);
num = unique(date + 1, date + N + 1) - date - 1;
for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date;
}
void Get() {
static int las[MAXN];
for(int i = 1; i <= N; i++) pre[i] = las[a[i]], las[a[i]] = i;
for(int i = 1; i <= N; i++) las[i] = N + 1;
for(int i = N; i >= 1; i--) nxt[i] = las[a[i]], las[a[i]] = i;
}
#define Getmid ((T[k].l + T[k].r) >> 1)
#define ls k << 1
#define rs k << 1 | 1
struct Node {
int l, r, mx;
}T[MAXN];
void update(int k) {
T[k].mx = max(T[ls].mx, T[rs].mx);
}
void Build(int k, int ll, int rr) {
T[k].l = ll; T[k].r = rr; T[k].mx = 0;
if(ll == rr) return ;
int mid = Getmid;
Build(ls, ll, mid); Build(rs, mid + 1, rr);
}
void Modify(int k, int pos, int v) {
if(T[k].l == T[k].r) {T[k].mx = v; return ;}
int mid = Getmid;
if(pos <= mid) Modify(ls, pos, v);
if(pos  > mid) Modify(rs, pos, v);
update(k);
}
int Query(int k, int ll, int rr) {
if(ll <= T[k].l && T[k].r <= rr) return T[k].mx;
int mid = Getmid, ans = 0;
if(ll <= mid) chmax(ans, Query(ls, ll, rr));
if(rr  > mid) chmax(ans, Query(rs, ll, rr));
return ans;
}
#undef ls
#undef rs
#undef Getmid
void Solve() {
set<int> s;
static vector<int> v[MAXN];
for(int i = 1; i <= N; i++) {
for(int j = 0; j < v[i].size(); j++) {
if(!pre[v[i][j]])
s.erase(v[i][j]);
else Modify(1, pre[v[i][j]], 0);
}
if(!pre[i])
s.insert(i);
else Modify(1, pre[i], i);

v[nxt[i]].push_back(i);
for(int j = 0; j < q[i].size(); j++) {
int t = Query(1, 1, q[i][j].fi - 1);
if(t >= q[i][j].fi) ans[q[i][j].se] = date[a[t]];
if(!s.empty()) {
set<int>::iterator it = s.end(); it--;
if(*it >= q[i][j].fi) ans[q[i][j].se] = date[a[*it]];
}

}

}
}
signed main() {
for(int i = 1; i <= N; i++) a[i] = read();
Des();
Get();
Build(1, 1, N + 1);
for(int i = 1; i <= M; i++) {
q[r].push_back(MP(l, i));
}
Solve();
for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
return 0;
}
/*
5
1 2 2 1 1
2
1 5
2 3

10
5 9 6 4 8 7 4 9 7 6
1
4 8
*/```

0 条评论

• ### P1983 车站分级

题目描述 一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一...

• ### 04:病毒

04:病毒 查看 提交 统计 提问 总时间限制:1000ms内存限制:65535kB描述     有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现...

• ### P1629 邮递员送信

题目描述 有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，...

• ### P1983 车站分级

题目描述 一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一...

• ### 395. Longest Substring with At Least K Repeating Characters

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元...

• ### 1545 最简单排序

个人博客：double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

• ### P2419 [USACO08JAN]牛大赛Cow Contest

题目背景 [Usaco2008 Jan] 题目描述 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are ...

• ### P1418 选点问题

题目描述 给出n个点，m条边，每个点能控制与其相连的所有的边，要求选出一些点，使得这些点能控制所有的边，并且点数最少。同时，任意一条边不能被两个点控制 输入输出...

• ### P1629 邮递员送信

题目描述 有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，...

• ### P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平，所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500)，每个单元格的海拔范围在0到10^9之...