Znzryb's Blog

2025 牛客暑期多校训练营 7——Ivory（数学递推与gcd结合）

Posted on 2025-08-05 Edited on 2026-02-18

思路讲解

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78683868

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <functional>
#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) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #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 namespace std;

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 vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
ll binpow(ll a,ll k,const ll &p=mod){
    ll res=1;
    a%=p;
    while(k>0){
        if((k&1)==1) res=a*res%p;
        a=a*a%p;
        k>>=1;
    }
    return res;
}
inline void __(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    if(b>=d){
        swap(a,c);
        swap(b,d);
    }
    i128 ans=1;
    function<void(ll,ll,ll,ll)> dfs=[&](ll a,ll b,ll c,ll d){
        if(d>=b){  
            
        }else{
            swap(a,c);
            swap(b,d);
        }
        if(b==0 || d==0 || a==1 || c==1){
            return;
        }
        if(b<=1 && d<=1){
            if(b==0) a=1;
            if(d==0) c=1;
            ans*=__gcd(c,a);
            ans%=mod;
            return;
        }
        ll e=__gcd(a,c);
        ans*=binpow(e, b);
        ans%=mod;
        ll x=a/e;
        // dfs(e*x,b,e,b-d);
        dfs(x,b,e,d-b);
    };
    dfs(a,b,c,d);
    cout<<(ll)ans<<"\n";
}
/*
1
4 2 8 1
MLE
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78683716
TLE
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78683747

*/

心路历程（WA，TLE，MLE……）

这个循环退出条件特别容易忘记。

function<void(ll,ll,ll,ll)> dfs=[&](ll a,ll b,ll c,ll d){
    if(d>=b){  
        
    }else{
        swap(a,c);
        swap(b,d);
    }
    if(b==0 || d==0 || a==1 || c==1){
        return;
    }
    if(b<=1 && d<=1){
        if(b==0) a=1;
        if(d==0) c=1;
        ans*=__gcd(c,a);
        ans%=mod;
        return;
    }
    ll e=__gcd(a,c);
    ans*=binpow(e, b);
    ans%=mod;
    ll x=a/e;
    // dfs(e*x,b,e,b-d);
    dfs(x,b,e,d-b);
};

2025“钉耙编程”中国大学生算法设计暑期联赛（6）（2025杭电多校 6）——钥匙迷宫（dfs序）

Posted on 2025-08-05 Edited on 2026-02-21

题目大意

题目大意

给定一棵包含 $2n$ 个节点的树，树上分布着 $n$ 种钥匙（编号 $1$ 到 $n$ ）和 $n$ 种锁（编号 $1$ 到 $n$ ）。每种钥匙和每种锁在树上恰好出现一次。

节点信息由数组 $a$ 给出：

若 $a_i > 0$ ，表示该节点拥有编号为 $a_i$ 的钥匙。
若 $a_i < 0$ ，表示该节点拥有编号为 $-a_i$ 的锁。

移动与收集规则

出发点：必须选择一个拥有钥匙的节点作为起点。
钥匙获取：到达（或经过）拥有钥匙的节点时，自动获得该钥匙。钥匙永久保留。
通行限制：只有当手中拥有编号为 $k$ 的钥匙时，才能进入拥有编号为 $k$ 的锁的节点。

目标
对于每一种钥匙 $i$ （ $1 \le i \le n$ ），判断：如果从拥有钥匙 $i$ 的节点出发，是否能够遍历树的足够多部分，从而收集到全部 $n$ 种钥匙。

输入格式

第一行包含整数 $T$ ，表示测试数据组数。
每组数据包含：
- 整数 $n$ 。
- $2n$ 个整数 $a_1, \dots, a_{2n}$ ，表示节点上的物品。
- $2n-1$ 行，每行两个整数 $u, v$ ，表示树边。

输出格式
对于每组数据，输出一个长度为 $n$ 的 01字符串。

字符串第 $i$ 个字符对应编号为 $i$ 的钥匙作为起点的结果。
若能收集所有钥匙输出 1，否则输出 0。

样例

Input
4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6

Output
1
011
000
000

样例解释（以第二组数据为例）

