当前位置：首页 > news >正文

小奇的糖果(candy)

news 来源：原创 2024/4/29 14:14:37

【题目背景】
小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。
【问题描述】
有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或
下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的
颜色。
【输入格式】
包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。
接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表
示点数和颜色数。
接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点
的位置,最后一个数 z (1 ≤ z ≤ k) 描述点的颜色。
【输出格式】
对于每组数据在一行内输出一个非负整数 ans,表示答案。
【样例输入】
1
10 3
1 2 3
2 1 1
2 4 2
3 5 3
4 4 2
5 1 2
6 3 1
6 7 1
7 2 3
9 4 2
【样例输出】
5
【数据范围】
对于 30% 的数据,N ≤ 100;
对于 60% 的数据,N ≤ 5000;
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<queue>
  8 #include<vector>
  9 #include<set>
 10 using namespace std;
 11 typedef long long LL;
 12 const int maxn=100010;
 13 int T,ANS,N,K;
 14 int last[maxn],l[maxn],r[maxn];
 15 int disc[maxn],x[maxn],b[maxn];
 16 struct Candy{
 17     int x,y,k;
 18     int id;
 19 }a[maxn];
 20 inline int cmpbyy(const Candy & w,const Candy & e){//´ÓÏÂµ½ÉÏ ´Ó×óµ½ÓÒ 
 21     return w.y<e.y||(w.y==e.y&&w.x<e.x);
 22 }
 23 inline int cmpbyx(const Candy & w,const Candy & e){//´Ó×óµ½ÓÒ ´ÓÏÂµ½ÉÏ 
 24     return w.x<e.x||(w.x==e.x&&w.y>e.y);
 25 }
 26 struct Tree{
 27     int l,r,sum;
 28 }tr[maxn*8];
 29 inline void Build(int rt,int l,int r){
 30     tr[rt].l=l; tr[rt].r=r;
 31     if(l==r){
 32         tr[rt].sum=b[l];
 33         return ;
 34     }
 35     int mid=(l+r)>>1;
 36     Build(rt<<1,l,mid); Build(rt<<1|1,mid+1,r);
 37     tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
 38 }
 39 inline void change(int rt,int pos,int delta){
 40     if(tr[rt].l==tr[rt].r){
 41         tr[rt].sum+=delta;
 42         return ;
 43     }
 44     int mid=(tr[rt].l+tr[rt].r)>>1;
 45     if(pos<=mid) change(rt<<1,pos,delta);
 46     else change(rt<<1|1,pos,delta);
 47     tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
 48 }
 49 inline int query(int rt,int l,int r){
 50     if(l<=tr[rt].l&&tr[rt].r<=r){
 51         return tr[rt].sum;
 52     }
 53     int mid=(tr[rt].l+tr[rt].r)>>1;
 54     int ans=0;
 55     if(l<=mid) ans+=query(rt<<1,l,r);
 56     if(mid+1<=r) ans+=query(rt<<1|1,l,r);
 57     return ans;
 58 }
 59 inline void update(int l,int r){
 60     if(l>r) return ;
 61     ANS=max(ANS,query(1,l,r));
 62 }
 63 inline void work(){
 64     x[0]=0; x[N+1]=N+1;
 65     memset(last,0,sizeof(last)); memset(b,0,sizeof(b));
 66     for(int i=1;i<=800000;i++) tr[i].l=tr[i].r=tr[i].sum=0;
 67     
 68     sort(a+1,a+N+1,cmpbyx);
 69     for(int i=1;i<=N;i++) b[x[i]]++;
 70     Build(1,1,N+1);
 71     for(int i=1;i<=N;i++){
 72         int tmp=a[i].id,L=last[a[i].k];
 73         l[tmp]=L; r[tmp]=N+1;
 74         if(L) r[L]=tmp;
 75         update(x[L]+1,x[tmp]-1);
 76         last[a[i].k]=tmp;
 77     }
 78     for(int i=1;i<=K;i++){
 79         update(x[last[i]]+1,N+1);
 80     }
 81     sort(a+1,a+N+1,cmpbyy);
 82     for(int i=1,j=1;i<=N;i++){
 83         int tmp=a[i].id;
 84         while(j<=N&&a[j].y==a[i].y){
 85             change(1,a[j].x,-1);
 86             j++;
 87         }
 88         l[r[tmp]]=l[tmp]; r[l[tmp]]=r[tmp];
 89         update(x[l[tmp]]+1,x[r[tmp]]-1);
 90     }
 91 }
 92 int main(){
 93 //    freopen("candy.in","r",stdin);
 94 //    freopen("candy.out","w",stdout);
 95     scanf("%d",&T);
 96     while(T--){
 97         ANS=0;
 98         scanf("%d%d",&N,&K);
 99         for(int i=1;i<=N;i++){
100             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].k);
101             a[i].id=i;
102         }
103         for(int i=1;i<=N;i++){
104             disc[i]=a[i].x;
105         }
106         sort(disc+1,disc+N+1);
107         int *end=unique(disc+1,disc+N+1);
108         for(int i=1;i<=N;i++){
109             a[i].x=lower_bound(disc+1,end,a[i].x)-disc;
110             x[i]=a[i].x;
111         }
112         work();
113         for(int i=1;i<=N;i++) a[i].y*=-1;
114         work();
115         printf("%d\n",ANS);
116     }
117     return 0; 
118 }