[TIOJ]1699. Problem I 害蟲決戰時刻

題目連結：http://tioj.infor.org/problems/1699

莫隊算法的經典題，區間眾數。
對數值離散化之後，開陣列紀錄數字 x 出現了幾次，以及有幾種數字出現了 y 次。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
struct Query{
    int l,r,k,id,lid;
    bool operator < (const Query & x) const{
        return lid == x.lid ? r < x.r : lid < x.lid;
    }
}q[1000005];
bitset<1000005> as;
int n,m,t,a[50005],ans;
int num[50005],cnt[50005];
void add(int x){
    cnt[num[x]]--;
    num[x]++;
    cnt[num[x]]++;
    ans = max(ans,num[x]);
}
void sub(int x){
    cnt[num[x]]--;
    num[x]--;
    cnt[num[x]]++;
    if(!cnt[ans])ans--;
}
void MO(){
    sort(q,q+m);
    int L = 1,R = 1;
    cnt[0] = n;
    add(a[L]);
    for(int i = 0 ; i < m ; i++){
        while(R < q[i].r)add(a[++R]);
        while(L > q[i].l)add(a[--L]);
        while(R > q[i].r)sub(a[R--]);
        while(L < q[i].l)sub(a[L++]);
        if(1.0 * ans >= 1.0 * (q[i].r-q[i].l+1)/q[i].k)as[q[i].id] = 1;
    }
    for(int i = 0 ; i < m ; i++)cout << (as[i] ? "Yes" : "No") << endl;
}
int main(){jizz
    cin >> n >> m;
    vector<int> v;
    for(int i = 1 ; i <= n ; i++)cin >> a[i],v.push_back(a[i]);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(int i = 1; i <= n ; i++)a[i] = lower_bound(v.begin(),v.end(),a[i])-v.begin();
    int s = sqrt(n)+1;
    for(int i = 0 ; i < m ; i++){
        cin >> q[i].l >> q[i].r >> q[i].k;
        q[i].id = i;
        q[i].lid = q[i].l/s;
    }
    MO();
    return 0;
}