[JZOJ5229] 小奇的糖果

Description

有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3。
线段两侧上下的点不算

Solution

比赛的时候一直在想带修主席树的做法，大致思想还是停留在枚举线段的范围

事实上这题有很♂妙♂的做法

枚举哪一种颜色不选，是整一题的关键。

当然，如果颜色不全，就是说有的颜色根本没有，答案就是N

用树状数组维护区间点的个数，用双向链表记录当前点左边或右边第一个跟他同色是那个点

可以将所有点按照纵坐标排序
从上到下，找过的点删掉，计算这个点链表左右中间的区间

如果一个点左或右为空那直接统计0或者N

一开始还要直接统计每种颜色相邻两两点之间的所有点

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int n,m,l[N],r[N],ls[N],z[N],ans,c[N],mx,mp[N];
struct node
{
    int x,y,z,p;
}a[N],b[N];
int bz[N];
int lowbit(int k)
{
    return k&(-k);
}
int get(int k)
{
    int s=0;
    while(k) s+=c[k],k-=lowbit(k);
    return s;
}
void put(int k,int v)
{
    while(k<=n) c[k]+=v,k+=lowbit(k);
}
bool cmp(node x,node y)
{
    return x.x<y.x;
}
bool cmp1(node x,node y)
{
    return (x.y<y.y||(x.y==y.y&&x.x<y.x));
}
bool cmp2(node x,node y)
{
    return (x.y>y.y||(x.y==y.y&&x.x<y.x));
}
void doit(int q)
{
    if(q==0) sort(a+1,a+n+1,cmp1);
    else sort(a+1,a+n+1,cmp2);
    memset(c,0,sizeof(c));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    memset(ls,0,sizeof(ls));
    fo(i,1,n) z[a[i].p]=i;
    fo(i,1,n) b[i].p=a[z[b[i].p]].p=z[b[i].p];
    fo(i,1,n)
    {
        l[b[i].p]=ls[b[i].z];
        r[ls[b[i].z]]=b[i].p;
        ls[b[i].z]=b[i].p;
        put(b[i].x,1);
    }
    fo(i,1,m)
    {
        int k=ls[i];
        ans=max(ans,get(n)-get(a[k].x));
        while(k)
        {
            int x=l[k];
            if(a[k].x-a[x].x>0) ans=max(ans,get(a[k].x-1)-get(a[x].x));
            k=x;
        }
    }
    fo(i,1,n)
    {
        int x=l[i],y=r[i];
        if(a[x].x+1<=a[i].x-1) ans=max(ans,get(a[i].x-1)-get(a[x].x));
        if(a[i].x+1<=a[y].x-1) ans=max(ans,get(a[y].x-1)-get(a[i].x));
        if(a[i].x==89)
        {
            n++;
            n--;
        }
        if(y==0) ans=max(ans,get(n)-get(a[i].x));
        put(a[i].x,-1); 
        bz[a[i].z]--;
        if(bz[a[i].z]==0) ans=max(ans,n-i);
        int x1=a[x].x,y1=a[y].x-1;
        if(y==0) y1=n+1;
        if(x==0) x1=0;
        if(x1+1<=y1) ans=max(ans,get(y1)-get(x1));
        r[l[i]]=r[i];
        l[r[i]]=l[i];
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(bz,0,sizeof(bz));
        int s1=0;
        fo(i,1,n) 
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            b[i].x=a[i].x,b[i].y=a[i].y,b[i].z=a[i].z,a[i].p=b[i].p=i;
            if(!bz[a[i].z]) s1++;
            bz[a[i].z]++;
        }
        if(s1<m)
        {
            printf("%d\n",n);
            continue;
        }
        mx=0;
        sort(b+1,b+n+1,cmp);
        fo(i,1,n) 
        {
            if(b[i].x!=b[i-1].x||i==1) mx++;
            mp[i]=mx;
        }
        fo(i,1,n) b[i].x=a[b[i].p].x=mp[i];
        ans=0;
        doit(0);
        fo(i,1,n) bz[a[i].z]++;
        doit(1);
        printf("%d\n",ans);
    }
}