b417. 區間眾數

#pragma GCC optimzize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef complex<int> P;
#define X real()
#define Y imag()
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
int s[N];
int cnt[N];
int num[N];
int Max=0;
void add(int x){
    if(!x) return ;
    int c0=cnt[s[x]]++;
    num[c0]--;
    num[c0+1]++;
    if(Max<c0+1) Max=c0+1;
}
void sub(int x){
    if(!x) return ;
    int c0=cnt[s[x]]--;
    num[c0]--;
    num[c0-1]++;
    if(!num[Max]) Max--;
}
const int Q=1e6+7;
pii ans[Q];
int K;
struct query{
    int l;
    int r;
    int pos;
    int block;
    inline bool operator < (const query&o) const{
        if(block!=o.block) return block<o.block;
        //if(block&1) return r>o.r;
        return r<o.r;

    }
}qry[Q];
signed main(){
    quick
    int n,q;
    cin>>n>>q;
    K=n/sqrt(q*1.0);
    rep(i,1,n) cin>>s[i];
    rep(i,0,q-1){
        cin>>qry[i].l>>qry[i].r;
        qry[i].pos=i;
        qry[i].block=qry[i].l/K;
    }
    sort(qry,qry+q);
    Max=0;
    int l=0;
    int r=-1;
    rep(i,0,q-1){
        while(r<qry[i].r) add(++r);
        while(r>qry[i].r) sub(r--);
        while(l<qry[i].l) sub(l++);
        while(l>qry[i].l) add(--l);
        ans[qry[i].pos]=mp(Max,num[Max]);
    }
    rep(i,0,q-1){
        cout<<ans[i].F<<" "<<ans[i].S<<"\n";
    }

    return 0;
}