Znzryb's Blog

影石Insta360杯-2025牛客暑期多校训练营9——AVL tree

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

思路讲解

这道题目的想法实际上非常暴力。

DP状态定义

dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。
- 注意：高度正好h，根u保留。
- 如果无法做到，设为INF（大数）。

问题描述

这道题给你一棵以节点1为根的二叉树（节点数n ≤ 2×10^5），但它可能不是AVL树（即高度平衡二叉树：每个节点左右子树高度差不超过1）。你可以通过三种操作来改造它：

删除一个叶子节点。
选择一个没有左孩子的节点，添加一个新节点作为它的左孩子。
选择一个没有右孩子的节点，添加一个新节点作为它的右孩子。

目标是求最小操作次数，使整棵树变成AVL树。注意：操作可以任意次，包括删除原有节点或添加新节点，但根节点1必须保留（因为AVL树定义包括根）。

多测试用例，T ≤ 10000，但总∑n ≤ 2×10^5。

解题思路

我们用树形动态规划（DP）来解决这个问题。核心是计算每个子树的最小代价，使其成为指定高度的AVL树。

关键概念

AVL树的定义：如题所述，空树高度0；否则高度 = max(左高, 右高) + 1，且|左高 - 右高| ≤ 1，且左右子树也是AVL。
操作的本质：
- 删除叶子：相当于 pruning（修剪）不需要的部分。
- 添加孩子：相当于在空位上建新子树。
- 要平衡树，我们可能需要删除整个子树（代价 = 子树大小，因为要逐个删除叶子），然后从头建一个平衡的子树（代价 = 新添加的节点数）。
最****小节点数的AVL树：对于高度h的AVL树，最小节点数m[h]满足：
- m[0] = 0（空树）
- m[1] = 1（单节点）
- m[h] = 1 + m[h-1] + m[h-2]（类似斐波那契，最小化节点：一侧高度h-1，另一侧h-2）
- 这可以预计算，h最高取60就够，因为m[60]已经很大，超过n的范围。

DP状态定义

dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。
- 注意：高度正好h，根u保留。
- 如果无法做到，设为INF（大数）。
最终答案：min over h (dp[1][h])，因为根树高度可以任意，只要平衡。

最关键的这个部分已经给出

