1 /*
   2 ymc 2009/4/8 线段树
   3 zju 1610
   4 题目大意:
   5 在x轴上,每次在某一个区间画一种颜色,求最后每种颜色的
   6 选段要多少条。
   7 l[i],r[i],c[i]表示在区间[l[i],r[i]]上画颜色c[i]
   8 (颜色保存的时候保存c[i]+1,因为会出现0号颜色,但是
   9 线段树中用0表示背景色)
  10 用Left,Right记录最左边的左边和最右边的坐标
  11 用Left_c,Right_c记录最小的颜色和最大的颜色
  12 flag[i]记录第i号颜色的线段数。
  13 */
  14 
  15 #include <iostream>
  16 #include <limits>
  17 using namespace std;
  18 const int N=20000;
  19 int tree[N];
  20 int l[N],r[N],c[N];
  21 int flag[N];
  22 int n;
  23 int Left,Right,Left_c,Right_c;;
  24 void Init()
  25 {
  26     Left=INT_MAX;
  27     Right=INT_MIN;
  28     Left_c=INT_MAX;
  29     Right_c=INT_MIN;
  30     for(int i=0;i<n;i++)
  31     {
  32         scanf("%d %d %d",&l[i],&r[i],&c[i]);
  33         if(l[i]<Left)
  34             Left=l[i];
  35         if(r[i]>Right)
  36             Right=r[i];
  37         c[i]++;
  38         if(c[i]<Left_c)
  39             Left_c=c[i];
  40         if(c[i]>Right_c)
  41             Right_c=c[i];
  42     }
  43     for(int k=1;k<=2*(Right-Left);k++)
  44         tree[k]=0;//0为初始颜色即背景颜色
  45     for(int k=Left_c;k<=Right_c;k++)
  46         flag[k]=0;//所有颜色的线段数初始为0
  47 }
  48 
  49 /*
  50 在以tree[k]为树根的线段树(代表的区间为[l,r])上
  51 在区间[a,b]颜色c
  52 */
  53 void Insert(int k,int l,int r,int a,int b,int c)
  54 {
  55     if(tree[k]==c)//已经有的颜色要要画的颜色相同
  56         return;
  57     if(l==a&&r==b)//正好画满整个线段树
  58     {
  59         tree[k]=c;
  60         return;
  61     }
  62     if(tree[k]>=0)//[l,r]上已有一种颜色,则上色后有多种颜色
  63     {
  64         tree[2*k]=tree[k];
  65         tree[2*k+1]=tree[k];
  66         tree[k]=-1;//-1表示该区间有多种颜色
  67     }
  68     int m=(l+r)/2;
  69     if(b<=m)//左儿子上色
  70         Insert(2*k,l,m,a,b,c);
  71     else if(m<=a)//右儿子上色
  72         Insert(2*k+1,m,r,a,b,c);
  73     else//左右儿子均上色
  74     {
  75         Insert(2*k,l,m,a,m,c);
  76         Insert(2*k+1,m,r,m,b,c);
  77     }
  78 }
  79 /*
  80 在以tree[k]为树根的线段树[l,r]上统计不同颜色的线段数
  81 lc,rc为[l,r]上左右端点的颜色
  82 */
  83 void Count(int k,int l,int r,int &lc,int &rc)
  84 {
  85     if(tree[k]>=0)//[l,r]上颜色单一
  86     {
  87         lc=tree[k];//父节点需要知道
  88         rc=tree[k];
  89         flag[tree[k]]++;
  90         return ;
  91     }
  92     if(l>=r)    return;
  93     int tl,tr;
  94     Count(2*k,l,(l+r)/2,lc,tl);//统计左儿子
  95     Count(2*k+1,(l+r)/2,r,tr,rc);//统计右儿子
  96     if(tl==tr)//左儿子的最右线段与右儿子的最左线段同色
  97         flag[tl]--;
  98 }
  99 void Solve()
 100 {
 101     for(int i=0;i<n;i++)
 102         Insert(1,Left,Right,l[i],r[i],c[i]);
 103     int lc,rc;
 104     Count(1,Left,Right,lc,rc);
 105 }
 106 void OutPut()
 107 {
 108     for(int k=Left_c;k<=Right_c;k++)
 109         if(flag[k]>0)
 110             printf("%d %d\n",k-1,flag[k]);
 111 }
 112 int main()
 113 {
 114    while(scanf("%d",&n)!=EOF)
 115    {
 116         Init();
 117         Solve();
 118         OutPut();
 119         printf("\n");
 120    }
 121 }

   1 /*
   2 1610 Count the Colors
   3 ymc
   4 */
   5 
   6 #include <iostream>
   7 using namespace std;
   8 const int N=8010;
   9 struct Point
  10 {
  11     int e;  
  12     int s;  
  13 };
  14 Point a[N];
  15 int b[N];
  16 int n;
  17 
  18 int main()
  19 {
  20     int c,d,color;
  21     while( scanf("%d",&n)!=EOF )
  22     {
  23         for(int i=0;i<N;i++)
  24         {
  25             a[i].s=a[i].e=-1;
  26             b[i]=0;
  27         }
  28         for(int i=0;i<n;i++)
  29         {
  30             scanf("%d %d %d",&c,&d,&color);
  31             a[c].s=color;
  32             a[d].e=color;
  33             for(int k=c+1;k<d;k++)
  34                 a[k].s=a[k].e=color;            
  35         }
  36         int k;
  37         for(int i=0;i<N-1;)
  38         {
  39             while(a[i].s==-1)
  40               i++;
  41             k=i;
  42             while(k<N&&a[k].s==a[i].s)
  43                 k++;
  44                     if(k>=N) break;
  45             b[a[i].s]++;
  46             i=k;
  47         }
  48         for(int i=0;i<N;i++)
  49             if(b[i]>0)
  50                 printf("%d %d\n",i,b[i]);
  51                         printf("\n");
  52     }   
  53 }

zju1610 参考答案 (last edited 2009-04-11 10:35:48 by 128)

ch3n2k.com | Copyright (c) 2004-2020 czk.