UVALive 6261 Jewel heist

题意：珠宝大盗Arsen Lupin偷珠宝。在展厅内，每颗珠宝有个一个坐标为(xi,yi)和颜色ci。

Arsen Lupin发明了一种设备，可以抓取平行x轴的一条线段下的所有珠宝而不触发警报，

唯一的限制是抓取的珠宝不能不能有所有的m种颜色。询问能抓取的最大珠宝数量。

分析：要决策的东西有两个，一是这条线段的y坐标，二是线段的x的范围。

枚举线段的y坐标，线段宽度要保证下方不能有所有的颜色，这需要知道颜色的关于x的坐标信息，

为了x的坐标信息的重复利用，从小到大枚举y。

对于一个固定的y，怎么找到合适的区间呢？一个简单且正确的想法是枚举不要的颜色，

对于每种不要的颜色，只要选择不包含这种颜色的区间就可以保证符号要求了。

但是这样做太慢了，枚举颜色是O(n)的。

幸运的是，这里面有大量的重复计算，在枚举y的时候，有很多的区间是不会变的，已经计算过的了，

只要枚举发生了改变的区间。

关于颜色的区间信息可以用set保存，在枚举的区间合法的情况下只是一个区间询问单点更新可用BIT，下标范围需要离散。

/*********************************************************

*          ----------------------------                  *

*   author AbyssalFish                                   *

**********************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5+;

set<int> S[maxn];

int x[maxn],y[maxn],c[maxn];

int r[maxn], xs[maxn];

int *cmp_c;

bool cmp_id(int i,int j){ return cmp_c[i] < cmp_c[j]; }

int C[maxn];

int ns;

void add(int x)

{

    while(x <= ns){

        C[x]++; x += x&-x;

    }

}

int sum(int x)

{

    int re = ;

    while(x > ){

        re += C[x]; x &= x-;

    }

    return re;

}

void solve()

{

    int n, m, i, j, k;

    scanf("%d%d",&n,&m);

    for(i = ; i < n; i++) {

        scanf("%d%d%d",x+i,y+i,c+i);

        r[i] = i;

    }

    cmp_c = x;

    sort(r,r+n,cmp_id);

    ns = ;

    xs[r[]] = ns;

    for(i = ; i < n; i++){

        xs[r[i]] = (x[r[i]] == x[r[i-]]) ? ns:++ns;

    }

    for(i = ; i <= m; i++){

        S[i].clear();

        S[i].insert();

        S[i].insert(ns+);

    }

    cmp_c = y;

    for(i = ; i < n; i++) r[i] = i;

    sort(r,r+n,cmp_id);

    memset(C+,,sizeof(int)*ns);

    int ans = , p, q, cur_y;

    for(i = ; i < n; i = k){

        cur_y = y[r[i]];

        for(j = i; j < n && y[k = r[j]] == cur_y; j++){

            auto it = S[c[k]].lower_bound(xs[k]);

            p = *it-;

            q = *--it;

            if(p > q)

                ans = max(ans,sum(p)-sum(q));

        }

        k = j;

        while(--j >= i){

            p = r[j];

            S[c[p]].insert(xs[p]);

            add(xs[p]);

        }

    }

    for(i = ; i <= m; i++){

        auto it = S[i].begin();

        q = ;

        for(it++; it != S[i].end(); it++){

            p = *it-;

            if(p > q) ans = max(ans, sum(p) - sum(q));

            q = *it;

        }

    }

    printf("%d\n", ans);

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int T; scanf("%d",&T);

    while(T--) solve();

    return ;

}