vector<vll> dp(N+5,vll(H+5,INF));
dp[0][0]=0;
dp[0][1]=1;
FOR(h,2,H){
    dp[0][h]=dp[0][h-1]+dp[0][h-2]+1;
}
function<void (ll,ll)> dfs=[&](ll u,ll p){
    bool isleaf=true;
    vll wp;
    for(auto v:g[u]){
        if(v==p) continue;
        dfs(v,u);
        wp.EB(v);
        isleaf=false;
    }
    if(isleaf){
        dp[u][1]=0;
        dp[u][0]=1;
        FOR(h,2,H){
            dp[u][h]=dp[0][h]-1;
        }
        return;
    }
    if(SZ(wp)==1){
       wp.EB(0);
    }
    ll v=wp[0],v2=wp[1];
    vll ldp(H+5,INF),lldp(H+5,INF);
    FOR(h,1,H){
        ldp[h]=dp[v][h-1];
    }
    FOR(h,1,H){
        ldp[h]+=min({dp[v2][h-1],dp[v2][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        lldp[h]=dp[v2][h-1];
    }
    FOR(h,1,H){
        lldp[h]+=min({dp[v][h-1],dp[v][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        dp[u][h]=min(ldp[h],lldp[h]);
    }
    dp[u][0]=dp[u][1]+1;
    
};
dfs(1,1);

AC代码

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#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)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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;
}
/*
    1
   2  3
 4   6 7
fabo[30]:832040
#ifdef LOCAL
vll fabo(30+3);fabo={0,1,1};
FOR(i,3,30){
    fabo[i]=fabo[i-1]+fabo[i-2];
}
debug(fabo[30]);
#endif
*/
inline void __(){
    cin>>N;
    vector<vector<ll>> g(N+5);
    ll H=30;
    FOR(i,1,N){
        ll u,v;
        cin>>u>>v;
        if(u!=0) g[i].EB(u),g[u].EB(i);
        if(v!=0) g[i].EB(v),g[v].EB(i);
    }
    vector<vll> dp(N+5,vll(H+5,INF));
    dp[0][0]=0;
    dp[0][1]=1;
    FOR(h,2,H){
        dp[0][h]=dp[0][h-1]+dp[0][h-2]+1;
    }
    function<void (ll,ll)> dfs=[&](ll u,ll p){
        bool isleaf=true;
        vll wp;
        for(auto v:g[u]){
            if(v==p) continue;
            dfs(v,u);
            wp.EB(v);
            isleaf=false;
        }
        if(isleaf){
            dp[u][1]=0;
            dp[u][0]=1;
            FOR(h,2,H){
                dp[u][h]=dp[0][h]-1;
            }
            return;
        }
        if(SZ(wp)==1){
           wp.EB(0);
        }
        ll v=wp[0],v2=wp[1];
        vll ldp(H+5,INF),lldp(H+5,INF);
        FOR(h,1,H){
            ldp[h]=dp[v][h-1];
        }
        FOR(h,1,H){
            ldp[h]+=min({dp[v2][h-1],dp[v2][h-2<0?0:h-2]});
        }
        FOR(h,1,H){
            lldp[h]=dp[v2][h-1];
        }
        FOR(h,1,H){
            lldp[h]+=min({dp[v][h-1],dp[v][h-2<0?0:h-2]});
        }
        FOR(h,1,H){
            dp[u][h]=min(ldp[h],lldp[h]);
        }
        dp[u][0]=dp[u][1]+1;
        
    };
    dfs(1,1);
    ll ans=minn(dp[1]);
#ifdef LOCAL
    FOR(i,1,N){
        _print(dp[i]);
    }
#endif
    cout<<ans<<"\n";
}
/*

*/

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

P1471 方差

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

思路讲解

AC代码

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

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cfloat>
#include <vector>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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 __();
// 参考了（抄了）beta99999 的提交  https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
template <typename T,typename value_type> struct base_segtree{
    int n,sz;
    vector<value_type> tr,trsq;
    static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
    // zkw线段树开两倍大小，identity为默认值
    base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity),trsq(sz<<1,T::identity){}    
    T *derived() { return static_cast<T*>(this); }
    void pushup(int o){
        tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
        trsq[o]=T::op(trsq[o<<1],trsq[o<<1|1]);
    }

    // zkw选配  
    int dis(int o){return __lg(sz)-__lg(o);}    // 倒数第几层？有倒数第0层
    int len(int o){return 1<<dis(o);}   // （直接调用就可以，就是左闭右开区间长度）
    int le(int o){return (o<<dis(o))-sz; }  // 左闭
    int rr(int o){return (o+1<<dis(o))-sz;} // 右开

    // 单节点的下推 在子类中实现
    // void pushdown(int o){}
    void call_pushdown(int i){  // 把路径上的所有点向下推
        int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
        for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
            derived()->pushdown(o>>k);
        }
    }
    void call_pushup(int i){
        int o=i+sz;
        // 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
        for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
            derived()->pushup(o>>k);
        }
    }
    void build(){
        for(int o=sz-1;o>=1;--o){
            derived()->pushup(o);
        }
    }
    template<typename D> 
    void update(int l,int r,D x){
        call_pushdown(l),call_pushdown(r);
        int l0=l,r0=r;l+=sz,r+=sz;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) derived()->settag(l++,x);
            if(r&1) derived()->settag(--r,x);  // 毕竟是右开区间
        }
        call_pushup(l0);call_pushup(r0);
    }
    value_type query(int l, int r){
        call_pushdown(l);call_pushdown(r);
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) resl=T::op(resl,tr[l++]);
            if(r&1) resr=T::op(tr[--r],resr);
        }
        return T::op(resl,resr);
    }
    value_type querysq(int l, int r){
        call_pushdown(l);call_pushdown(r);
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) resl=T::op(resl,trsq[l++]);
            if(r&1) resr=T::op(trsq[--r],resr);
        }
        return T::op(resl,resr);
    }
    void assign(int i,value_type a){
        tr[i+sz]=a;
        trsq[i+sz]=a*a;
    }
};
// 主要要重载pushdown，构造函数，静态函数op，settag
struct segtree:base_segtree<segtree, DB>{
    static constexpr DB identity = 0;
    static DB op(const DB &a,const DB &b){
        return a+b;
    }
    vdb tag;
    segtree(int n):base_segtree(n),tag(sz,identity){}
    void settag(int o,DB x){
        ll ln=len(o);
        trsq[o]+=(2*tr[o]*x+ln*x*x);
        tr[o]+=x*ln;
        if(o<sz) tag[o]+=x;
    }
    void pushdown(int o){
        if(o>=sz) return;
        if(abs(tag[o])<eps) return;
        settag(o<<1,tag[o]);
        settag(o<<1|1, tag[o]);
        tag[o]=0;
    }
};
constexpr DB segtree::identity;

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

