Znzryb's Blog

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

Posted on 2025-08-04 Edited on 2026-04-06

思路讲解

AC代码

源代码

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

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

Posted on 2025-08-04 Edited on 2026-04-06

思路讲解

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-04-06

思路讲解

【莫队算法【力扣双周赛 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/

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

P3812 【模板】线性基

Posted on 2025-08-01 Edited on 2026-04-06

思路讲解

【线性基【力扣周赛 460】】 https://www.bilibili.com/video/BV1pm8vzAEXx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

视频，我只推荐灵茶山艾府。

AC代码

https://www.luogu.com.cn/record/228289095

源代码

// by Gospel_rock
// from template_cpp
#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 vdb = vector<DB>;using vc=vector<char>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
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;
}
/*

*/
// https://www.luogu.com.cn/record/228289095
struct LB{
    ll n;vector<ll> b;
    LB(ll n=62){
        this->n=n;
        b.assign(n+5,0);
    }
    void insert(ll x){
        for(int i=n;i>=0;--i){
            if(x>>i&1){
                if(b[i]){
                    x^=b[i];
                }else{
                    b[i]=x;
                    return;
                }
            }
        }
    }
    ll findmx(){
        ll res=0;
        for(int i=n;i>=0;--i){
            if((res^b[i]) > res){
                res^=b[i];
            }
        }
        return res;
    }
};
inline void __(){
	cin>>N;
    vll A(N);
    LB lb;
	FOR(i,1,N){
        cin>>A[i-1];
        lb.insert(A[i-1]);
    }
    cout<<lb.findmx();
}
/*
AC
https://www.luogu.com.cn/record/228289095
*/

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

2025牛客暑期多校训练营5——K. Perfect Journey

Posted on 2025-08-01 Edited on 2026-04-06

思路讲解

下面把**“任意两点 u → v 经过哪些关键边”在 O(log n) 时间求出的方法补充得更细一些。**

给出两种写法：

A) 更快也更简单的一行式（查询 O(1)）

思路：

从根结点 root 出发 DFS，一路累积“根 → 当前结点”这条链上出现的关键边集合，记到数组 upMask[] 里。

1 2	upMask[child] = upMask[parent] \| (当前这条边是关键边 ? (1<<bit) : 0);

因为一条树上路径 (u,v) 可以分解成

root → u 和 root → v 两条链，而它们公共的部分（root → lca）在两条链里都会出现一次，

用异或就能把它抵消掉，所以

1 2	pathMask(u,v) = upMask[u] ^ upMask[v]; // O(1)

整条路径上恰好出现一次的边，正好就是 u-v 之间的那条简单路径。

预处理：一次 DFS，O(n)。
查询：连 LCA 都不用求，完全 O(1)。

AC代码

源代码