【BZOJ4548】小奇的糖果-树状数组+链表+扫描线

测试地址：小奇的糖果
做法：本题需要用到树状数组+链表+扫描线。
取走的糖果不包含全部的颜色，也就意味着至少有一种颜色不取。
考虑计算不取某种颜色的点的最佳方案，先考虑选择线段下方的方案，可知：如果有一个该颜色的点 $(x, y)$ ，则表示在所取的线段纵坐标 $\geq y$ 时，线段的横坐标区间不能跨越 $x$ 。因此我们从上到下考虑每个该颜色的点 $(x, y)$ ，考虑线段纵坐标为 $y - 1$ 的最大方案，这里我们显然只用考虑有改动的方案，也就是在上面不能取，现在却能取的横坐标区间，这需要找到在这个点下方的，横坐标最接近当前点的同颜色的点的横坐标。我们当然可以用set来解决这个问题，但是常数太大，可能过不了，所以这里我使用了更加稳妥的双向链表来维护。而找到所求的横坐标区间之后，当然就可以用树状数组统计出这个区域中点的数量了。注意我们还要考虑选择的线段的纵坐标为无限大时的方案。
如果我们枚举颜色，对于每种颜色做上面的过程，时间复杂度是 $O (k n \log n)$ 的，完全爆炸。注意到不同颜色之间的操作是互不影响的，所以我们完全可以并行处理，时间复杂度 $O (n \log n)$ 。
而考虑选择线段上方的方案的话，和上面非常相似，只要把每个点的纵坐标取个反再做一遍就行了。注意点的坐标要离散化。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
int T,n,k,totx,toty,ans;
int pre[300010],nxt[300010],head[300010],tail[300010],now[100010];
int sum[100010],pos[100010];
struct forsort
{
    int val,id;
}x[100010],y[100010];
struct point
{
    int x,y,z;
}p[300010];

bool cmp(forsort a,forsort b) {return a.val<b.val;}
bool cmpp(point a,point b) {return a.x<b.x;}
bool cmp1(int a,int b) {return p[a].y>p[b].y;}
bool cmp2(int a,int b) {return p[a].y<p[b].y;}

void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x[i].val,&y[i].val,&p[i].z);
        x[i].id=y[i].id=i;
    }
    sort(x+1,x+n+1,cmp);
    sort(y+1,y+n+1,cmp);
    totx=toty=0;
    for(int i=1;i<=n;i++)
    {
        if (i==1||x[i].val!=x[i-1].val) totx++;
        p[x[i].id].x=totx;
    }
    for(int i=1;i<=n;i++)
    {
        if (i==1||y[i].val!=y[i-1].val) toty++;
        p[y[i].id].y=toty;
    }
}

void insert(int x,int y)
{
    pre[nxt[x]]=y;
    nxt[y]=nxt[x];
    nxt[x]=y;
    pre[y]=x;
}

void Delete(int x)
{
    nxt[pre[x]]=nxt[x];
    pre[nxt[x]]=pre[x];
}

void build()
{
    sort(p+1,p+n+1,cmpp);
    for(int i=1;i<=k;i++)
    {
        head[i]=n+i,tail[i]=(n<<1)+i;
        p[head[i]].x=0,p[tail[i]].x=totx+1;
        nxt[head[i]]=tail[i],pre[tail[i]]=head[i];
        now[i]=head[i];
    }
    for(int i=1;i<=n;i++)
    {
        insert(now[p[i].z],i);
        now[p[i].z]=i;
    }
}

int lowbit(int x)
{
    return x&(-x);
}

void Add(int x,int c)
{
    for(int i=x;i<=totx;i+=lowbit(i))
        sum[i]+=c;
}

int Sum(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=sum[i];
    return ans;
}

int query(int l,int r)
{
    if (l>r) return 0;
    else return Sum(r)-Sum(l-1);
}

bool check(int x,int y,int type)
{
    if (!type) return p[x].y>=p[y].y;
    else return p[x].y<=p[y].y;
}

void work(int type)
{
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++) Add(p[i].x,1);
    for(int i=1;i<=k;i++)
        for(int j=head[i];j!=tail[i];j=nxt[j])
            ans=max(ans,query(p[j].x+1,p[nxt[j]].x-1));
    int last=1;
    for(int i=1;i<=n;i++)
    {
        int x=pos[last],y=pos[i];
        while(last<=n&&check(x,y,type)) Add(p[x].x,-1),x=pos[++last];
        ans=max(ans,query(p[pre[y]].x+1,p[nxt[y]].x-1));
        Delete(y);
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        ans=0;
        build();
        for(int i=1;i<=n;i++) pos[i]=i;
        sort(pos+1,pos+n+1,cmp1);
        work(0);
        build();
        sort(pos+1,pos+n+1,cmp2);
        work(1);
        printf("%d
",ans);
    }

    return 0;
}