*/
inline void __(){
    cin>>N>>Q;
    segtree tr(N);
    FOR(i,0,N-1){
        DB a;
        cin>>a;
        tr.assign(i, a);
    }
    tr.build();
    FOR(i,1,Q){
        ll op,l,r;
        cin>>op>>l>>r;
        DB len=r-l+1;
        if(op==1){
            DB x;cin>>x;
            tr.update(l-1, r, x);
        }else if(op==2){
            DB res=tr.query(l-1, r)/len;
            cout<<fsp(4)<<res<<"\n";
        }else{
            DB sum=tr.query(l-1, r),sumsq=tr.querysq(l-1, r);
            DB aver=sum/len;
            DB res=sumsq/len-aver*aver;
            // DB res=sumsq-2*sum*aver+aver*aver*len;
            // res/=len;
            cout<<fsp(4)<<res<<"\n";
        }
    }
}
/*
AC
https://www.luogu.com.cn/record/230330272
8 15
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22 
3 1 8
1 2 8 -2.7566713364794850E+0000
1 2 8  2.1308819339610636E+0000
1 1 6  1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330E+0000
1 1 7  2.5193137815222144E+0000
1 3 8  1.2835426828823984E+0000
3 3 8

ans:
7.4145
5.2609
6.2101
1.8256
6.1810
5.8854

暴力程序打出来的每一次操作后区域内的sqsum的值
sqsum:323.127
allsqsum:323.127
71.5716 36.3609 13.9129 0.1024 55.2049 13.7641 64.6416 67.5684 
sqsum:98.1098
allsqsum:169.681
71.5716 10.7147 0.947369 5.93737 21.84 0.908836 27.9136 29.848 
sqsum:207.387
allsqsum:278.959
71.5716 29.2055 9.63612 0.0935072 46.2973 9.51236 54.9705 57.672 
sqsum:266.01
allsqsum:378.652
101.028 48.9369 22.0477 1.65249 70.4843 21.8602 54.9705 57.672 
sqsum:156.444
allsqsum:156.444
52.9018 17.7879 3.67708 2.22734 31.5571 3.60078 21.4952 23.1966 
sqsum:122.211
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468 
sqsum:78.3601
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468 
sqsum:66.8385
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:49.453
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:42.7848
allsqsum:83.4041
33.2653 7.35396 2.13736 23.7361 5.00877 2.19624 4.45696 5.24938 
sqsum:147.84
allsqsum:153.09
68.6731 27.3647 1.11797 5.535 22.6323 1.07608 21.4412 5.24938 
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784 
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784 


*/

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

最优解。

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

线段树内部之间不要相互调用

P1471 方差

千万不要这么干，因为不仅更新的时候要调用，下传标记也要调用，你能保证两个线段树的懒标记状态一样吗？这个是不可能的，因为你也不可能同时更新，询问两个线段树，除非把他们合为一个。

错误代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cfloat>
#include <vector>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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 __();
// 参考了（抄了）beta99999 的提交  https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
template <typename T,typename value_type> struct base_segtree{
    int n,sz;
    vector<value_type> tr;
    static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
    // zkw线段树开两倍大小，identity为默认值
    base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}    
    T *derived() { return static_cast<T*>(this); }
    value_type val(int o){
        // if(o<sz) return tr[o];
        // int i=o-sz;
        // if(i>=n) return T::identity; 
        return tr[o];
    }
    void pushup(int o){
        tr[o]=T::op(val(o<<1),val(o<<1|1));
    }

    // zkw选配  
    int dis(int o){return __lg(sz)-__lg(o);}    // 倒数第几层？有倒数第0层
    int len(int o){return 1<<dis(o);}   // （直接调用就可以，就是左闭右开区间长度）
    int le(int o){return (o<<dis(o))-sz; }  // 左闭
    int rr(int o){return (o+1<<dis(o))-sz;} // 右开

    // 单节点的下推 在子类中实现
    // void pushdown(int o){}
    void call_pushdown(int i){  // 把路径上的所有点向下推
        int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
        for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
            derived()->pushdown(o>>k);
        }
    }
    void call_pushup(int i){
        int o=i+sz;
        // 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
        for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
            derived()->pushup(o>>k);
        }
    }
    void build(){
        for(int o=sz-1;o>=1;--o){
            derived()->pushup(o);
        }
    }
    template<typename D> 
    void update(int l,int r,D x){
        call_pushdown(l),call_pushdown(r);
        int l0=l,r0=r;l+=sz,r+=sz;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) derived()->settag(l++,x);
            if(r&1) derived()->settag(--r,x);  // 毕竟是右开区间
        }
        call_pushup(l0);call_pushup(r0);
    }
    value_type query(int l, int r){
        call_pushdown(l);call_pushdown(r);
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
#ifdef LOCAL
    debug(l);debug(r);
#endif
            if(l&1) resl=T::op(resl,val(l++));
            if(r&1) resr=T::op(val(--r),resr);
        }
        return T::op(resl,resr);
    }
    value_type& operator[](int i) {
        return tr[i + sz];
    }
    // value_type get(int o){
    //     // for(int i=__lg(o);i>=__builtin_ctz(o)+1;--i){
    //     //     derived()->pushdown(o>>i);
    //     // }
    //     call_pushdown(le(o));call_pushdown(rr(o));
    //     return tr[o];
    // }
};
// 主要要重载pushdown，构造函数，静态函数op，settag
struct segtree:base_segtree<segtree, DB>{
    static constexpr DB identity = 0;
    static DB op(const DB &a,const DB &b){
        return a+b;
    }
    vdb tag;
    segtree(int n):base_segtree(n),tag(sz,identity){}
    void settag(int o,DB x){
        ll ln=len(o);
        tr[o]+=x*ln;
        if(o<sz) tag[o]+=x;
    }
    void pushdown(int o){
        if(o>=sz) return;
        if(abs(tag[o])<eps) return;
        settag(o<<1,tag[o]);
        settag(o<<1|1, tag[o]);
        tag[o]=0;
    }
};
struct sqsegtree:base_segtree<sqsegtree, DB>{
    static constexpr DB identity = 0;
    static DB op(const DB &a,const DB &b){
        return a+b;
    }
    segtree& yici;  // 指向外部的segtree实例
    vdb tag;
    sqsegtree(int n,segtree & yici):base_segtree(n),yici(yici),tag(sz,identity){}
    void settag(int o,DB x){
        DB cursum=yici.query(le(o),rr(o));
        ll ln=len(o);
// #ifdef LOCAL
//     debug(cursum);debug(tr[o]);
// #endif
        tr[o]+=(2*cursum*x+ln*x*x);
        if(o<sz) tag[o]+=x;
    }
    void pushdown(int o){
        if(o>=sz) return;
        if(abs(tag[o])<eps) return;
        settag(o<<1,tag[o]);
        settag(o<<1|1, tag[o]);
        tag[o]=0;
    }
};
constexpr DB segtree::identity;
constexpr DB sqsegtree::identity;

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

