题解：P15482 [CERC2012] Jewel heist

· · 题解

枚举是哪种颜色没有选到，然后从下往上扫这种颜色的每个点，每次找到在当前点下面的最右的左边的点和最左的右边的点，那么这三个点中间围出来的矩形就可能是最优答案。

这个横向的区间可以用类似 ODT 的方法用 set 维护，一开始有一个 [1,n]，每次找到一个 p 就把所在的区间 [l,r] 分割为 [l,p-1] 与 [p+1,r] 即可。特别地，最后 set 里剩下的所有区间也都可能是最优答案，向上的距离是无限的。

显然这样的矩形个数是 O(n) 个的。那么找到所有矩形之后，离线下来跑二维偏序即可。

复杂度 O(n \log n)，常数可能略大。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
const int N=1e6+10,mod=1e9+7;
int x[N],y[N],c[N];
int b[N];
void lsh(int* a,int n)
{
    for(int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
}
bool vis[N];
vector<pii>pos[N];
vector<pair<pii,int>>tms;
vector<pii>qs[N];
vector<int>ms[N];
int ans[N];
int cid;
int n,k;
struct bit
{
    int c[N];
    void add(int x,int v){for(;x<=n;x+=lowbit(x)) c[x]+=v;}
    int sum(int x){int s=0;for(;x;x-=lowbit(x)) s+=c[x];return s;}
}bit;
void solve()
{
    cin>>n>>k;
    tms.clear();
    for(int i=1;i<=k;i++) pos[i].clear();
    for(int i=1;i<=n;i++) qs[i].clear(),ms[i].clear();
    memset(bit.c,0,sizeof(bit.c));
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof(ans));
    cid=0;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>c[i];
    lsh(x,n),lsh(y,n);
    for(int i=1;i<=n;i++) pos[c[i]].pb(y[i],x[i]);
    for(int i=1;i<=k;i++)
    {
        sort(pos[i].begin(),pos[i].end());
        set<pii>ds;
        ds.insert({1,n});
        for(int j=0;j<pos[i].size();j++)
        {
            auto v=pos[i][j];
            if(vis[v.se]) continue;
            vis[v.se]=1;
            auto p=prev(ds.upper_bound({v.se,1e9}));
            tms.pb(pii(p->fi,p->se),v.fi-1);
            if(p->fi<v.se) ds.insert({p->fi,v.se-1});
            if(v.se<p->se) ds.insert({v.se+1,p->se});
            ds.erase(p);
        }
        for(auto v:pos[i]) vis[v.se]=0;
        for(auto v:ds) tms.pb(pii(v.fi,v.se),n);
    }
    for(auto v:tms)
    {
        qs[v.fi.se].pb(v.se,++cid);
        qs[v.fi.fi-1].pb(v.se,-cid);
    }
    for(int i=1;i<=n;i++) ms[x[i]].pb(y[i]);
    for(int i=1;i<=n;i++)
    {
        for(auto v:ms[i]) bit.add(v,1);
        for(auto v:qs[i])
        {
            int t=bit.sum(v.fi);
            if(v.se>0) ans[v.se]+=t;
            else ans[-v.se]-=t;
        }
    }
    int sss=0;
    for(int i=1;i<=cid;i++) sss=max(sss,ans[i]);
    cout<<sss<<'\n'; 
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

:::