2019牛客多校（第十场）FPopping Balloons —— 线段树+枚举

https://ac.nowcoder.com/acm/contest/890/F

题意：二维平面中有n个气球，你可以横着社三法子弹，竖着射三发子弹，且横着子弹的关系是y,y+r,y+2*r,竖着是x,x+r,x+2*r。问你怎么射才能射爆最多的气球。

分析：（代码注释）

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define lson root<<1,l,midd

#define rson root<<1|1,midd+1,r

const int M=3e5+;

int n,m;

vector<int>mp[M];

int tree[M<<];

void up(int root){

    tree[root]=max(tree[root<<],tree[root<<|]);

}

void update(int pos,int val,int root,int l,int r){

    if(l==r){

        tree[root]+=val;

        return ;

    }

    int midd=(l+r)>>;

    if(pos<=midd)

        update(pos,val,lson);

    else

        update(pos,val,rson);

    up(root);

}

void change(int pos,int val){

    update(pos,val,,,1e5+);

    if(pos-m>=)

        update(pos-m,val,,,1e5+);

    if(pos-*m>=)

        update(pos-*m,val,,,1e5+);

}

int main(){

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

    int ans=;

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

        int x,y;

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

        x++,y++;

        mp[x].pb(y);

        change(y,);

    }

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

        ///三行贡献

        int hang=mp[i].size()+mp[i+m].size()+mp[i+*m].size();

        ///求去掉三行后的三列最大贡献

        for(int j=;j<mp[i].size();j++){

            change(mp[i][j],-);

        }

        for(int j=;j<mp[i+m].size();j++){

            change(mp[i+m][j],-);

        }

        for(int j=;j<mp[i+*m].size();j++){

            change(mp[i+*m][j],-);

        }

        ans=max(ans,hang+tree[]);

        ///加回来为了下一次计算做准备

        for(int j=;j<mp[i].size();j++){

            change(mp[i][j],);

        }

        for(int j=;j<mp[i+m].size();j++){

            change(mp[i+m][j],);

        }

        for(int j=;j<mp[i+*m].size();j++){

            change(mp[i+*m][j],);

        }

    }

    printf("%d",ans);

    return ;

}