配置： $n=3$ $n = 3$ 。
- 节点 1：锁 3 (-3)
- 节点 2：钥匙 2 (2)
- 节点 3：钥匙 1 (1)
- 节点 4：锁 1 (-1)
- 节点 5：钥匙 3 (3)
- 节点 6：锁 2 (-2)
- 边连接结构：4-2-1-3-6，且 2-5 相连。即 1 是中心，连接 2 和 3；2 连接 4 和 5；3 连接 6。

判定过程：
1. 从钥匙 1 出发（位于节点 3）：
- 初始拥有：{钥匙 1}。
- 相邻节点：节点 1（锁 3，无钥匙 3，不可入），节点 6（锁 2，无钥匙 2，不可入）。
- 结果：困在节点 3，无法收集所有。对应字符串第 1 位为 0。
1. 从钥匙 2 出发（位于节点 2）：
- 初始拥有：{钥匙 2}。
- 相邻节点：节点 1（锁 3，不可入），节点 4（锁 1，不可入），节点 5（钥匙 3，可入）。
- 移动到节点 5，获得钥匙 3。现有：{钥匙 2, 钥匙 3}。
- 回到节点 2，尝试进入节点 1（锁 3）。因有钥匙 3，可入。
- 到达节点 1 后，可前往节点 3（钥匙 1，可入）。获得钥匙 1。
- 现有：{钥匙 1, 2, 3}。收集完毕。对应字符串第 2 位为 1。
1. 从钥匙 3 出发（位于节点 5）：
- 初始拥有：{钥匙 3}。
- 前往节点 2（钥匙 2，可入）。获得钥匙 2。
- 现有：{钥匙 2, 3}。后续过程同上，可收集完毕。对应字符串第 3 位为 1。
最终输出：011。

思路讲解

首先，我们想到暴力，但是跑一次只需要 $O(n)$ ，也要 $O(n^2)$ 才能跑完。

于是面对这种复杂的问题，我们想到，需要分而治之。

我们先想，如果只有一个钥匙和一个门，那么合法的点在哪里那？

不难发现，肯定是在这边半颗树，也就是有钥匙的子树上的点才是合法的。

那么这个结论是非常显然的，那么现在问题在于我们有非常多的门，其实我们运用一下这个结论就会发现，我们只要不断往门上含有钥匙的子树上走，就行了，最后我们会得到一个联通块，检查一下这个联通块的联通性即可。

AC代码

https://vjudge.net/solution/64200130

源代码

