Codeforces 369E Valera and Queries【逆向思维+离线+树状数组】好题！好题！好题！

3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8

3
1
0

题目大意：

一共有N个区间，有M组询问，每组询问包含一些点，问这组点会在多少个区间内出现（一个区间只会被覆盖一次）。

思路（源自：http://blog.csdn.net/l123012013048/article/details/49314335）：

正难则反.

遇事不决先打表.

1、我们正着做很显然有两种查询方式：

①每次拿出一个区间，然后到每组查询中看看是否有点在这个区间内，如果有，ans【这组查询的编号】++即可，这里可以使用二分优化查询速度，但是因为组数比较多，即使二分加速也只能加速一组内的点查询问题，所以时间复杂度还是容不下。

②每次拿出一个组，然后每组中拿出一个点进行查询，询问这个点会在多少个区间内出现过，这个很好处理，但是处理点与点之间去重的问题的时候，就显得非常难了。

既然正着做怎么搞都是那么的难，那么我们不妨引入“正难则反”的思路来想这个题

2、反向思考，那就是对于一组点的查询中，我们查询一共有多少个区间不会被点所覆盖，记数量为x，那么ans=n-x.

对于一组点的查询中，问题转化为求区间：【a[i]+1，a[i+1]-1】所包含的整个区间的个数为多少个。

那么我们考虑将所有区间按照l从大到小排序，然后再按照r从小到大排序。

那么对于排序得到的数组，如果我们查询一个区间【L,R】中有多少个整个区间，那么对应其之前的所有区间的L都一定在这个区间的右边，所以我们只要查询之前的区间中，有多少个区间的r小于等于R即可.

那么这里使用树状数组加速查询。

3、注意如果查询区间【L,R】和原来给出的区间的L,R相等的话，排序优先级是原串优先。

细节处理详情参考代码。主体思路已经尽力描述出来了。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1003000
struct node
{
    int l,r,pos;
}a[13080000];
int ans[300080];
int tree[1004005];//树
int cmp(node a,node b)
{
    if(a.l==b.l)
    {
        if(a.r==b.r)return a.pos<b.pos;
        else  return a.r<b.r;
    }
    else return a.l>b.l;
}
int lowbit(int x)//lowbit
{
    return x&(-x);
}
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
void add(int x,int c)
{
    while(x<=N)
    {
        tree[x]+=c;
        x+=lowbit(x);
    }
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int tot=0;
        memset(tree,0,sizeof(tree));
        memset(ans,0,sizeof(ans));
        for(int i=0;i<n;i++)scanf("%d%d",&a[tot].l,&a[tot].r),a[tot++].pos=0;
        for(int i=1;i<=m;i++)
        {
            int pre=-1;
            int mi;scanf("%d",&mi);
            for(int j=0;j<mi;j++)
            {
                int x;scanf("%d",&x);
                if(pre==-1)
                {
                    if(x>1)
                    {
                        a[tot].l=1;a[tot].r=x-1;a[tot++].pos=i;
                    }
                    pre=x;
                }
                else
                {
                    if(x-1>=pre+1)
                    {
                        a[tot].l=pre+1,a[tot].r=x-1;a[tot++].pos=i;
                    }
                    pre=x;
                }
            }
            a[tot].l=pre+1,a[tot].r=1000020,a[tot++].pos=i;
        }
        sort(a,a+tot,cmp);
        for(int i=0;i<tot;i++)
        {
            if(a[i].pos==0)
            {
                add(a[i].r,1);
            }
            else
            {
                ans[a[i].pos]+=sum(a[i].r);
            }
        }
        for(int i=1;i<=m;i++)printf("%dn",n-ans[i]);
    }
}

最后

以上就是怕孤单花瓣为你收集整理的Codeforces 369E Valera and Queries【逆向思维+离线+树状数组】好题！好题！好题！的全部内容，希望文章能够帮你解决Codeforces 369E Valera and Queries【逆向思维+离线+树状数组】好题！好题！好题！所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。