*/
inline void __(){
    cin>>N>>Q;
    segtree yici(N);
    sqsegtree square(N,yici);
    FOR(i,0,N-1){
        DB a;
        cin>>a;
        // square.update(i, i+1, a);
        // yici.update(i, i+1, a);
        square[i]=a*a;
        yici[i]=a;
    }
    square.build();yici.build();
    FOR(i,1,Q){
        ll op,l,r;
        cin>>op>>l>>r;
        DB len=r-l+1;
        if(op==1){
            DB x;cin>>x;
            square.update(l-1, r, x);
            yici.update(l-1, r, x);
        }else if(op==2){
            DB res=yici.query(l-1, r)/len;
            cout<<fsp(4)<<res<<"\n";
        }else{
            DB sum=yici.query(l-1, r),sumsq=square.query(l-1, r);
            DB aver=sum/len;
            DB res=sumsq/len-aver*aver;
            // DB res=sumsq-2*sum*aver+aver*aver*len;
            // res/=len;
            cout<<fsp(4)<<res<<"\n";
        }
#ifdef LOCAL
    FOR(j,1,N){
        cerr<<square.query(j-1,j)<<" ";
    }
    cerr<<"\n";
#endif
        
    }
}
/*
8 15
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22 
3 1 8
1 2 8 -2.7566713364794850E+0000
1 2 8  2.1308819339610636E+0000
1 1 6  1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330E+0000
1 1 7  2.5193137815222144E+0000
1 3 8  1.2835426828823984E+0000
3 3 8

ans:
7.4145
5.2609
6.2101
1.8256
6.1810
5.8854

暴力程序打出来的每一次操作后区域内的sqsum的值
sqsum:323.127
allsqsum:323.127
71.5716 36.3609 13.9129 0.1024 55.2049 13.7641 64.6416 67.5684 
sqsum:98.1098
allsqsum:169.681
71.5716 10.7147 0.947369 5.93737 21.84 0.908836 27.9136 29.848 
sqsum:207.387
allsqsum:278.959
71.5716 29.2055 9.63612 0.0935072 46.2973 9.51236 54.9705 57.672 
sqsum:266.01
allsqsum:378.652
101.028 48.9369 22.0477 1.65249 70.4843 21.8602 54.9705 57.672 
sqsum:156.444
allsqsum:156.444
52.9018 17.7879 3.67708 2.22734 31.5571 3.60078 21.4952 23.1966 
sqsum:122.211
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468 
sqsum:78.3601
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468 
sqsum:66.8385
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:49.453
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468 
sqsum:42.7848
allsqsum:83.4041
33.2653 7.35396 2.13736 23.7361 5.00877 2.19624 4.45696 5.24938 
sqsum:147.84
allsqsum:153.09
68.6731 27.3647 1.11797 5.535 22.6323 1.07608 21.4412 5.24938 
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784 
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784 


*/

2025钉耙编程-中国大学生算法设计暑期联赛（8）——最努力的活着

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

思路讲解

暴力程序是这样的。

i128 ans=0;
while(true){
    if(n<W) break;
    ans+=(1+N)*N/2-(sum+1)*sum/2;
    sum+=n/W;
    n-=n/W;
}
ans+=(1+N)*N/2-(sum+1)*sum/2;

不难发现，我们可以分块处理相同n/W的部分，以获得logn的时间复杂度。

AC代码

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

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cstdio>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = __int128;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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
i128 N,M,Q,X,K,T,lT,W;

