> 我的邮箱是 tju87896001@163.com ,请把程序发给我看看吧(WA的也行,只要结构对)
> 我绝对是为了学习线段树,不会COPY你的程序的!!
> 再再跪啊啊~~~~~~~~~~~~~
> 
> 
> 线段树,你真的好难啊!!!


要好好消化～～～
以下为我第一次ac的线段树，消化不完全产品，离散部分用了stl的map，所以比较慢

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
map<int,int>mp;
struct node{int s,t,c;}t[61000]; 
int n,ct,i,j,ans,k,tn,xn,txn;
int d[10010][2],x[21000];
char hash[10010];

void make_tree(int nd,int st,int ed)
{
     if (nd>tn) tn=nd;
     //printf("nd=%d  st=%d  ed=%d\n",nd,st,ed);
     t[nd].s=st;t[nd].t=ed;t[nd].c=0;
     if (ed-st>1){
       make_tree(nd+nd,st,(st+ed)/2);
       make_tree(nd+nd+1,(st+ed)/2,ed);
     }
     return ;
}

void insert_tree(int nd,int st,int ed,int col)
{
    // printf("nd=%d  st=%d  ed=%d  col=%d\n",nd,st,ed,col);
     if (t[nd].c!=col){
        if (t[nd].s==st&&t[nd].t==ed){ 
           t[nd].c=col;
      //     printf("t[%d].c=%d\n",nd,col);
           return ;}
        int m=(t[nd].s+t[nd].t)/2;
        if (t[nd].c>0){ 
           t[nd+nd].c=t[nd+nd+1].c=t[nd].c;
        //   printf("t[%d].c=%d  t[%d].c=%d\n",nd+nd,t[nd].c,nd+nd+1,t[nd].c);
           t[nd].c=-1;
        }
        if (m<=st) insert_tree(nd+nd+1,st,ed,col);else
        if (m>=ed) insert_tree(nd+nd,st,ed,col);else{
           insert_tree(nd+nd,st,m,col);
           insert_tree(nd+nd+1,m,ed,col);
        }
     }
     return ;
}
           
void count_tree(int nd)
{
     if (t[nd].c>0){ 
        hash[t[nd].c]=1;
       // printf("hash[%d]=%d\n",t[nd].c,hash[t[nd].c]);
     }
     else{
        if (nd+nd<=tn) count_tree(nd+nd);
        if (nd+nd+1<=tn) count_tree(nd+nd+1);
     }
     return ;
}

int main()
{
    scanf("%d",&ct);
    while (ct--){
      memset(d,0,sizeof(d));memset(x,0,sizeof(x));
      memset(hash,0,sizeof(hash));
      scanf("%d",&n);tn=xn=0;mp.clear();
      for (i=0;i<n;i++){
        scanf("%d%d",&d[i][0],&d[i][1]);
        x[xn++]=--d[i][0];x[xn++]=d[i][1];
      }
      sort(x,x+xn);txn=0;
      for (i=0;i<xn;i++) if (mp.find(x[i])==mp.end()) mp[x[i]]=txn++;
      ans=0;xn=txn;
      make_tree(1,0,xn-1);
     // for (i=0;i<n;i++) printf("%d:%d  %d:%d\n",d[i][0],mp[d[i][0]],d[i][1],mp[d[i][1]]);
      for (i=0;i<n;i++) insert_tree(1,mp[d[i][0]],mp[d[i][1]],i+1);
      count_tree(1);
      for (i=1;i<=n;i++) if (hash[i])ans++; 
      printf("%d\n",ans);
     }
     return 0;
}

• 这个……自己底下交流吧，贴出来不大好 (2494) frkstyc 2005-08-08 23:20:46
  • 这回怎么have seen something了? (0) c0500448242 2005-08-08 23:23:16
    • 谁叫你昨天指给我看 (0) frkstyc 2005-08-08 23:24:13
      • ...... (0) c0500448242 2005-08-08 23:24:55
        • 。。。。。横竖都是你的错 (0) sunmoonstar_love 2005-08-08 23:32:02
          • BINGO! (0) frkstyc 2005-08-09 00:19:28