牛客網Popping Balloons【線分樹】

标题:座標軸にn個の点(n<=1 e 5)を与え、点の横長座標は[0,1 e 5]で、3行を選択することができ、各行間隔はdで、3列の同じ間隔dを選択し、点は1回しか選択できず、最大何点を選択できるかを聞く.d<=1e5
考え方:num[j]+num[j+d]+num[j+2 d]の値を1本のセグメントツリーを作成し、選択したポイントを削除し、セグメントツリーで最大値を検索すればいいと考えています.ポイントを削除するときは、自分のx,x-d,x-2 dの位置にのみ影響します.クエリーを削除した後、追加し直します.

#include 
using namespace std;
typedef long long ll;
#define ls rt << 1
#define rs rt << 1|1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1|1
const int N = 100005;
const int maxn = 2e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
vector v[maxn];
int num[maxn]; // 
ll tree[maxn << 2];
int n, d;
 
void push_up(int rt)
{
    tree[rt] = max(tree[ls], tree[rs]);
}
void build(int l, int r, int rt)
{
    if(l == r)
    {
        for(int i = 0; i < 3; ++i)
            if(l + i * d <= N)
                tree[rt] += num[l + i * d];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int pos, int val, int l, int r, int rt)
{
    if(l < 0 || r > N || pos < 0 || pos > N)
        return;
    if(l == r)
    {
        tree[rt] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update(pos, val, lson);
    else
        update(pos, val, rson);
    push_up(rt);
}
ll query(int ql, int qr, int l, int r, int rt)
{
    if(ql <= l && r <= qr)
        return tree[rt];
    int mid = (l + r) >> 1;
    ll ret = -inf;
    if(ql <= mid)
        ret = max(ret, query(ql, qr, lson));
    if(qr > mid)
        ret = max(ret, query(ql, qr, rson));
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &d);
    for(int i = 1; i <= n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v[y].push_back(x);
        num[x]++;
    }
    build(0, N, 1);
    ll ans = 1;
    for(int i = 0; i <= N; ++i) // 
    {
        ll tmp = 0;
        for(int j = 0; j < 3; ++j)
        {
            if((ll)(i + j * d) <= N)
            {
                tmp += v[i + j * d].size();
                for(auto x : v[i + j * d])
                {
                    update(x, -1, 0, N, 1);
                    update(x - d, -1, 0, N, 1);
                    update(x - 2 * d, -1, 0, N, 1);
                }
            }
        }
        tmp += query(0, N, 0, N, 1);
        ans = max(ans, tmp);
        for(int j = 0; j < 3; ++j)
        {
            if((ll)(i + j * d) <= N)
            {
                for(auto x : v[i + j * d])
                {
                    update(x, 1, 0, N, 1);
                    update(x - d, 1, 0, N, 1);
                    update(x - 2 * d, 1, 0, N, 1);
                }
            }
        }
    }
    printf("%lld
", ans);
    return 0;
}