3636.查询超过阈值频率最高元素（回滚莫队） · znzryb
## 思路讲解
【莫队算法【力扣双周赛 162】】 [https://www.bilibili.com/video/BV1p3h3zYEbc/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37](https://www.bilibili.com/video/BV1p3h3zYEbc/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37)
看视频吧，以我的理解
## AC代码
[https://leetcode.cn/problems/threshold-majority-queries/submissions/649553401/](https://leetcode.cn/problems/threshold-majority-queries/submissions/649553401/)
::: 源代码
```cpp
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cout << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
static constexpr ll MAXN=(ll)2e5+10,INF=(ll)1e17+9; // 1e18+9也是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
struct Que{
ll bid,l,r,w,i;
};
bool cmp(const Que &a,const Que &b){
if(a.bid!=b.bid) return a.bid<b.bid;
return a.r<b.r;
}
class Solution {
public:
vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
// vector<tuple<ll,ll,unordered_map<ll,ll> > > kuai;
ll Q=SZ(queries);
ll n=max(1ll,SZ(nums)/(ll)sqrtl(Q));
vector<int> ans(Q);
vector<Que> que;
FOR(i,0,Q-1){
ll l=queries[i][0],r=queries[i][1],w=queries[i][2];
ll bid=l/n; // 0based的话块的编号可以直接这么获取
ll rbid=r/n;
if(bid==rbid){ // 两者在一个块当中的，我们就先处理了
unordered_map<ll,ll> cnt;
ll lans=INF,mxc=0;
FOR(i,l,r){
cnt[nums[i]]++;
if(cnt[nums[i]]==mxc){
lans=min<ll>(lans,nums[i]);
}else if(cnt[nums[i]]>mxc){
mxc=cnt[nums[i]];
lans=nums[i];
}
}
if(lans==INF || mxc<w) ans[i]=-1;
else ans[i]=lans;
}else{
que.EB(bid,l,r,w,i);
}
}
sort(all(que),cmp);
ll lans=INF,mxc=0;
unordered_map<ll,ll> freq;
auto add=[&](ll num,ll cc){
freq[num]+=cc;
if(freq[num]==mxc){
lans=min(lans,num);
}else if(freq[num]>mxc){
mxc=freq[num];
lans=num;
}
};
auto minus=[&](ll num,ll cc){
freq[num]-=cc;
};
ll up=-1,upr=-1;
ll tmplans=INF,tmpmxc=0;
FOR(i,0,SZ(que)-1){
auto &[bid,l,r,w,id]=que[i];
if(bid==up){
up=bid;
// ll bidr=upper_bound(all(kk),r)-kk.begin()-1;
for(;upr<=r;++upr){
add(nums[upr],1);
}
tmplans=lans,tmpmxc=mxc; // 回滚莫队的精髓
FOR(j,l,min<ll>((bid+1)*n-1,SZ(nums)-1)){
add(nums[j],1);
}
if(lans==INF || mxc<w) ans[id]=-1;
else ans[id]=lans;
// 回滚操作
lans=tmplans,mxc=tmpmxc;
FOR(j,l,min<ll>((bid+1)*n-1,SZ(nums)-1)){
minus(nums[j],1);
}
}else{
lans=INF,mxc=0;freq.clear();
up=bid;upr=(bid+1)*n;
// ll bidr=upper_bound(all(kk),(pll){r,INF})-kk.begin()-1;
for(;upr<=r;++upr){
add(nums[upr],1);
}
tmplans=lans,tmpmxc=mxc; // 回滚莫队的精髓
FOR(j,l,min<ll>((bid+1)*n-1,SZ(nums)-1)){
add(nums[j],1);
}
if(lans==INF || mxc<w) ans[id]=-1;
else ans[id]=lans;
// 回滚操作
lans=tmplans,mxc=tmpmxc;
FOR(j,l,min<ll>((bid+1)*n-1,SZ(nums)-1)){
minus(nums[j],1);
}
}
}
return ans;
}
};
// 回滚莫队（哈希表）
// AC https://leetcode.cn/problems/threshold-majority-queries/submissions/649550425/
// 稍微优化了一下（还是用的是这个哈希表，把算块的换成了除法而已）
// AC https://leetcode.cn/problems/threshold-majority-queries/submissions/649553401/
```
:::
## 心路历程（WA，TLE，MLE……）