menu 雨落亭
search
poj 2528 (线段树)
雨落
雨落
Time:
share




成段更新

这题数据很大,数组开不下,要离散化,把输入的区间离散化,映射到相应的小区间,就可以了。离散的时候注意,这是区间离散后会出现些问题,所以离散时将区间差大于1的数后面插入一个数,保证离散正确化,离散的方法,排序,去重,在二分查找,将对应的数组索引作为新的端点。
这里,标记=0表示没有贴,标记大于0 表示贴了,并且不同标记代表不同海报,不断更新,最后查询,将海报数输出。

/*
poj 2528 
该死的 海报板 
n太大了,得离散化 不能普通的离散,使离散区间大一点,所以,在区间大于1的两个数间插个数,隔开些 
*/ 
#include  <cstdio>
#include <cstring> 
#include <algorithm> 
#include <iostream>
#include <vector>
#define MAX 12000
using namespace std;

//int sum[MAX];
int mark[MAX<<4];
int vis[MAX<<1];
int h[MAX<<1];
int w[MAX<<1];
int v[MAX<<2];
int ans =0;
void change_down(int T)
{
  if (mark[T])//
  {
       mark[T<<1] = mark[T<<1|1] = mark[T];
       mark[T]=0;
  }
}

void update(int T,int s,int e,int p,int l,int r)
{
   if (s<= l && e>=r)
    {
      mark[T] = p;
      return;
    }
   else
   {
        change_down(T);
        int mid = (l + r)>>1;
        if (s<=mid)  update(T<<1,s,e,p,l,mid);
        if (e>mid)   update(T<<1|1,s,e,p,mid+1,r);
   }
}

void Query (int T,int l,int r)
{
   if (mark[T])
   {
        if (!vis[mark[T]])
         {
         vis[mark[T]] = 1;
         ans++;
      }
        return;
   }
   if (l==r) return ;
    change_down(T);
    int mid = (l+r)>>1;
    Query(T<<1,l,mid) ;
    Query(T<<1|1,mid+1,r);
}

int main ()
{
    int T;
    int n,a1,b1;
    scanf ("%d",&T);
    while(T--)
    {  memset (mark,0,sizeof(mark));
       memset(vis,0,sizeof (vis));
       scanf ("%d",&n);
       int k=0;
      for (int i=0;i<n;++i)
       {
             scanf ("%d%d",&h[i],&w[i]);
             v[k++]=h[i];v[k++]=w[i];
       }
       sort(v,v+k);
       int size = unique(v,v+k)-v;
       for (int i=0;i<n ;++i)
        {
         a1 = lower_bound(v,v+size,h[i])-v+1;//这里小心了是去重后的大小 
         b1 = lower_bound(v,v+size,w[i])-v+1;//别写成K了, 去重后,元素个数变了,记住 
        //printf ("%d %d\n",a1,b1);          //要不然你就 一直Runtime Error 吧 
         update(1,a1,b1,i+1,1,size);         //wtf !!!!! 
        } 
        ans = 0;
        Query(1,1,size);
       printf ("%d\n",ans);
    }
    return 0;
} 

/*
1
5
1 4
2 6
8 10
3 4
7 10

*/

评论

   textsms
   account_circle
昵称不能为空
   email
邮箱格式错误
   language





message 没有评论惹=_=

arrow_back 上一篇
arrow_back 上一篇
APP漏洞挖掘
下一篇 arrow_forward
poj 3468 (线段树)
下一篇 arrow_forward