传送门

一般扫描线

今天才发现我这种写法，需要把差分负值作为第二排序依据，因为差分结束的地方可能和另外一个差分开始的地方重合， 如果不清除以前的影响会造成答案变大

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e5 + 233;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
struct Node{
    int l, r, dat, mk;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define dat(x) t[x].dat
    #define mk(x) t[x].mk
}t[maxn * 4];
void build(int p, int l, int r)
{
    l(p) = l; r(p) = r;
    if(l == r)
    {
        dat(p) = 0; mk(p) = 0;
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    dat(p) = 0; mk(p) = 0; 
}
void spr(int p)
{
    if(mk(p))
    {
        dat(ls(p)) += mk(p);
        dat(rs(p)) += mk(p);
        mk(ls(p)) += mk(p);
        mk(rs(p)) += mk(p);
        mk(p) = 0;
    }
}
void update(int p, int l, int r, int v)
{
    if(l <= l(p) && r >= r(p))
    {
        dat(p) += v;
        mk(p) += v;
        return ;
    }
    spr(p);
    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid) update(ls(p), l, r, v);
    if(r > mid) update(rs(p), l, r, v);
    dat(p) = max(dat(ls(p)), dat(rs(p)));
}
int ask(int p, int l, int r)
{
    if(l <= l(p) && r >= r(p)) return dat(p);
    spr(p);
    int mid = (l(p) + r(p)) >> 1;
    int res = 0;
    if(l <= mid) res = max(res, ask(ls(p), l, r));
    if(r > mid) res = max(res, ask(rs(p), l, r));
    return res;
}
//--------------------↓-----------这个要放在前面
vector<pair<int, pair<int,pii> > > org;
int main()
{
    int n, r;
    cin >> n >> r;
    for(int i = 1; i <= n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        y++;
        org.push_back({x,{z, {y, y + r - 1}}});
        org.push_back({x + r,{-z, {y, y + r - 1}}});
    }
    sort(org.begin(), org.end());
    int ans = 0;
    build(1,1,10001);
    for(int i = 0; i < org.size(); i++)
    {
        pii now = org[i].second.second;
        int ty = org[i].second.first;
        update(1, now.first, now.second, ty);
        ans = max(ans, ask(1, 1, 10001));
    }
    cout<<ans;
}