小红的双排列查询

期望： pts

实际： pts

#pragma GCC optimize(3,"Ofast")
#include <bits/stdc++.h>
#define v vector 
#define vi vector<int>
#define mi multiset<int>
#define int long long 
using namespace std;

const int maxa=2.5E5;
template<class T>vector<vector<T>>vertices(size_t n){return vector<vector<T>>(n);}

struct Qry {
    int l,r,id,m,bk;
    bool operator<(const Qry &other) const {if (bk!=other.bk) return bk<other.bk; return (bk&1)?(r<other.r):(r>other.r);}
};

int n, q;
vi a,ans,cnt,d;
v<Qry> q_;  
int tree[maxa]; 
void upt(int idx, int val) {
    while (idx<maxa) {tree[idx]+=val; idx+=idx&-idx;}
}
 
int qry(int idx) {
    int sum=0;
    while (idx) {sum+=tree[idx]; idx-=idx&-idx;}
    return sum;
}

void add(int x, mi &_s) {
    int _cnt=cnt[x];
    ++cnt[x];
    if (_cnt==2) {if (d[x]==0) {d[x]=1; upt(x,1);}} 
    else if (_cnt==1) {if (d[x]==1) {d[x]=0; upt(x,-1);}}
    _s.insert(x); 
}

void remove(int x, mi &_s) {
    auto it=_s.find(x); 
    if (it!=_s.end()) _s.erase(it); 
    int _cnt=cnt[x];
    --cnt[x]; //
    if (_cnt==2) {if (d[x]==0) {d[x]=1; upt(x,1);}} 
    else if (_cnt==3) {if (d[x]==1) {d[x]=0; upt(x,-1);}}
}
 
int get_max(mi &_s) {return _s.empty()?0:*_s.rbegin();}
 
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(NULL); 
    cin.rdbuf() -> pubsetbuf(NULL, 1<<20);
    cout.rdbuf() -> pubsetbuf(NULL, 1<<20);
    
    cin>>n>>q;
    a.resize(n); 
    for (int i=0; i<n; ++i) cin>>a[i];
    int bk_sz=sqrt(n);
    q_.resize(q); 
    for (int i=0; i<q; ++i) {
        int l,r; cin>>l>>r; --l;--r;
        int len=r-l+1;
        q_[i]={l,r,i,len/2,l/bk_sz};
    }
    
    sort(q_.begin(), q_.end()); 
    ans.resize(q,0);
    cnt.assign(maxa,0);
    d.assign(maxa,1); 
    memset(tree,0,sizeof(tree));
    
    for (int i=1; i<maxa; ++i) upt(i,1); 
    mi _s;
    int l_=0, r_=-1;
    for (auto & _q:q_) {
        int L=_q.l, R=_q.r, id=_q.id, m=_q.m;
        if ((R-L+1)%2!=0) {ans[id]=0; continue;}
        
        while (r_<R) add(a[++r_], _s);
        while (l_>L) add(a[--l_], _s);
        while (r_>R) remove(a[r_--], _s);
        while (l_<L) remove(a[l_++], _s);

        if (get_max(_s)>m) ans[id]=0;
        else ans[id]=(qry(m)==0);
    }
    for (int i=0; i<q; ++i) cout<<(ans[i]?"Yes\n":"No\n");
}