题意

给你一个 的矩形范围，你可以用一个宽度最多为 ，高度为 的十字架覆盖矩形范围之内的点，求最多可以覆盖多少个点？（不同点的坐标可能重合，十字架中心点可以随意移动）

方法一（暴力求解）

枚举矩形范围内的所有点，作为十字架的中心点，然后依照题意统计当前点作为十字架的中心点后能够覆盖多少个点，最后答案取最大值即可。

class Solution {
public:
    int cnt[200005];
    int g[200005][200005];
    int BoomKill(int n, int m, vector<Point>& Player) {
        for(int i=0;i<Player.size();i++){
            cnt[Player[i].x]++;//统计每一列（此处的列按照数学坐标系的来）玩家个数
            g[Player[i].x][Player[i].y]++;
        }
        int ans=0;
        for(int x=1;x<=n;x++){
            for(int y=1;y<=n;y++){
                int res=0;
                for(int k=max(1,x-m+1);k<=min(n,x+m-1);k++){
                    res+=g[k][y];
                }
                res+=cnt[x];
                res-=g[x][y];//十字架中心点的玩家数量加了两次，所以要减掉一次
                ans=max(ans,res);
            }
        }
        return ans;
    }
};

时间复杂度： ,枚举中心点坐标是 的，暴力计算炸掉多少是 的，故总的时间复杂度为
空间复杂度： ，保存矩形范围需要一个 的二维数组

方法二（正解）

前置知识：线段树，二分查找，排序

（注意，以下"行"和"列"是数学坐标系下的，而不是二维数组中的）
既然可以炸掉一整列，我们暂不考虑这个条件，首先考虑行范围的限制。那么能炸的范围就是一个宽度最多为 ，高度为 的框，如下图所示。

其中中间的那条红线表示当前十字架的中心线，左右两条红线为能够覆盖的宽度范围（宽度最多为 ）。
考虑已知当前这个框，怎么求解答案？
当前已经固定了横坐标（十字架中心线的横坐标），记为 ，考虑枚举中心线上的 个点，分别求出以这 个点向左右扩展能够炸掉的玩家数量，求出最大值即可，最大值记为 。
记 表示横坐标为 的这一列玩家总数量。
那么当前中心线下的答案为 ，最终答案取所有中心线答案最大值即可。
其中 可以预先统计出来，求解 可以利用线段树求解，显然这里是单点修改，区间求最大值
那么我们考虑如何求解（十字架中心点的玩家数量）
方法一：对玩家以 作为第一关键字， 作为第二关键字排序，在给定 范围内对 做二分查找即可。
方法二：开 个动态开点线段树，在线段树内做"单点查询"。
这边我们采用方法一。
具体的：
1.首先将玩家以 为第一关键字， 为第二关键字排序。
2.
（1）主循环枚举方框中心线横坐标，求出方框左边界 和右边界 ，将横坐标小于等于 的玩家"加入"（线段树单点修改）。
（2）计算当前中心线对答案的贡献，取max。
（3）计算下一次循环的 ，把横坐标小于 的玩家全部"踢出"（线段树单点修改）。
3.输出答案

bool cmp(const Point& x,const Point& y){
    if(x.x==y.x)return x.y<y.y;//如果x相同时，按照y从小到大排序
    return x.x<y.x;//按照x从小到大排序
}
class Solution {
public:
    struct segtree{
        int mxval[200005<<2][2];
        //mxval[x][0] 表示线段树节点x所管辖区间的最大值
        //mxval[x][1] 表示线段树节点x所管辖区间的最大值所对应的下标
        inline int lson(int x){
            return x<<1;
        }
        inline int rson(int x){
            return x<<1|1;
        }
        inline void pushup(int x){
            if(mxval[lson(x)][0]>mxval[rson(x)][0]){
                mxval[x][0]=mxval[lson(x)][0];
                mxval[x][1]=mxval[lson(x)][1];
            }else{
                mxval[x][0]=mxval[rson(x)][0];
                mxval[x][1]=mxval[rson(x)][1];
            }
        }
        void add(int x,int l,int r,int p,int v){//单点修改
            if(l==r){
                mxval[x][0]+=v;
                mxval[x][1]=p;
                return;
            }
            int mid=(l+r)>>1;
            if(p<=mid)add(lson(x),l,mid,p,v);
            else add(rson(x),mid+1,r,p,v);
            pushup(x);
        }
    }seg;
    int st[200005],ed[200005],cnt[200005];
    void clear(){
        //多测得清空
        memset(st,0,sizeof st);
        memset(ed,-1,sizeof ed);
        memset(cnt,0,sizeof cnt);
        memset(seg.mxval,0,sizeof seg.mxval);
    }
    inline int find_player_cnt(vector<Point>& p,int x,int y){
        //查询坐标为(x,y)的玩家的数量
        int ansl=0,ansr=-1;
        int l=st[x],r=ed[x];
        while(l<=r){//第一次二分，寻找该坐标最先出现的位置
            int mid=(l+r)>>1;
            if(p[mid].y==y){
                ansl=mid;
                r=mid-1;
            }else if(p[mid].y<y){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        l=st[x],r=ed[x];
        while(l<=r){//第二次二分，寻找该坐标最后出现的位置
            int mid=(l+r)>>1;
            if(p[mid].y==y){
                ansr=mid;
                l=mid+1;
            }else if(p[mid].y<y){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return ansr-ansl+1;
    }
    int BoomKill(int n, int m, vector<Point>& Player) {
        clear();
        sort(Player.begin(),Player.end(),cmp);//先排序
        //st[x]表示横坐标为x的玩家第一次出现的位置
        st[Player[0].x]=0;
        //ed[x]表示横坐标为x的玩家最后一次出现的位置
        ed[Player[0].x]=0;
        cnt[Player[0].x]++;
        for(int i=1;i<Player.size();i++){
            if(Player[i].x!=Player[i-1].x){
                st[Player[i].x]=i;
                ed[Player[i].x]=i;
            }else{
                ed[Player[i].x]=i;
            }
            cnt[Player[i].x]++;
        }
        int ans=0;
        int idx=0;
        for(int cx=1;cx<=n;cx++){
            int lx=max(1,cx-m+1);
            int rx=min(n,cx+m-1);
            while(idx<Player.size()&&Player[idx].x<=rx){
                seg.add(1,1,n,Player[idx].y,1);//加入玩家
                idx++;
            }
            ans=max(ans,cnt[cx]+seg.mxval[1][0]-find_player_cnt(Player,cx,seg.mxval[1][1]));
            if(max(1,cx+1-m+1)!=lx){
                for(int i=st[lx];i<=ed[lx];i++){
                    seg.add(1,1,n,Player[i].y,-1);//踢出玩家
                }
            }
        }
        return ans;
    }
};

时间复杂度： 线段树单点修改，查询还有二分查找都是 的，由于每个玩家只会进出线段树一次，所以复杂度为
空间复杂度： ，线段树开四倍内存是 的，程序中其他数组也是 级别的