CFR 622 C. Not Equal on a Segment ( TLE Mo's / AC Segment Tree )

Problem - C - Codeforces
すぐに思いついたのが mo'sだったが、実装が下手すぎてTLEした。
でも自分の書き方のバグに気付いた。
以前は
int lb = 2, rb = 1;　みたいなもの書いてすぐ適当に尺取りしていたが、
もしさきに lbを縮ませてしまうとまだ何も入ってないのでＲＥしてしまいます。
int lb = 1, rb = 0;　と書いて先に右へ動かせましょう。

// TLE
#include <bits/stdc++.h>
#pragma optimize ("O3")
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXA = 1e6 + 6;

int n, m;
int a[ MAXN ];

int BLK_SIZE;
int blk[ MAXN ];
struct Query{
    int id;
    int ql, qr, v;
    Query(int _l = -1, int _r = -1, int v = 0){}
    bool operator < (const Query &oth) const{
        if( blk[ ql ] != blk[ oth.ql ] )
            return blk[ ql ] < blk[ oth.ql ];
        return qr < oth.qr;
    }
} qry[ MAXM ];

multiset< int > has;
multiset< int > vis[ MAXA ];
int ans[ MAXM ];

void solve(){
    BLK_SIZE = sqrt( m ) + 1;
    for(int i = 1; i <= n; ++i)
        blk[ i ] = ( i - 1 ) / BLK_SIZE;
    sort( qry, qry + m );
    int lb = 1, rb = 0;
    for(int i = 0; i < m; ++i){
        int ql = qry[ i ].ql, qr = qry[ i ].qr;
        while( rb < qr ){
            ++rb;
            vis[ a[ rb ] ].insert( rb );
            has.insert( a[ rb ] );
        }
        while( rb > qr ){
            vis[ a[ rb ] ].insert( rb );
            has.erase( has.find( a[ rb ] ) );
            --rb;
        }
        while( lb > ql ){
            --lb;
            vis[ a[ lb ] ].insert( lb );
            has.insert( a[ lb ] );
        }
        while( lb < ql ){
            vis[ a[ lb ] ].erase( lb );
            has.erase( has.find( a[ lb ] ) );
            ++lb;
        }
        if( *has.begin() != qry[ i ].v )
            ans[ qry[ i ].id ] = *vis[ *has.begin() ].begin();
        else if( *( --has.end() ) != qry[ i ].v )
            ans[ qry[ i ].id ] = *vis[ *( --has.end() ) ].begin();
        else
            ans[ qry[ i ].id ] = -1;
    }
    for(int i = 0; i < m; ++i)
        printf("%d\n", ans[ i ]);
}

void readInt(int &x){
    char c; while( ( c = getchar() ) < '0' );
    for(x = c - '0'; ( c = getchar() ) >= '0'; x = x * 10 + c - '0');
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        readInt( a[ i ] ); // scanf("%d", &a[ i ]);
    for(int i = 0; i < m; ++i){
        qry[ i ].id = i;
        // scanf("%d%d%d", &qry[ i ].ql, &qry[ i ].qr, &qry[ i ].v);
        readInt( qry[ i ].ql ), readInt( qry[ i ].qr ), readInt( qry[ i ].v );
    }
    solve();
    return 0;
}

RMQ だけで処理するのが想定解らしい

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXA = 1e6 + 6;
const int INF = 1e9;
typedef pair< int, int > pii;

int n, m;
int a[ MAXN ];

struct itvt{
    int minv, maxv;
    int min_idx, max_idx;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1){
        lb = _l, rb = _r;
        minv = INF;
        maxv = -INF;
        lc = rc = NULL;
    }
    void pull(){
        if( lc->minv < rc->minv ){
            minv = lc->minv;
            min_idx = lc->min_idx;
        } else{
            minv = rc->minv;
            min_idx = rc->min_idx;
        }
        if( lc->maxv > rc->maxv ){
            maxv = lc->maxv;
            max_idx = lc->max_idx;
        } else{
            maxv = rc->maxv;
            max_idx = rc->max_idx;
        }
    }
    pii qmin(int ql, int qr){
        if( qr < lb || rb < ql ) return pii( INF, INF );
        if( ql <= lb && rb <= qr ) return pii( minv, min_idx );
        return min( lc->qmin( ql, qr ), rc->qmin( ql, qr ) );
    }
    pii qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return pii( -INF, -INF );
        if( ql <= lb && rb <= qr ) return pii( maxv, max_idx );
        return max( lc->qmax( ql, qr ), rc->qmax( ql, qr ) );
    }
} *root;

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ){
        t->minv = t->maxv = a[ lb ];
        t->min_idx = t->max_idx = lb;
        return t;
    }
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    root = buildItvt( 1, n );
    for(int i = 0; i < m; ++i){
        int l, r, x; scanf("%d%d%d", &l, &r, &x);
        pii mn = root->qmin( l, r );
        pii mx = root->qmax( l, r );
        if( mn.first != x ) printf("%d\n", mn.second);
        else if( mx.first != x ) printf("%d\n", mx.second);
        else puts("-1");
    }
    return 0;
}