哪里有错,佬们
查看原帖
哪里有错,佬们
948817
nanfeng_楼主2023/4/20 18:39
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<ctime>
using namespace std;
//================================================
typedef long long ll;
int t;
const int N = 1e5 + 10;
int v[N];
struct node
{
    ll l, r;
    ll mx;
}sgt[N << 3];
struct Line
{
    ll x;
    ll y1, y2;
    ll val;
    bool operator < (const Line& ob)const
    {
        return this->x < ob.x;
    }
}line[N << 2];
void Init()
{
     memset(sgt,0,sizeof sgt);
     memset(v,0,sizeof v);
}
ll ls(ll k)
{
    return k << 1;
}
ll rs(ll k)
{
    return k << 1 | 1;
}
void build(ll l, ll r, ll k = 1)
{
    sgt[k].l = v[l], sgt[k].r = v[r];
    sgt[k].mx = 0;
    if (r - l <= 1)return;
    ll mid = l + r >> 1;
    build(l, mid, ls(k));
    build(mid, r, rs(k));
}
void pushup(ll k)
{
    sgt[k].mx = max(sgt[ls(k)].mx, sgt[rs(k)].mx);
}
void modify(ll l, ll r, ll z, ll k = 1)
{
    if (l <= sgt[k].l && sgt[k].r <= r)
    {
        sgt[k].mx += z;//区间就是权值
        return;
    }
    if (l < sgt[ls(k)].r)
        modify(l, r, z, ls(k));
    if (r > sgt[rs(k)].l)
        modify(l, r, z, rs(k));
    pushup(k);
}
signed main(signed arg, const char* args[])
{
    clock_t st = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //============================================
    scanf("%d", &t);
    while (t--)
    {
        Init();
        ll n, w, h;
        scanf("%lld%lld%lld", &n, &w, &h);
        for (int i = 1; i <= n; i++)
        {
            ll x, y, l;
            scanf("%lld%lld%lld", &x, &y, &l);
            v[i] = y, v[i + n] = y + h - 1;
            line[i] = { x,y,y + h - 1,l };
            line[i + n] = { x + w - 1,y,y + h - 1,-l };
        }
        sort(v + 1, v + 1 + (n << 1));
        sort(line + 1, line + 1 + (n << 1));
        build(1, n << 1);
        ll ans = 0;
        for (int i = 1; i <= (n << 1); i++)
        {
            ans = max(ans, sgt[1].mx);
            modify(line[i].y1, line[i].y2, line[i].val);
        }
        printf("%lld\n", ans);
    }
    //============================================
end:
    cerr << "Time Used:" << clock() - st << "ms" << endl;
    return 0;
}

2023/4/20 18:39
加载中...