// by Gospel_rock
#include <bitset>
#include <queue>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)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) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

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 vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll maxn = 210;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
struct Node{
    ll u;
    int isKey;
    bool operator<(const Node& o)const {
        return isKey<o.isKey;
    }
};
struct Solve {
    vll A;
    vector<vll> g;
    vll dir;
    vii isOpen;
    vii vis;
    vll waitKey;
    vii hasKey;
    // vii visDfs;
    Solve() {
        cin >> N;
        N*=2;
        A.resize(N + 5);
        g.resize(N + 5);
        dir.resize(N + 5);
        isOpen.resize(N + 5);
        vis.resize(N+5);
        waitKey.resize(N+5);
        hasKey.resize(N+5);
        // visDfs.resize(N+5);
        FOR(i, 1, N) { cin >> A[i]; }
        FOR(i, 1, N - 1) {
            ll u, v;
            cin >> u >> v;
            g[u].PB(v);
            g[v].PB(u);
        }
        ll door;
        FOR(i, 1, N) {
            if (A[i] < 0) {
                door = i;
                break;
            }
        }
        dfsm(door, door);
#ifdef LOCAL 
        debug(door);
        cerr << "dir:";
        FOR(i, 1, N) { cerr << dir[i] << " "; }
        cerr << "\n";
#endif
        dfs(door, door);
        priority_queue<Node> pq;
        FOR(i,0,SZ(valid)-1){
            vis[valid[i]]=true;
            pq.push({valid[i],1});
        }
        while (!pq.empty()) {
            auto [u,iskey]=pq.top();
            pq.pop();
            if (A[u] > 0) hasKey[A[u]] = 1;
            if(iskey){
                ll key=A[u];
                if(waitKey[key]){
                    vis[waitKey[key]]=true;
                    pq.push({waitKey[key],0});
                }
            }
            for(auto v:g[u]){
                if(vis[v]) continue;
                if(A[v]<0){
                    ll doorVal=abs(A[v]);
                    if(hasKey[doorVal]){
                        vis[v]=true;
                        pq.push({v,0});
                    }else{
                        waitKey[doorVal]=v;
                    }
                }else{
                    vis[v]=true;
                    pq.push({v,1});
                }
            }
        }
        bool ok=true;
        FOR(i,1,N){
            if(!vis[i]) {ok=false;break;}
        }
        if(!ok){
            FOR(i,1,N/2){
                cout<<0;
            }
            cout<<"\n";
            return;
        }
        vii ans(N/2+5);
        FOR(i,0,SZ(valid)-1){
            ans[A[valid[i]]]=1;
        }
        FOR(i,1,N/2){
            cout<<ans[i];
        }
        cout<<"\n";
#ifdef LOCAL
        cerr << "valid:";
        FOR(i, 0, SZ(valid) - 1) { cerr << valid[i] << " "; }
        cerr << "\n";
#endif

    }
    vll valid;
    // return 1 表示的是可以往下走
    // return 0 表示不可以往下走
    int dfs(ll u, ll fa) {
        ll dfsm;
        if (A[u] < 0) {
            if (dir[u] <= 0)
                return 0;
            valid.clear();
            dfs(dir[u], u);
            return 1;
        } else {
            valid.PB(u);
            for (auto v : g[u]) {
                if (v == fa)
                    continue;
                int ret=dfs(v, u);
                if(ret){
                    return 1;
                }
            }
            return 0;
        }
    }
    void dfsm(ll u, ll fa) {
        ll dfs;
        if (A[u] < 0) {
            ll doorKind = abs(A[u]);
            if (isOpen[doorKind]) {
                dir[u] = -1;
            }
            for (auto v : g[u]) {
                if (v == fa)
                    continue;
                dfsm(v, u);
                if (!dir[u] && isOpen[doorKind]) {
                    dir[u] = v;
                }
            }
        } else {
            isOpen[A[u]] = true;
            for (auto v : g[u]) {
                if (v == fa)
                    continue;
                dfsm(v, u);
            }
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        Solve a;
    return 0;
}
/*


hack：
1
3
-3 1 -2 3 2 -1
1 2
4 6
2 3
3 5
2 4

010

hack：
3
7
-1 5 -2 4 -3 3 2 -6 -7 7 6 -4 1 -5
1 3
8 13
1 2
2 4
5 14
4 12
6 10
6 8
4 5
3 6
6 7
5 9
8 11
8
3 -3 -2 7 -7 -1 6 2 -6 -5 8 5 -4 1 -8 4
1 3
1 10
10 12
12 14
1 4
2 7
4 5
1 2
7 13
6 8
4 15
10 16
8 11
8 9
2 6
5
-2 2 4 -3 3 1 -5 5 -4 -1
5 10
2 5
7 8
2 6
1 2
5 7
2 4
2 3
4 9

ans：
0000010
10001000
00001

*/

心路历程（WA，TLE，MLE……）

那么一开始，我们选择的是纯 dfs 解决该问题，但是 WA 了。

vll valid;
void dfs(ll u, ll fa) {
    ll dfsm;
    if (A[u] < 0) {
        if (dir[u] <= 0)
            return;
        valid.clear();
        dfs(dir[u], u);
    } else {
        valid.PB(u);
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            dfs(v, u);
        }
    }
}

主要原因是使用 dfs 时，没有一个全局的信息来参考。

比如下面这组 hack 数据，我的程序会错误地把 2，3 加入 valid 数组中，这个显然是有问题的。

这个其实是因为我们先走了节点 3 这条支路，又走了节点4。

于是我们继续在想，用树上差分固然可以解决此问题，但是总觉得有点杀鸡用牛刀了。使用纯 dfs 方案用办法解决此问题吗？

我们发现这个问题在于我们走完一条路了以后，我们需要知道这条路是封闭的，还是会继续往下走的？其实只要是会继续往下走的，其他路也不需要走了。

知道了这个以后，我们发现，其实不用改动很多，仅仅只需要加一个返回值，子树返回值为 1 时，我们直接开摆即可。

// return 1 表示的是可以往下走
// return 0 表示不可以往下走
int dfs(ll u, ll fa) {
    ll dfsm;
    if (A[u] < 0) {
        if (dir[u] <= 0)
            return 0;
        valid.clear();
        dfs(dir[u], u);
        return 1;
    } else {
        valid.PB(u);
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            int ret=dfs(v, u);
            if(ret){
                return 1;
            }
        }
        return 0;
    }
}

