CF1000F One Occurrence

我们考虑离线询问，然后按照右端点排序来处理。对于当前的右端点，我们对每个值维护当询问左端点 $L$ 在一个区间（这个值最后一次出现到倒数第二次出现的位置之间），这个值就不是出现一次的。所以我们考虑的就是当前左端点是否被至少一个这种值覆盖。于是有了个显然的 2log 做法，每个点维护一个 set。。然后就 get 了一个 TLE。

于是考虑我们可以建立线段树表示当某个原数组位置的值想要作为右端点左端点得是多少。于是就变成了一个区间取最小值的问题。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define deadoralive puts("alive.")
typedef long long ll;
int n , m;
int A[MAXN];

struct que {
    int l , r , id;
    bool operator < ( const que x ) const {
        return r > x.r;
    }
} Q[MAXN] ;

bool cmp( que a , que b ) {
    return a.r == b.r ? a.l < b.l : a.r < b.r;
}

int T[MAXN << 2] , idx[MAXN << 2];
void pu( int rt ) {
    if( T[rt << 1] < T[rt << 1 | 1] ) T[rt] = T[rt << 1] , idx[rt] = idx[rt << 1];
    else T[rt] = T[rt << 1 | 1] , idx[rt] = idx[rt << 1 | 1];
}
int tim;
void mdfy( int rt , int l , int r , int p , int c ) {
    ++ tim;
    if( l == r ) { T[rt] = c , idx[rt] = l; return; }
    int m = l + r >> 1;
    if( p <= m ) mdfy( rt << 1 , l , m , p , c );
    else mdfy( rt << 1 | 1 , m + 1 , r , p , c );
    pu( rt );
}
int qwq;
pii que( int rt , int l , int r , int L , int R ) {
    if( L <= l && R >= r ) { return mp( T[rt] , idx[rt] ); }
    int m = l + r >> 1; pii ret = mp( 0x3f3f3f3f , 0 );
    if( L <= m ) ret = min( ret , que( rt << 1 , l , m , L , R ) );
    if( R > m ) ret = min( ret , que( rt << 1 | 1 , m + 1 , r , L , R ) );
    return ret;
}

int last[MAXN] , ans[MAXN];

void solve() {
    cin >> n;
    rep( i , 1 , n ) scanf("%d",A + i);
    cin >> m;
    rep( i , 1 , m ) {
        scanf("%d%d",&Q[i].l,&Q[i].r) , Q[i].id = i;
    }
    sort( Q + 1 , Q + m + 1 , cmp );
    int cur = 1 , x , y;
    memset( T , 0x3f , sizeof T );
    for( int i = 1 ; i <= n ; ++ i ) {
        qwq = i;
        if( last[A[i]] ) mdfy( 1 , 1 , n , last[A[i]] , 0x3f3f3f3f );
        mdfy( 1 , 1 , n , i , last[A[i]] + 1 );
        last[A[i]] = i;
        while( cur <= m && Q[cur].r == i ) {
            pii re = que( 1 , 1 , n , Q[cur].l , n );
            ans[Q[cur].id] = re.fi > Q[cur].l ? 0 : A[re.se];
            ++ cur;
        }
    }
    rep( i , 1 , m ) printf("%d\n",ans[i]);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}