M_sea

BZOJ4548 小奇的糖果
BZOJ分析用树状数组维护一下横坐标区间内有多少糖果,用双向链表维护左边、右边横坐标最接近的同色的糖果。先考虑选直...
扫描右侧二维码阅读全文
22
2018/12

BZOJ4548 小奇的糖果

BZOJ

分析

用树状数组维护一下横坐标区间内有多少糖果,用双向链表维护左边、右边横坐标最接近的同色的糖果。

先考虑选直线下方的情况:

首先,枚举哪种颜色不选,然后找出所有不包含这种颜色的区间更新答案

然后,按纵坐标从小到大枚举所有点(可以想象成所求直线向上移),在双端链表中删掉它,并在树状数组中删除所有与它纵坐标相同的点。

把纵坐标全部取相反数就变成了直线上方的情况

横坐标要离散。注意清数组。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

struct candy { int x,y,z,id; } a[MAXN];
inline int cmpx(candy x,candy y) { return x.x<y.x; }
inline int cmpy(candy x,candy y) { return x.y<y.y; }
int n,k,ans=-1;

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=n+1) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int y=0; while (x) y+=c[x],x^=lowbit(x); return y; }
inline int query(int l,int r) { return l<=r?sum(r)-sum(l-1):-1; }

int tmp[MAXN],x[MAXN];
int last[MAXN];
int L[MAXN],R[MAXN];


inline void init() {
    x[0]=0,x[n+1]=n+1;
    memset(last,0,sizeof(last));
    memset(c,0,sizeof(c));
}

inline void solve() {
    init(); sort(a+1,a+n+1,cmpx);
    for (re int i=1;i<=n;++i) add(a[i].x,1);
    for (re int i=1;i<=n;++i) {
        int id=a[i].id,color=a[i].z,pre=last[color];
        L[id]=pre,R[id]=n+1,last[color]=id;
        if (pre) R[pre]=id;
        ans=max(ans,query(x[pre]+1,x[id]-1)); //相邻的两个同种颜色的糖果之间
    }
    for (re int i=1;i<=k;++i) ans=max(ans,query(x[last[i]]+1,n+1)); //每种颜色的最后一个糖果到最后
    sort(a+1,a+n+1,cmpy);
    for (re int i=1,j=1;i<=n;++i) {
        int id=a[i].id;
        while (j<=n&&a[j].y==a[i].y) add(a[j].x,-1),++j;
        L[R[id]]=L[id],R[L[id]]=R[id];
        ans=max(ans,query(x[L[id]]+1,x[R[id]]-1));
    }
}

int main() {
    int T=read();
    while (T--) {
        ans=-1,n=read(),k=read();
        for (re int i=1;i<=n;++i)
            a[i].x=read(),a[i].y=read(),a[i].z=read(),a[i].id=i;
        for (re int i=1;i<=n;++i) tmp[i]=a[i].x;
        sort(tmp+1,tmp+n+1); int m=unique(tmp+1,tmp+n+1)-tmp-1; //离散化
        for (re int i=1;i<=n;++i)
            x[i]=a[i].x=lower_bound(tmp+1,tmp+m+1,a[i].x)-tmp;
        solve();
        for (re int i=1;i<=n;++i) a[i].y=-a[i].y;
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 01 月 09 日 07 : 50 AM

发表评论