pku 2528 Mayor's posters

时间：2011-05-13 来源：奋斗青春

刚开始写这道题目的时候用的是离散化。。

把所有的坐标都给存到数组里面，然后对数组进行排序。。

然后每帖一张海报就二分找到两个端点，最后对所有的顶点枚举一遍就行了，，

写出来后在pku很快就AC了，之后又在南工交，wa了，感觉存在某些实例过不了。。

在pku的discuss里果然发现了，每一个顶点它不单纯的只是一个顶点，它是一段板。

比如

1 10

1 3

6 10

这组实例就没能过，因为对于3和6之间的那一段距离访问不到。。

之后又想了一种方法，如果排序之后的两个相邻点之间的距离不为1，

就增加一个顶点，可以是他们两个之间的任一点，不过为了方便起见，增加s[i-1]+1这个点。

（对于上面的那个例子而言，3和6虽然相邻，但是他们之间仍存在点，所以这个时候就增加一个顶点4），这样就把所有的情况给考虑完整了。

在南工上也A了（2000+ms）。。

中午吃过饭后发现，南工竟然把时间给改了，改成1000ms了，顿时无语了。。

非得逼着让用线段树啊。。==。。

下午过来，就试着用线段树写了下，写着写着，感觉用线段树其实还挺简单的。。

tree树里面的每一个节点只需要三个域。

l,r存左右边界，增加一个cp标记该节点是否被某一张海报完全覆盖。。

像离散化、添加顶点这些，都还是要用到的。。

最后在pku上AC（78ms），南工（108ms）。

贴一个线段树的代码：

# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define N 10005
struct node{
        int x1,x2;
}s[N];
int vis[N],st[2*N],str[4*N],ys,count;
struct node1{
        int l,r;
        int cp;//标记该节点是否被某张海报完全覆盖
}tree[16*N];//在添加顶点之后，最坏情况下，顶点数会达到4*N
int cmp(const void *a,const void *b)
{
        return *(int *)a - *(int *)b;
}
int find(int x)
{
        //必须找得到
        int mid,l,r;
        l=1;
        r=ys;
        while(r>=l)
        {
                mid=(l+r)/2;
                if(str[mid]>x) r=mid-1;
                else if(str[mid]<x) l=mid+1;
                else return mid;
        }
}
void bulid(int l,int r,int t)
{
        int mid;
        tree[t].l=l;
        tree[t].r=r;
        tree[t].cp=0;
        if(l==r) return;
        mid=(l+r)/2;
        bulid(l,mid,2*t);
        bulid(mid+1,r,2*t+1);
}
void updata(int l,int r,int t,int num)
{
        if(tree[t].l==l && tree[t].r==r)
        {
                tree[t].cp=num;
                return;
        }
        if(tree[t].cp!=0)
        {
                tree[2*t].cp=tree[2*t+1].cp=tree[t].cp;
                tree[t].cp=0;
        }
        if(r<=tree[2*t].r) updata(l,r,2*t,num);
        else if(l>=tree[2*t+1].l) updata(l,r,2*t+1,num);
        else 
        {
                updata(l,tree[2*t].r,2*t,num);
                updata(tree[2*t+1].l,r,2*t+1,num);
        }
}
void query(int t)
{
        if(tree[t].cp!=0) 
        {
                if(vis[tree[t].cp]==0)
                {
                        count++;
                        vis[tree[t].cp]=1;
                }
                return;
        }
        if(tree[t].l==tree[t].r) return;
        query(2*t);
        query(2*t+1);
}
int main()
{
        int i,n,ncase,k,ans1,ans2;
        scanf("%d",&ncase);
        while(ncase--)
        {
                scanf("%d",&n);
                k=0;
                for(i=1;i<=n;i++)
                {
                        scanf("%d%d",&s[i].x1,&s[i].x2);
                        k++;
                        st[k]=s[i].x1;
                        k++;
                        st[k]=s[i].x2;
                }
                qsort(st+1,k,sizeof(st[1]),cmp);
                ys=1;
                str[1]=st[1];
                for(i=2;i<=k;i++)
                {
                        if(st[i]!=st[i-1])
                        {
                                if(st[i]!=st[i-1]+1) 
                                {
                                        ys++;
                                        str[ys]=st[i-1]+1;
                                }
                                ys++;
                                str[ys]=st[i];
                        }
                }//增加顶点，并除去相等的顶点。
                bulid(1,ys,1);
                for(i=1;i<=n;i++)
                {
                        ans1=find(s[i].x1);
                        ans2=find(s[i].x2);//二分找到边界
                        updata(ans1,ans2,1,i);
                }
                memset(vis,0,sizeof(vis));
                count=0;
                query(1);//遍历一次，查询
                printf("%d\n",count);
        }
        return 0;
}

训练也两三天了，感觉状态还不错，争取坚持到省赛之后。。

Come On.......