然后就 AC 了。

2025“钉耙编程”中国大学生算法设计暑期联赛（6）——cats 的 max

Posted on 2025-08-04 Edited on 2026-02-18

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

2025“钉耙编程”中国大学生算法设计暑期联赛（6）——传送排序

Posted on 2025-08-04 Edited on 2026-02-18

思路讲解

P2880 [USACO07JAN] Balanced Lineup G

用树状数组RMQ。

AC代码

https://acm.hdu.edu.cn/contest/view-code?cid=1177&rid=12260

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#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) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #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 namespace std;

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 vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
// by Gospel_rock znzryb
// 参考了（抄了）OIwiki
// https://www.luogu.com.cn/record/228807838 ST表模版题（max）
// https://www.luogu.com.cn/record/228809172 打乱了插入顺序，和上面是同一道
struct RMQ{
    using ll = long long;
    ll n;vector<ll> tr;bool ismax;vector<ll> origin;
    inline ll lowbit(const ll &x){
        return x&-x;
    }
    private:
    ll get(const ll &a,const ll &b){
        if(ismax){
            return max(a,b);
        }else{
            return min(a,b);
        }
    }
    ll set(){
        if(ismax) return -INF;
        else return INF;
    }
    public:
    RMQ(ll n,bool ismax=true){  // origin[i] 初始化就是 0
        this->n=n;this->ismax=ismax;
        if(ismax) tr.resize(n+5,-INF),origin.resize(n+5);
        else tr.resize(n+5,INF),origin.resize(n+5);
    }
    ll query(ll l,ll r){
        ll res=set();
        while (r>=l) {
            res=get(origin[r],res);
            r--;
            for(;r-lowbit(r)>=l;r-=lowbit(r)){ 
                res=get(res, tr[r]);
            }
        }
        return res;
    }
    void upd(ll p,ll x){    
        origin[p]=x;
        for(int i=p;i<=n;i+=lowbit(i)){     // 枚举受影响的区间
            tr[i]=origin[i];
            for(int j=1;j<lowbit(i);j<<=1){
                tr[i]=get(tr[i],tr[i-j]);
            }
        }
    }
};
  
inline void __(){
    cin>>N;
    vll A(N),pos(N+5);
    FOR(i,1,N){
        cin>>A[i-1];
        pos[A[i-1]]=i-1;
    }
    if(N==1){
        cout<<0<<"\n";
        return;
    }
    RMQ tr(N);
    vb vis(N+5);
    FOR(i,1,N){
        ll val=A[i-1];
        vis[val]=true;
        ll res=tr.query(1, val-1);
        if(res==-INF) res=0;
        ll lans=tr.origin[val-1]+vis[val-1]+(val==1 || val==N);
        //                      第一次WA是WA在这里
        lans=max(lans,res+(val==1 || val==N));
        tr.upd(val, lans);
    }
    ll ans=tr.query(1, N);
#ifdef LOCAL
    FOR(i,1,N){
        cerr<<tr.origin[i]<<" ";
    }
    cend;
#endif
    ans=N+1-ans;
    cout<<ans<<"\n";
}
/*
WA
https://acm.hdu.edu.cn/contest/view-code?cid=1177&rid=12203
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1177&rid=12260
*/

心路历程（WA，TLE，MLE……）

1和n的超距作用。

https://acm.hdu.edu.cn/contest/view-code?cid=1177&rid=12203

FOR(i,1,N){
    ll val=A[i-1];
    vis[val]=true;
    ll res=tr.query(1, val-1);
    if(res==-INF) res=0;
    ll lans=tr.origin[val-1]+vis[val-1]+(val==1 || val==N);
    //                      第一次WA是WA在这里
    lans=max(lans,res+(val==1 || val==N));
    tr.upd(val, lans);
}

3636.查询超过阈值频率最高元素（回滚莫队）

Posted on 2025-08-03 Edited on 2026-02-18

思路讲解

【莫队算法【力扣双周赛 162】】 https://www.bilibili.com/video/BV1p3h3zYEbc/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

看视频吧，以我的理解

AC代码

https://leetcode.cn/problems/threshold-majority-queries/submissions/649553401/

源代码

#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/