小奇的糖果(candy)-白红宇

小奇的糖果(candy)

阅读量：6426 次

发布时间：2019-06-23

本文共 3256 字，大约阅读时间需要 10 分钟。

【题目背景】

小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。

【问题描述】

有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或

下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的

颜色。

【输入格式】

包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。

接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表

示点数和颜色数。

接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点

的位置,最后一个数 z (1 ≤ z ≤ k) 描述点的颜色。

【输出格式】

对于每组数据在一行内输出一个非负整数 ans,表示答案。

【样例输入】

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

【样例输出】

【数据范围】

对于 30% 的数据,N ≤ 100;

对于 60% 的数据,N ≤ 5000;

对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               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); 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 }