Source Code

Problem: 2528  User: Sona 
Memory: 3428K  Time: 110MS 
Language: G++  Result: Accepted 

Source Code 
#include"iostream"
#include"algorithm"
using namespace std;
int sa[80010],a[80010],s[80010][2],n,d,f;
struct node
{
  int beg,end,num,flag;       
}tree[160010];
int search(int x)
{
  int l=0,r=d-1,m;    
  while(1)
    {
    m=(l+r)/2;
    if(a[m]==x)
      return m;
    else
      if(a[m]>x)
        r=m-1;
      else
        l=m+1;          
    }
}
void Inp(void)
{
  int i;
  d=1;
  scanf("%d",&n); 
  for(i=0;i<n;i++)
    {
    scanf("%d%d",&s[i][0],&s[i][1]);
    sa[i*2]=s[i][0];
    sa[i*2+1]=s[i][1];              
    }
  sort(sa,sa+2*n);
  a[0]=sa[0];
  for(i=1;i<2*n;i++)
    if (sa[i]!=sa[i-1])
      if (sa[i]==sa[i-1]+1)
        a[d++]=sa[i];
      else
        {
        a[d++]=sa[i-1]+1;
        a[d++]=sa[i];             
        }  
  for(i=0;i<n;i++)
    {
    s[i][0]=search(s[i][0]);              
    s[i][1]=search(s[i][1]);    
    }   
  memset(a,0,sizeof(a));  
  memset(tree,0,sizeof(tree));   
}
void Create(int p,int beg,int end)
{
  while(1){
  tree[p].beg=beg;
  tree[p].end=end;
  tree[p].flag=tree[p].num=0;
  if (beg==end)
    return;
  Create(p*2,beg,(beg+end)/2);  
  p=p*2+1;
  beg=(beg+end)/2+1;  
  }  
}
void Loop(int p,int beg,int end,int x)
{
  if (tree[p].beg>end||tree[p].end<beg)
    return;
  if (tree[p].beg>=beg&&tree[p].end<=end)
    {
    tree[p].num=tree[p].flag=x;                                     
    return;
    }
  tree[p].num=-1;
  if (tree[p].flag)
    tree[p*2].num=tree[p*2].flag=tree[p*2+1].num=tree[p*2+1].flag=tree[p].flag;
  tree[p].flag=0;
  Loop(p*2,beg,end,x);
  Loop(p*2+1,beg,end,x);
  if (tree[p*2].num==tree[p*2+1].num)    
    tree[p].num=tree[p*2].num;
} 
void Get(int p)
{
  int i;
  if (tree[p].num>0)
    {
    a[tree[p].num]=1;
    return;
    }
  if (tree[p].beg==tree[p].end)
    return;  
  Get(p*2);
  Get(p*2+1);  
}
void Cl(void)
{
  int i,res=0;
  Create(1,0,d-1);
  for(i=0;i<n;i++)
    Loop(1,s[i][0],s[i][1],i+1);
  Get(1);
  for(i=0;i<d;i++)
    res+=a[i];
  cout<<res<<endl;       
}
int main()
{
  int c,i;
  scanf("%d",&c);
  for(i=0;i<c;i++)
    {
    Inp();
    Cl();
    }  
  system("pause");  
  return 0;  
} 

• 哈哈。63MS，查了好久错，死马当作活马医加大一倍所有数组，居然A了。。 (0) userfriendly 2009-03-23 17:10:36