牛客NOIP暑期七天营-普及组2-D线段

题目大意：已知n条线段的左右端点与颜色，现有m个循环，问区间中被完全包含的线段有多少种颜色？

36分，普及组该拿的分数：对于每个区间，暴力枚举每条线段，统计颜色数——只有颜色恰好加到1，才算增加一种颜色的线段。

    for(i=1; i<=m; i++){
        ans = 0;
        for(j=1; j<=n; j++){
            if(x[i]<=l[j] && r[j]<=y[i]){
                if(++f[c[j]] == 1) ans++;
            }
        }
        printf("%d\n", ans);
        for(j=1; j<=n; j++){
            if(x[i]<=l[j] && r[j]<=y[i]) --f[c[j]];
        }
    }

满分：树状数组，感觉超过普及组范围了。

这是离线做法，将线段和循环一起排序；保存在同一个结构体，注意标记好，便于后面区分。如线段有颜色c，询问有编号i。

贪心1：线段问题，通常都按某端点排序，这里也不例外。
按照右端点排序，询问排在线段后面。这样的好处是，查询的时候不需要管右端点了，查询区间内左端点的数量就是覆盖的线段数量。因为之前的线段右端点都小，要么在区间内，左端点也在就算；要么不在区间内，左端点肯定也不在。（颜色各不相同的数据提示统计线段数）

贪心2：同一种颜色只算1次，对于“排在前面”的两根同色线段，左端点越靠右越好，靠左边的可以删除。对于后面的询问来说，如果左边的被包含，右边的也必会被包含，右边的做代表就可以了。开个数组记录每种颜色最靠右的位置，如果出现更靠右的，删除之前的左端点，增加当前的左端点。

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n, m, i, j, k, l, r, c;
int s[N], f[N], ans[N>>2];
struct LR{
    int l, r, c, i;
    bool operator < (const LR &A) const{
        if(r != A.r) return r < A.r;
        return c > A.c;
    }
} d[N*5];
void jia(int i, int x){
    while(i < N) s[i] += x, i += -i&i;
}
int he(int i){
    int c = 0;
    while(i) c += s[i], i -= -i&i;
    return c;
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d%d%d", &d[i].l, &d[i].r, &d[i].c);
    }
    for(n+=m; i<=n; i++){
        scanf("%d%d", &d[i].l, &d[i].r);
        d[i].i = i + m - n;
    }
    sort(d+1, d+n+1);
    for(i=1; i<=n; i++){
        l = d[i].l, r = d[i].r, c = d[i].c, j = d[i].i;
        if(j){
            ans[j] = he(r) - he(l-1);
        }
        else{
            if(!f[c]) jia(f[c]=l, 1);
            else if(l > f[c]){
                jia(f[c], -1);
                jia(f[c]=l, 1);
            }
        }
    }
    for(i=1; i<=m; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}