Codeforces Round #216 (Div. 2) E. Valera and Queries （BIT）

标题效果：

给很多分布 x 行轴。

然后给出了一个非常的多点集，问该组点分布多少不同段。

IDEAS：

分散成多个线段点集的。

给出的线段的话，也就是说这个点集上不会有点在这条线段上。

所以我们就是求出点集做出的线段包括了多少个给出的线段就能够了。

那么也就是比較l r的大小，排序之后用BIT

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&(-x))
#define maxn 1000005

using namespace std;

struct node
{
    int l,r,p;
    bool operator < (const node &cmp)const
    {
        if(l!=cmp.l)return l>cmp.l;
        if(r!=cmp.r)return r<cmp.r;
        return p<cmp.p;
    }
} line[maxn];
int bit[maxn],ans[maxn],n,m,S=1e6+1;
int sum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))res+=bit[x];
    return res;
}
int add(int x)
{
    for(;x<=S;x+=lowbit(x))bit[x]++;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&line[i].l,&line[i].r);
    int T=n,cnt,p,x;
    for(int i=1;i<=m;i++)
    {
        ans[i]=n;
        scanf("%d%d",&cnt,&p);
        if(p>1)line[++T].l=1,line[T].r=p-1,line[T].p=i;
        for(;--cnt;p=x)
        {
            scanf("%d",&x);
            if(x>p+1)line[++T].l=p+1,line[T].r=x-1,line[T].p=i;
        }
        line[++T].l=p+1,line[T].r=S,line[T].p=i;
    }
    sort(line+1,line+1+T);
    for(int i=1;i<=T;i++)
        if(line[i].p)
            ans[line[i].p]-=sum(line[i].r);
        else add(line[i].r);
    for(int i=1;i<=m;i++)printf("%d
",ans[i]);
    return 0;
}