2025“钉耙编程”中国大学生算法设计暑期联赛（7）——矩形框选 · znzryb
## 思路讲解
我的做法还是我的做法，就是需要用zkw线段树卡一下常
复杂度是$O(\sqrt k \times N \times \log(n))$。
## AC代码
[https://acm.hdu.edu.cn/contest/status?cid=1178&rid=15857](https://acm.hdu.edu.cn/contest/status?cid=1178&rid=15857)
::: 源代码
```cpp
// 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](https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=15813)
::: 源代码
```cpp
// 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](https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19430)
::: 源代码
```cpp
// 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……）