Codeforce 216 div2

D

　　只要搞清楚一个性质:确定了当前最大和次大的位置,局面就唯一确定了;

　　根据这个性质设计dp,统计到达该局面的方法数即可.

E

　　询问的要求是: 求有多少个区间至少覆盖了询问的点集中的一个;

　　转化成逆命题比较好算: 算出排好序后相邻的点之间有多少个完整区间,再用n减去它.

　　于是问题转化为回答若干询问[l,r] ,它当中有多少个完整的区间.

　　可以用经典的离线+树状数组来做.

　　

#define rep(i,n) for(int i=0 ; i<(n) ; i++ )

#define ls ((rt)<<1)

#define rs (((rt)<<1)+1)

#define mid ((l+r)>>1)

#define maxn 1000002

struct node

{

    int id,lft;

};vector<node>q[maxn];

vector<int>l[maxn];

int sum[maxn],ans[],n,m,cnt[];

int lowbit(int x) {return x&(-x);}

void add(int pos,int var)

{

    for (int i=pos ; i<maxn ; i+=lowbit(i)) sum[i]+=var;

}

int query(int pos)

{

    int res=;

    for (int i=pos ; i> ; i-=lowbit(i)) res+=sum[i];

    return res;

}

int main()

{

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

    rep(i,n)

    {

        int lft,rgt;

        scanf("%d%d",&lft,&rgt);

        l[rgt].push_back(lft);

    }

    rep(i,m)

    {

        int sz;

        scanf("%d",&sz);

        rep(j,sz) scanf("%d",&cnt[j]);

        int lft,rgt;

        lft=,rgt=cnt[]-;

        q[rgt].push_back((node){i,lft});

        rep(j,sz-)

        {

            lft=cnt[j]+;

            rgt=cnt[j+]-;

            if (lft<=rgt) q[rgt].push_back((node){i,lft});

        }

        lft=cnt[sz-]+,rgt=;

        q[rgt].push_back((node){i,lft});

    }

    rep(i,maxn)

    {

        rep(j,(int)l[i].size())

        {

            int pos = l[i][j];

            add(pos,);

        }

        rep(j,(int)q[i].size())

        {

            int id = q[i][j].id;

            ans[id] += query(i)-query(q[i][j].lft-);

        }

    }

    rep(i,m) printf("%d\n",n-ans[i]);

    return ;

}