inline void __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
i128 ans=0;
// void calres(ll n,ll obj,ll step){
//     // i128 l=(i128)N*(N-1)/2-(i128)(N-obj+1)*(N-obj)/2;
//     // i128 r=(i128)N*(N-1)/2-(i128)(N-n+1)*(N-n)/2;
//     i128 num=n-obj;
//     i128 l=(i128)(N-n+1)*(N-n)/2;
//     i128 r=(i128)(N-obj+1)*(N-obj)/2;
//     i128 res=(i128)(N+1)*N/2*((n-obj+1)/step)-(l+r)*((n-obj+1)/step)/2;
// #ifdef LOCAL
//     debug(n);debug(obj);
//     debug((ll)l);debug((ll)r);debug((ll)res);
//     cend;
// #endif
//     ans+=res;
// }
void calres(i128 n,i128 obj,i128 step,i128 num){
    i128 sum=(N+1)*N/2*num;
    i128 fn=N-n,fob=N-(obj+step);
    // =(fn+jd)^2
    i128 sumsq=num*(num-1)*(2*num-1)/6;
    i128 minus=fn*fn*num+sumsq*step*step+2*fn*(num-1+0)*num/2*step;
    minus+=(fn+fob)*num/2;
    minus/=2;
    ans+=sum-minus;
}
// ceil_div
template<typename T> T chu(T x,T y) {
    if ((x ^ y) < 0) return x / y;
    if (x % y == 0) return x / y;
    return x / y + 1;
}

inline void __(){
    Cin(N,W);
    i128 n=N;
    ans=0;
    while(true){
        if(n<W) break;
        i128 step=n/W;
        i128 obj=W*(n/W)-1;
        ll num=chu((n-obj),step);
        obj=n-step*num;
        calres(n, obj,n/W,num);
        n=obj;
    }
    ans+=(1+N)*N/2-(i128)(N-n+1)*(N-n)/2;
    write(ans);putchar('\n'); 
}
/*
前面因为long long溢出WA了一发
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14726
(1+N)*N/2-(sum+1)*sum/2:15
(1+N)*N/2-(sum+1)*sum/2:12
(1+N)*N/2-(sum+1)*sum/2:9
(1+N)*N/2-(sum+1)*sum/2:5

1
7 4

n:7
(1+N)*N/2-(sum+1)*sum/2:28
n:6
(1+N)*N/2-(sum+1)*sum/2:27
n:5
(1+N)*N/2-(sum+1)*sum/2:25
n:4
(1+N)*N/2-(sum+1)*sum/2:22
n:3
(1+N)*N/2-(sum+1)*sum/2:18
*/

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

容易发现，fob的计算一定是交给后面算的，就算是最后一个也是。

2025“钉耙编程”中国大学生算法设计暑期联赛（7）——龙族栖息地

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

思路讲解

AC代码

源代码

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

2025“钉耙编程”中国大学生算法设计暑期联赛（7）——矩形框选

Posted on 2025-08-08 Edited on 2026-03-14

思路讲解

我的做法还是我的做法，就是需要用zkw线段树卡一下常

复杂度是 $O(\sqrt k \times N \times \log(n))$ 。

AC代码

https://acm.hdu.edu.cn/contest/status?cid=1178&rid=15857

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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;
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

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

*/
// AC https://www.luogu.com.cn/record/229740484 P1253 扶苏的问题
// https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15813 卡常卡过去了
template <typename T, typename value_type> struct base_segtree {
    static constexpr bool zkw = 0;
    static constexpr bool custom_leaf = 0;
    static constexpr bool pushdown_when_update = 1;

    int n, sz;
    vector<value_type> data;

    base_segtree(int n): n(n), sz(T::zkw ? bit_ceil(n) : n), data(sz << !T::custom_leaf, T::identity) {}
    static int bit_ceil(int n) { int k = 1; while (k < n) k <<= 1; return k; }

    T *derived() { return static_cast<T*>(this); }
    value_type val(int o) { 
        return val_impl(o, typename std::integral_constant<bool, T::custom_leaf>::type{});
    }
private:
    value_type val_impl(int o, std::true_type) {
        if (o < sz) return data[o];
        int i = o - sz;
        if (i >= n) return T::identity;
        return derived()->get_leaf(i);
    }
    value_type val_impl(int o, std::false_type) {
        return data[o];
    }
public:
    value_type get_leaf(int i) { return T::identity; }
    void pushup(int o) {
        data[o] = T::op(val(o << 1), val(o << 1 | 1));
    }
    void pushdown(int o) {}
    void call_pushdown(int i) { 
        int o = i + sz;
        for (int k = lg(o); k >= __builtin_ctz(o) + 1; k--) derived()->pushdown(o >> k); 
    }   
    void call_pushup(int i) { 
        int o = i + sz;
        for (int k = __builtin_ctz(o) + 1; k <= lg(o); k++) derived()->pushup(o >> k); 
    }
    value_type& operator[](int i) {
        static_assert(!T::custom_leaf, "custom leaf do not support operator[]");
        return data[i + sz];
    }
    void build() { 
        for(int o = sz - 1; o >= 1; o--) derived()->pushup(o); 
    }
    template <typename D> void update(int l, int r, D x) {
        if (T::pushdown_when_update) call_pushdown(l), call_pushdown(r);
        int l0 = l, r0 = r; l += sz, r += sz;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) derived()->settag(l++, x);
            if (r & 1) derived()->settag(--r, x);
        }
        call_pushup(l0), call_pushup(r0);
    }
    value_type ask(int l, int r) {
        call_pushdown(l), call_pushdown(r);
        l += sz, r += sz;
        value_type resl = T::identity, resr = T::identity;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = T::op(resl, val(l++));
            if (r & 1) resr = T::op(val(--r), resr);
        }
        return T::op(resl, resr);
    }
    static int lg(int x) {
        return x == 0 ? -1 : 31 - __builtin_clz(x);
    }
};

