Codeforces 1000F One Occurrence 主席树|| 离线+线段树

时间:2021-04-20 15:43:52

One Occurrence

为什么我半年前这么菜呀, 这种场只A三题。。。

我们在主席树 || 线段树上维护每个数的右边和它一样的数在哪里, 然后就变成了区间求最大值。

注意加进去的时候要把它右边一样的数的信息删掉。

我懒得离线数据就写了个主席树。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 5e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, cnt, rt[N], b[N];
int Map[N]; struct node {
PII v;
int ls, rs;
} a[N * ]; void build(int l, int r, int& x) {
x = ++cnt;
if(l == r) {
a[x].v = mk(, l);
return;
}
int mid = l + r >> ;
build(l, mid, a[x].ls);
build(mid + , r, a[x].rs);
a[x].v = max(a[a[x].ls].v, a[a[x].rs].v);
} void update(int p, int val, int l, int r, int& x, int y) {
x = ++cnt; a[x] = a[y];
if(l == r) {
a[x].v.fi = val;
return;
}
int mid = l + r >> ;
if(p <= mid) update(p, val, l, mid, a[x].ls, a[y].ls);
else update(p, val, mid + , r, a[x].rs, a[y].rs);
a[x].v = max(a[a[x].ls].v, a[a[x].rs].v);
} PII query(int L, int R, int l, int r, int x) {
if(l >= L && r <= R) return a[x].v;
int mid = l + r >> ;
if(R <= mid) return query(L, R, l, mid, a[x].ls);
else if(L > mid) return query(L, R, mid + , r, a[x].rs);
else return max(query(L, R, l, mid, a[x].ls), query(L, R, mid + , r, a[x].rs));
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &b[i]);
for(int i = ; i <= ; i++) Map[i] = n + ;
build(, n, rt[n+]);
for(int i = n; i >= ; i--) {
update(i, Map[b[i]], , n, rt[i], rt[i + ]);
if(Map[b[i]] <= n) update(Map[b[i]], , , n, rt[i], rt[i]);
Map[b[i]] = i;
}
int q; scanf("%d", &q);
while(q--) {
int L, R; scanf("%d%d", &L, &R);
PII tmp = query(L, R, , n, rt[L]);
if(tmp.fi <= R) puts("");
else printf("%d\n", b[tmp.se]);
}
return ;
} /*
*/