考虑将某线段下方的点取走：

将所有点从低到高排序

每扫描到一条水平线，对于上面每个点，找到它下面同色的前驱后继，统计中间点的个数

然后再把线上所有点插入数据结构中

最后再统计相邻的同色的点之间的点个数

用动态开点的权值线段树+树状数组维护，时间复杂度$O(n\log n)$。

考虑将某线段上方的点取走：

把扫描线的顺序反过来即可

注意特判出现颜色数没达到k的情况。

 

#include
     
      #include
      
       using namespace std;const int N=100010,M=1800000;int C,n,k,i,j,ans,bit[N],b[N],vis[N];struct P{int x,y,c;}a[N];inline bool cmpc(P a,P b){return a.c==b.c?a.x
       
        
         >1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}inline void add(int x){for(;x<=n;x+=x&-x)bit[x]++;}inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int T[N],vl[M],vr[M],l[M],r[M],tot,pre,nxt;void ins(int&x,int a,int b,int c){  if(!x)x=++tot;  if(a==b){vl[x]=vr[x]=a;return;}  int mid=(a+b)>>1;  if(c<=mid)ins(l[x],a,mid,c);else ins(r[x],mid+1,b,c);  vl[x]=vl[l[x]]?vl[l[x]]:vl[r[x]];  vr[x]=vr[r[x]]?vr[r[x]]:vr[l[x]];}void getl(int x,int a,int b,int c){  if(!x||nxt)return;  if(c<=a){nxt=vl[x];return;}  int mid=(a+b)>>1;  if(c<=mid)getl(l[x],a,mid,c);  getl(r[x],mid+1,b,c);}void getr(int x,int a,int b,int d){  if(!x||pre)return;  if(b<=d){pre=vr[x];return;}  int mid=(a+b)>>1;  if(d>mid)getr(r[x],mid+1,b,d);  getr(l[x],a,mid,d);}int main(){  for(read(C);C--;printf("%d\n",ans)){    read(n),read(k);    for(i=1;i<=k;i++)vis[i]=0;    for(ans=0,i=1;i<=n;i++)read(a[i].x),read(a[i].y),read(a[i].c),b[i]=a[i].x,vis[a[i].c]=1;    for(sort(b+1,b+n+1),sort(a+1,a+n+1,cmpy),i=1;i<=n;i++)a[i].x=lower(a[i].x);    for(i=1;i<=n;i++)bit[i]=0;    for(i=1;i<=k;i++)if(!vis[i]){ans=n;break;}    if(ans)continue;    for(i=1;i<=tot;i++)vl[i]=vr[i]=l[i]=r[i]=0;tot=0;    for(i=1;i<=k;i++)T[i]=0,ins(T[i],0,n+1,0),ins(T[i],0,n+1,n+1);    for(i=1;i<=n;i=j){      for(j=i;j<=n&&a[j].y==a[i].y;j++){        pre=nxt=0,getl(T[a[j].c],0,n+1,a[j].x),getr(T[a[j].c],0,n+1,a[j].x);        up(ask(nxt-1)-ask(pre));      }      for(j=i;j<=n&&a[j].y==a[i].y;j++)ins(T[a[j].c],0,n+1,a[j].x),add(a[j].x);    }    for(i=1;i<=n;i++)bit[i]=0;    for(i=1;i<=tot;i++)vl[i]=vr[i]=l[i]=r[i]=0;tot=0;    for(i=1;i<=k;i++)T[i]=0,ins(T[i],0,n+1,0),ins(T[i],0,n+1,n+1);    for(i=n;i;i=j){      for(j=i;j&&a[j].y==a[i].y;j--){        pre=nxt=0,getl(T[a[j].c],0,n+1,a[j].x),getr(T[a[j].c],0,n+1,a[j].x);        up(ask(nxt-1)-ask(pre));      }      for(j=i;j&&a[j].y==a[i].y;j--)ins(T[a[j].c],0,n+1,a[j].x),add(a[j].x);    }    for(sort(a+1,a+n+1,cmpc),i=1;i<=n;i++)bit[i]=0;    for(i=1;i<=n;i++)bit[a[i].x]++;    for(i=2;i<=n;i++)bit[i]+=bit[i-1];    for(i=1;i