题解：P15482 [CERC2012] Jewel heist

· · 题解

差点场切了，没注意到细节问题。

首先，既然必须有一组宝石不能被区间包含，那么我们就可以钦定颜色为 i 的宝石没有被拿，然后其他颜色的可拿可不拿。为了方便，我们将颜色为 i 的宝石染成红色，其余的染成蓝色。

那么，这里需要分两种情况。

第一种是钦定一个红点 f，为了让能选的区间尽可能大，我们就先让这个区间的 y 值为 y_f-1。然后我们看这个区间的左右能扩展到哪。先只考虑左边，如果某个红点 g 满足 x_g<x_f 且 y_g<y_f，则这个区间就不能够再往左扩展了，无论更往左的其他点如何。右边同理。

然后注意一下边界即可。这个就是模版单调栈，不过要做两遍。

然后这就是二维数点问题了。直接离散化后用扫描线和树状数组即可。

第二种就是我场上没考虑到的，就是这种情况也可以：

可以发现，只有在两个 x 相邻的红点时才会发生，这种情况也是二维数点即可。

::::success[Code]

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fir first
#define sec second
#define is insert
#define es erase
#define pb push_back
#define eb emplace_back
using namespace std;
const int N=2e5+5;
const int INF=1e9+7;
int T,n,k,nxtl[N],nxtr[N],tr[N],ans,st[N];
struct node{
    int x,y,c;
}f[N]; 
inline bool cmp1(const node&PP,const node&QQ){
    return PP.x<QQ.x;
}
inline bool cmp2(const node&PP,const node&QQ){
    return PP.y<QQ.y;
}
vector<int>rec[N];
vector<int>xs,ys;
struct Q{
    int l,r,w;
    inline bool operator<(const Q&oth)const{
        return w<oth.w;
    }
}q[N];
inline int lowbit(int x){
    return x&-x;
}
inline void add(int x){
    for(;x<=n+2;x+=lowbit(x)){
        tr[x]++;
    }
}
inline int ask(int x){
    int res=0;
    for(;x;x-=lowbit(x)){
        res+=tr[x];
    }
    return res;
}
inline void solve(){
    ans=0;
    cin>>n>>k;
    for(int i=0;i<=n+2;i++){
        tr[i]=0;
    }
    xs.clear(),ys.clear();
    for(int i=1;i<=k;i++){
        rec[i].clear();
    }
    f[0].x=0,f[0].y=0;
    f[n+1].x=INF,f[n+1].y=0;
    xs.eb(0);
    xs.eb(INF);
    ys.eb(0);
    for(int i=1;i<=n;i++){
        cin>>f[i].x>>f[i].y>>f[i].c;
        xs.eb(f[i].x);
        ys.eb(f[i].y);
    }
    sort(xs.begin(),xs.end());
    sort(ys.begin(),ys.end());
    xs.es(unique(xs.begin(),xs.end()),xs.end());
    ys.es(unique(ys.begin(),ys.end()),ys.end());
    for(int i=0;i<=n+1;i++){
        f[i].x=lower_bound(xs.begin(),xs.end(),f[i].x)-xs.begin();
        f[i].y=lower_bound(ys.begin(),ys.end(),f[i].y)-ys.begin();
    }
    sort(f+1,f+n+1,cmp1);
    for(int i=1;i<=n;i++){
        rec[f[i].c].eb(i);
        nxtr[i]=n+1;
        nxtl[i]=0;
    }
    for(int i=1;i<=k;i++){
        int top=0;
        for(int j=0;j<rec[i].size();j++){
            while(top&&f[rec[i][j]].y<f[rec[i][st[top]]].y){
                nxtr[rec[i][st[top]]]=rec[i][j];
                top--;
            }
            st[++top]=j;
        }
        top=0;
        for(int j=rec[i].size()-1;j>=0;j--){
            while(top&&f[rec[i][j]].y<f[rec[i][st[top]]].y){
                nxtl[rec[i][st[top]]]=rec[i][j];
                top--;
            }
            st[++top]=j;
        }
    }
    for(int i=1;i<=n;i++){
        q[i].l=f[nxtl[i]].x+1;
        q[i].r=f[nxtr[i]].x-1;
        q[i].w=f[i].y-1;
    }
    for(int i=1;i<=k;i++){
        for(int &j:rec[i]){
            j=f[j].x;
        }
    }
    sort(f+1,f+n+1,cmp2);
    sort(q+1,q+n+1);
    int p=1;
    for(int i=1;i<=n;i++){
        while(p<=n&&f[p].y<=q[i].w){
            add(f[p].x);
            p++;
        }
        ans=max(ans,ask(q[i].r)-ask(q[i].l-1));
    }
    while(p<=n){
        add(f[p].x);
        p++;
    }
    for(int i=1;i<=k;i++){
        if(rec[i].empty())continue;
        for(int j=0;j<rec[i].size()-1;j++){
            ans=max(ans,ask(rec[i][j+1]-1)-ask(rec[i][j]));
        }
        ans=max(ans,ask(rec[i][0]-1));
        ans=max(ans,ask(n+2)-ask(rec[i].back()));
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
}

::::