题目概述

有 $n$ 个有颜色的点，颜色有 $K$ 种，现在选一条线段并获取上面或下面的所有点，规定获得的点不能包含所有颜色，问你能获得多少点。

解题报告

我怎么套路题都不会做啊……首先有显然的贪心，就是选 $K-1$ 个颜色，那么我们先枚举不选的颜色是什么。

然后坐标系中就多了一堆限制点，我们肯定是贴着限制点选，所以从下往上或者从下往上搞搞就行了。

我是这么做的：

从下往上做，每次加入一个点之后就说明坐标系被分成了两半，用set维护一下这些分隔线就行了。

示例程序

我又被BZOJ卡常了……反正BZOJ3658过了……我不管了……

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=1e7;

int te,n,K,c[maxn+5],ro[maxn+5];LL x[maxn+5],y[maxn+5];
int len,sum[maxt+5],ls[maxt+5],rs[maxt+5],X,Y,ans;
vector<int> P[maxn+5];vector< pair<int,int> > p[maxn+5];
set<int> pos;set<int>::iterator it;

inline void Make(LL *a){
    static LL tem[maxn+5];for (int i=1;i<=n;i++) tem[i]=a[i];
    sort(tem+1,tem+1+n);tem[0]=unique(tem+1,tem+1+n)-tem-1;
    for (int i=1;i<=n;i++)
        for (int L=1,R=tem[0],mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
            if (a[i]==tem[mid]) {a[i]=mid;break;} else a[i]<tem[mid]?R=mid-1:L=mid+1;
}
#define newnode(s,l,r) (sum[len]=(s),ls[len]=(l),rs[len]=(r),len++)
int Build(int L,int R){
    int now=newnode(0,0,0);if (L==R) return now;int mid=L+(R-L>>1);
    ls[now]=Build(L,mid);rs[now]=Build(mid+1,R);return now;
}
int Insert(int p,int pos,int l=1,int r=X){
    int now=newnode(sum[p]+1,ls[p],rs[p]);if (l==r) return now;int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);return now;
}
int Ask(int p,int L,int R,int l=1,int r=X){
    if (R<l||r<L) return 0;if (L<=l&&r<=R) return sum[p];int mid=l+(r-l>>1);
    return Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r);
}
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b) {return a.sc<b.sc;}
inline int Count(){
    for (int i=1;i<=Y;i++) P[i].clear();for (int i=1;i<=n;i++) P[y[i]].push_back(x[i]);
    int ans=0;len=0;ro[0]=Build(1,X);
    for (int i=1;i<=Y;i++)
        for (int j=(ro[i]=ro[i-1],0);j<P[i].size();j++)
            ro[i]=Insert(ro[i],P[i][j]);
    for (int i=1;i<=K;i++) p[i].clear();
    for (int i=1;i<=n;i++) p[c[i]].push_back(mp(x[i],y[i]));
    for (int i=1;i<=K;i++){
        if (!p[i].size()) return n;sort(p[i].begin(),p[i].end(),cmp);
        pos.clear();pos.insert(0);pos.insert(X+1);
        for (int j=0;j<p[i].size();j++){
            if (pos.count(p[i][j].fr)) continue;int L,R;
            it=pos.lower_bound(p[i][j].fr);it--;L=*it;
            it=pos.upper_bound(p[i][j].fr);R=*it;
            ans=max(ans,Ask(ro[p[i][j].sc-1],L+1,R-1));pos.insert(p[i][j].fr);
        }
        for (int lst=(it=pos.begin(),*(it++));it!=pos.end();lst=*(it++))
            ans=max(ans,Ask(ro[Y],lst+1,(*it)-1));
    }
    return ans;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%lld%lld%d",&x[i],&y[i],&c[i]);
        Make(x);Make(y);X=0,Y=0;for (int i=1;i<=n;i++) X=max(X,(int)x[i]),Y=max(Y,(int)y[i]);
        ans=max(ans,Count());if (ans==n) {printf("%d\n",ans);goto END;}
        for (int i=1;i<=n;i++) y[i]=Y-y[i]+1;
        ans=max(ans,Count());printf("%d\n",ans);END:ans=0;
    }
    return 0;
}