> 
> 
> 要好好消化～～～
> 以下为我第一次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;
> }
> 

• 这回怎么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