牛客第十场 F.Popping Balloons

第一维直接遍历 第二维用线段树维护每个最左端可以得到的贡献

在线段树上每次删除一个点会影响到 X   X-R   X-2*R  3个值 最多操作1e5次 复杂度 6*n*logn(删了还要加回来

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;

int num[MAXN];

int number[MAXN];

struct Seg_Tre {

        int l, r;

        int w;

} tree[MAXN << ];

inline void push_up(int x) {

        tree[x].w = max(tree[x << ].w, tree[(x << ) | ].w);

}

inline void build(int x, int ll, int rr) {

        tree[x].l = ll, tree[x].r = rr;

        if (tree[x].l == tree[x].r) {

                tree[x].w = number[ll];

                return;

        }

        int m = (ll + rr) >> ;

        build(x << , ll, m);

        build((x <<  | ), m + , rr);

        push_up(x);

}

inline void change_point(int x, int aim, int add) {

        if (tree[x].l == tree[x].r) {

                tree[x].w += add;

                return;

        }

        int m = (tree[x].l + tree[x].r) >> ;

        if (aim <= m) {

                change_point(x << , aim, add);

        } else {

                change_point((x << ) | , aim, add);

        }

        push_up(x);

}

inline int ask_interval(int x, int ll, int rr) {

        if (tree[x].l > rr || tree[x].r < ll)

                return -;

        if (tree[x].l >= ll && tree[x].r <= rr) {

                return tree[x].w;

        }

        int now = ;

        int m = (tree[x].l + tree[x].r) >> ;

        if (ll <= m) {

                now = max(now, ask_interval(x << , ll, m));

        }

        if (rr > m) {

                now = max(now, ask_interval((x << ) | , m + , rr));

        }

        return now;

}

vector<int> G[MAXN];

int main() {

        int n, r;

        int x, y;

        scanf("%d %d", &n, &r);

        for (int i = ; i <= n; i++) {

                scanf("%d %d", &x, &y);

                G[x].push_back(y);

                num[y]++;

        }

        for (int i = ; i <= ; i++) {

                for (int j = ; j <= ; j++) {

                        if (i + j * r <= ) {

                                number[i] += num[i + j * r];

                        }

                }

        }

        build(, , );

        int ansnow = ;

        for (int i = ; i <= ; i++) {

                int now = ;

                for (int j = ; j <= ; j++) {

                        int u = i + j * r;

                        if (u > )

                                break;

                        for (int v : G[u]) {

                                now++;

                                for (int k = ; k <= ; k++)

                                        if (v - k * r >= )

                                                change_point(, v - k * r, -);

                        }

                }

                ansnow = max(ansnow, now + ask_interval(,,));

                for (int j = ; j <= ; j++) {

                        int u = i + j * r;

                        if (u > )

                                break;

                        for (int v : G[u]) {

                                now++;

                                for (int k = ; k <= ; k++)

                                        if (v - k * r >= )

                                                change_point(, v - k * r, );

                        }

                }

        }

        printf("%d\n", ansnow);

        return ;

}