struct segtree: base_segtree<segtree, ll> {
    static constexpr bool zkw = 1;
    static constexpr ll identity = -INF;
   
    static ll op(ll a, ll b) { return max(a, b); }
    vector<ll> tag;
    vector<bool> fixed;
    segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
    segtree(const vector<ll>& a): base_segtree(a.size()), tag(sz), fixed(sz) {
        for(int i = 0; i < (int)a.size(); i++) (*this)[i] = a[i];
        build();
    }
    void settag(int o, pair<int, ll> t) {
        int op = t.first;
        ll x = t.second;
        if (op == 1) {
            data[o] = x;
            if (o < sz) tag[o] = 0, fixed[o] = 1;
        } else {
            data[o] += x;
            if (o < sz && !fixed[o]) tag[o] += x;
        }
    }
    void pushdown(int o) {
        if (fixed[o]) {
            settag(o << 1, make_pair(1, data[o]));
            settag(o << 1 | 1, make_pair(1, data[o]));
            fixed[o] = 0;
        }
        if (tag[o]) {
            settag(o << 1, make_pair(2, tag[o]));
            settag(o << 1 | 1, make_pair(2, tag[o]));
            tag[o] = 0;
        }
    }
};
// 注意调用的时候是左开右闭区间，0-based，具体来讲[l,r]->[l-1,r)
// tr.update(0,N,(pll){1,0})    是清空操作
// C++14需要为static constexpr成员提供定义
constexpr bool segtree::zkw;
constexpr ll segtree::identity;

