BZOJ

分析

只考虑选的点都在线段下方的情况,在线段上方的情况可以通过将纵坐标取反一样的做。

首先考虑线段的纵坐标无限大的情况,显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序,维护一下上一个某种颜色的点,再用树状数组维护区间内点的个数即可。

现在把线段向下移动,假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$,此时线段左右边界会卡在上一个和 $u$ 颜色相同的点和下一个和 $u$ 颜色相同的点之间。我们用双端链表维护左右颜色相同的点,每次将纵坐标比线段当前纵坐标大的点删掉,然后把 $u$ 从双端链表里删掉即可。

具体实现起来有一些细节。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define clear(x,y) memset(x,y,sizeof(x))
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,k;

int x[N],S[N];
struct point { int x,y,c,id; } p[N];
inline bool cmpx(point a,point b) { return a.x<b.x; }
inline bool cmpy(point a,point b) { return a.y>b.y; }

int c[N];
inline void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }
inline int sum(int x,int y) { return sum(y)-sum(x-1); }

int L[N],R[N],lst[N];

inline int solve() { int ans=0;
    x[0]=0,x[n+1]=n+1; clear(lst,0);
    sort(p+1,p+n+1,cmpx);
    for (re int i=1;i<=n;++i) add(p[i].x,1);
    for (re int i=1;i<=n;++i) {
        int now=p[i].id,pre=lst[p[i].c];
        lst[p[i].c]=now; R[pre]=now,L[now]=pre;
        ans=max(ans,sum(x[pre]+1,x[now]-1));
    }
    for (re int i=1;i<=k;++i) {
        R[lst[i]]=n+1;
        ans=max(ans,sum(x[lst[i]]+1,n));
    }
    sort(p+1,p+n+1,cmpy);
    for (re int i=1,j=1;i<=n;++i) {
        while (j<=n&&p[j].y==p[i].y) add(p[j].x,-1),++j;
        int now=p[i].id;
        R[L[now]]=R[now],L[R[now]]=L[now];
        ans=max(ans,sum(x[L[now]]+1,x[R[now]]-1));
    }
    return ans;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),k=read();
        for (re int i=1;i<=n;++i)
            p[i]=(point){read(),read(),read(),i};
        for (re int i=1;i<=n;++i) S[i]=p[i].x;
        sort(S+1,S+n+1); int tp=unique(S+1,S+n+1)-S-1;
        for (re int i=1;i<=n;++i) x[i]=p[i].x=lower_bound(S+1,S+tp+1,p[i].x)-S;
        int ans=solve();
        for (re int i=1;i<=n;++i) p[i].y=-p[i].y;
        printf("%d\n",max(ans,solve()));
    }
    return 0;
}
最后修改:2019 年 10 月 17 日 10 : 35 AM