欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

cf1000F. One Occurrence(线段树 set)

程序员文章站 2022-05-19 18:03:22
题意 "题目链接" Sol (真后悔没打这场EDU qwq) 首先把询问离线,预处理每个数的$pre, nxt$,同时线段树维护$pre$(下标是$pre$,值是$i$),同时维护一下最大值 那么每次在$(1, l 1)$内查询最大值,如果最大值$ = l$,那么说明合法 但是$pre$可能会有相同 ......

题意

题目链接

sol

(真后悔没打这场edu qwq)

首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

那么每次在\((1, l - 1)\)内查询最大值,如果最大值\(>= l\),那么说明合法

但是\(pre\)可能会有相同的情况(0),直接开个set维护一下

然后用vector对\(nxt\)维护一个类似差分的东西,在\(nxt_i\)的位置删除掉\(i\)的影响

// 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;}
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, 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() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    des();
    get();
    build(1, 1, n + 1);
    m = read();
    for(int i = 1; i <= m; i++) {
        int l = read(), r = read();
        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
*/