inline void __(){
    Cin(N,K);
    vector<vpll> xyv(N+5);
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xyv[x].EB(y,v);
    }
    ll ans=0;
    segtree tr(N);
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        FOR(x,1,min(xlen,N)){
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
        }
        ans=max(ans,tr.ask(0, N));
        FOR(x,xlen+1,N){
            ll qv=x-xlen;
            for(auto&[y,v]:xyv[qv]){
                tr.update(max(0ll,y-ylen),y,(pll){2,-v});
            }
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    FOR(i,1,sqrtl(K)){
        ll ylen=i,xlen=K/i;
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        FOR(x,1,min(xlen,N)){
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
        }
        ans=max(ans,tr.ask(0, N));
        FOR(x,xlen+1,N){
            ll qv=x-xlen;
            for(auto&[y,v]:xyv[qv]){
                tr.update(max(0ll,y-ylen),y,(pll){2,-v});
            }
            for(auto&[y,v]:xyv[x]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    write(ans);
    putchar('\n');
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15857
*/

稍微优化过的版本，不过这两个都比较卡着这个时限。

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

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <numeric>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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 __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;

// AC https://www.luogu.com.cn/record/229740484 P1253 扶苏的问题
template <typename T, typename value_type> struct base_segtree {
    static constexpr bool zkw = 0;
    static constexpr bool custom_leaf = 0;
    static constexpr bool pushdown_when_update = 1;

    int n, sz;
    vector<value_type> data;

    base_segtree(int n): n(n), sz(T::zkw ? bit_ceil(n) : n), data(sz << !T::custom_leaf, T::identity) {}
    static int bit_ceil(int n) { int k = 1; while (k < n) k <<= 1; return k; }

    T *derived() { return static_cast<T*>(this); }
    value_type val(int o) { 
        return val_impl(o, typename std::integral_constant<bool, T::custom_leaf>::type{});
    }
private:
    value_type val_impl(int o, std::true_type) {
        if (o < sz) return data[o];
        int i = o - sz;
        if (i >= n) return T::identity;
        return derived()->get_leaf(i);
    }
    value_type val_impl(int o, std::false_type) {
        return data[o];
    }
public:
    value_type get_leaf(int i) { return T::identity; }
    void pushup(int o) {
        data[o] = T::op(val(o << 1), val(o << 1 | 1));
    }
    void pushdown(int o) {}
    void call_pushdown(int i) { 
        int o = i + sz;
        for (int k = lg(o); k >= __builtin_ctz(o) + 1; k--) derived()->pushdown(o >> k); 
    }   
    void call_pushup(int i) { 
        int o = i + sz;
        for (int k = __builtin_ctz(o) + 1; k <= lg(o); k++) derived()->pushup(o >> k); 
    }
    value_type& operator[](int i) {
        static_assert(!T::custom_leaf, "custom leaf do not support operator[]");
        return data[i + sz];
    }
    void build() { 
        for(int o = sz - 1; o >= 1; o--) derived()->pushup(o); 
    }
    template <typename D> void update(int l, int r, D x) {
        if (T::pushdown_when_update) call_pushdown(l), call_pushdown(r);
        int l0 = l, r0 = r; l += sz, r += sz;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) derived()->settag(l++, x);
            if (r & 1) derived()->settag(--r, x);
        }
        call_pushup(l0), call_pushup(r0);
    }
    value_type ask(int l, int r) {
        call_pushdown(l), call_pushdown(r);
        l += sz, r += sz;
        value_type resl = T::identity, resr = T::identity;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = T::op(resl, val(l++));
            if (r & 1) resr = T::op(val(--r), resr);
        }
        return T::op(resl, resr);
    }
    static int lg(int x) {
        return x == 0 ? -1 : 31 - __builtin_clz(x);
    }
};

struct segtree: base_segtree<segtree, ll> {
    static constexpr bool zkw = 1;
    static constexpr ll identity = -INF;
   
    static ll op(ll a, ll b) { return max(a, b); }
    vector<ll> tag;
    vector<bool> fixed;
    segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
    segtree(const vector<ll>& a): base_segtree(a.size()), tag(sz), fixed(sz) {
        for(int i = 0; i < (int)a.size(); i++) (*this)[i] = a[i];
        build();
    }
    void settag(int o, pair<int, ll> t) {
        int op = t.first;
        ll x = t.second;
        if (op == 1) {
            data[o] = x;
            if (o < sz) tag[o] = 0, fixed[o] = 1;
        } else {
            data[o] += x;
            if (o < sz && !fixed[o]) tag[o] += x;
        }
    }
    void pushdown(int o) {
        if (fixed[o]) {
            settag(o << 1, make_pair(1, data[o]));
            settag(o << 1 | 1, make_pair(1, data[o]));
            fixed[o] = 0;
        }
        if (tag[o]) {
            settag(o << 1, make_pair(2, tag[o]));
            settag(o << 1 | 1, make_pair(2, tag[o]));
            tag[o] = 0;
        }
    }
};

// C++14需要为static constexpr成员提供定义
constexpr bool segtree::zkw;
constexpr ll segtree::identity;

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

*/
struct XYV{
    ll x,y,v;
    XYV(ll x,ll y,ll v) {this->x=x,this->y=y,this->v=v;}
};
inline void __(){
    Cin(N,K);
    // FOR(i,0,N+5){
    //     FOR(j,0,N+5)
    //         D[i][j]=0;
    // }
    // vtll xyv;
    vector<vector<XYV>> xyv(N+5);
    vtll xxx;
    ll tot=1,xtot=0;
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xxx.EB(x,y,v);
    }
    sort(all(xxx));
    for(auto&[x,y,v]:xxx){
        if(xyv[tot].empty() || xtot==x){
            xyv[tot].EB(x,y,v);
        }else{
            xyv[++tot].EB(x,y,v);
            xtot=x;
        }
    }
    ll ans=0;
    segtree tr(N);

    map<ll,ll> mp;
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        mp[xlen]=max(mp[xlen],ylen);
    }
    for(auto&[xlen,ylen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.update(max(0ll,y-ylen),y,(pll){2,-v});
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }

    for(auto&[ylen,xlen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.update(0,N,(pll){1,0});
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.update(max(0ll,y-ylen),y,(pll){2,-v});
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.update(max(0ll,y-ylen),y,(pll){2,v});
            }
            ans=max(ans,tr.ask(0, N));
        }
    }
    write(ans);
    putchar('\n');
}
/*
WA
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=5684
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=8240
WA 
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=10273
可能是需要去变换这个边长
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=11241
TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=11820
1
4 9
1 2 10
2 1 10
2 3 10
3 2 10

1
3 6
1 1 5
2 1 5
3 1 5

ans:15
*/

自己写的线段树rmq，会比之前的快一点。

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

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <numeric>
#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;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

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)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 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 __();
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;


