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

思路讲解

我的做法还是我的做法，就是需要用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
*/

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