// 参考zkw的PPT 以及 https://www.luogu.com.cn/record/207546670
// 参考题解 https://www.luogu.com.cn/article/w3gfeebh
// AC https://www.luogu.com.cn/record/232784803 RMQ 
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430 矩形框选卡常
constexpr ll preset=-INF;
struct SEG{
    static ll op(const ll &a,const ll &b){
        return max(a,b);
    }
    int n,sz=1,dep;
    vector<ll> tr;vector<ll> tag;vector<bool> fixed;
    SEG(int n){     // 传入的时候可以传大一点
        this->n=n+2;
        dep=__lg(this->n)+1;
        sz=1<<dep;
        tr.resize((sz<<1)+5,preset);
        tag.resize((sz<<1)+5,0);
        fixed.resize((sz<<1)+5,false);
    }
    void pushup(int o){tr[o]=op(tr[o<<1],tr[o<<1|1]);}
    void settag(int o,ll x){
        tr[o]+=x;
        if(!fixed[o]) tag[o]+=x;
    }
    void settag2(int o,ll x){   // 覆盖
        tr[o]=x;
        tag[o]=0;
        fixed[o]=true;
    }
    void pushdown(int o){ 
        int l=o<<1,r=l|1;   // 左儿子，右儿子
        if(fixed[o]){
            settag2(l, tr[o]);
            settag2(r, tr[o]);
            fixed[o]=false;
        }
        if(tag[o]){
            settag(l, tag[o]);
            settag(r, tag[o]);
            tag[o]=0;
        }
    }
    void push(int l,int r){
        //        在j层，l，r变为了同一点
        int i=dep,j=__lg(l^r);
        while (i<j) {   // 就是为了避免一下重复下推
            pushdown(l>>i--);
        }
        while(i){
            pushdown(l>>i),pushdown(r>>i--);
        }
    }
    void assign(int i,ll x){   
        tr[i+sz]=x;
    }
    void build(){
        for(int o=sz-1;o>=1;--o){
            pushup(o);
        }
    }
    ll query(int l,int r){
        ll res=preset;
        // 变为开区间，并加上sz
        l=l-1+sz,r=r+1+sz;
        push(l,r);
        for(;l^r^1;l>>=1,r>>=1){
            // l^r^1 表示 只要 l 与 r 还不是同一个父亲的两兄弟，就继续上跳。
            if(~l&1){   
                // l是偶数，说明l是父节点的左儿子，开区间，将其右儿子加入答案
                res=op(res,tr[l^1]);
            }
            if(r&1){
                res=op(tr[r^1],res);
            }
        }
        return res;
    }
    void add(int l,int r,ll x){
        int w=1;
        l=l-1+sz,r=r+1+sz;
        push(l, r);
        for(;l^r^1;pushup(l>>=1),pushup(r>>=1),w<<=1){
            if(~l&1){
                settag(l^1, x);
            }
            if(r&1){
                settag(r^1, x);
            }
        }
        for (l >>= 1; l; l >>= 1) pushup(l);
    }
    void modify(int l,int r,ll x){
        int w=1;
        l=l-1+sz,r=r+1+sz;
        push(l, r);
        for(;l^r^1;pushup(l>>=1),pushup(r>>=1),w<<=1){
            if(~l&1){
                settag2(l^1, x);
            }
            if(r&1){
                settag2(r^1, x);
            }
        }
        for (l >>= 1; l; l >>= 1) pushup(l);
    }
};

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

*/
struct XYV{
    ll x,y,v;
    XYV(ll x,ll y,ll v) {this->x=x,this->y=y,this->v=v;}
};
inline void __(){
    Cin(N,K);
    // FOR(i,0,N+5){
    //     FOR(j,0,N+5)
    //         D[i][j]=0;
    // }
    // vtll xyv;
    vector<vector<XYV>> xyv(N+5);
    vtll xxx;
    ll tot=1,xtot=0;
    FOR(i,0,N-1){
        ll x,y,v;
        Cin(x,y,v);
        xxx.EB(x,y,v);
    }
    sort(all(xxx));
    for(auto&[x,y,v]:xxx){
        if(xyv[tot].empty() || xtot==x){
            xyv[tot].EB(x,y,v);
        }else{
            xyv[++tot].EB(x,y,v);
            xtot=x;
        }
    }
    ll ans=0;
    SEG tr(N);

    map<ll,ll> mp;
    FOR(i,1,sqrtl(K)){
        ll xlen=i,ylen=K/i;
        mp[xlen]=max(mp[xlen],ylen);
    }
    for(auto&[xlen,ylen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.modify(1,N,0);
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.add(max(0ll,y-ylen)+1,y,-v);
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.add(max(0ll,y-ylen)+1,y,v);
            }
            ans=max(ans,tr.tr[1]);
        }
    }

    for(auto&[ylen,xlen]:mp){
        // if (xlen < 1 || ylen < 1) continue;
        tr.modify(1,N,0);
        ll st=1;
        FOR(i,1,tot){
            ll ix=xyv[i][0].x;
            ll stx=xyv[st][0].x;
            while(ix-stx+1>xlen){
                for(auto&[x,y,v]:xyv[st]){
                    // tr.add(y-ylen+1, y, -v);
                    tr.add(max(0ll,y-ylen)+1,y,-v);
                }
                ++st;
                stx=xyv[st][0].x;
            }
            for(auto&[x,y,v]:xyv[i]){
                tr.add(max(0ll,y-ylen)+1,y,v);
            }
            ans=max(ans,tr.tr[1]);
        }
    }

    write(ans);
    putchar('\n');
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430
1
4 9
1 2 10
2 1 10
2 3 10
3 2 10

1
3 6
1 1 5
2 1 5
3 1 5

ans:15
*/