这就是前面所谓“第一次用C++写程序”中写的程序——线段树维护线段染色。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/*
  线段染色问题 线段树维护
  输入格式: 线段长度 颜色数目m(不包括无色)
            左端点1 右短点1 颜色1 (擦除一段线段的颜色时,颜色处写0)
            左端点2 右短点2 颜色2
            ......
            左端点n 右短点n 颜色n
  输出格式: 无色线段长度
            颜色1线段长度
            ......
            颜色m线段长度
*/
#include <cstdlib>
#include <iostream>
using namespace std;
 
const int maxlength=524288;  //线段的长度(2^n形式)
int intcolor[maxlength<<1];  //线段树的节点(存储对应线段的颜色,-1表示此节点左右子节点颜色不同,0表示无色) 1..maxlength*2-1有效
int intlength;
 
void color(int p,int l,int r,int a,int b,int c)  //p:节点编号; l:节点的左端; a:需染色线段的左端; c:颜色
{
  if (a<=l && b>=r) intcolor[p]=c;
  else if (intcolor[p] != c)
  {
    if (intcolor[p]>=0)
    {
      intcolor[p<<1]=intcolor[(p<<1)+1]=intcolor[p];
      intcolor[p]=-1;
    }
    if ((a<(l+r)>>1)&&(b>(l+r)>>1))
    {
      color(p<<1,l,(l+r)>>1,a,(l+r)>>1,c);
      color((p<<1)+1,(l+r)>>1,r,(l+r)>>1,b,c);
    }
    else if (a<(l+r)>>1) color(p<<1,l,(l+r)>>1,a,b,c);
    else if (b>(l+r)>>1) color((p<<1)+1,(l+r)>>1,r,a,b,c);
    if (intcolor[p<<1]==intcolor[(p<<1)+1]) intcolor[p]=intcolor[p<<1];
  }
}
 
int findc(int p,int l,int r,int c)  //p:节点编号; c:颜色
{
  int cl=0,cr=0;
  if (intcolor[p]==c) return r-l;
  else if (intcolor[p]==-1)
  {
    cl=findc(p<<1,l,(l+r)>>1,c);
    cr=findc((p<<1)+1,(l+r)>>1,r,c);
    return cl+cr;
  }
  return 0;
}
 
int main()
{
  memset(intcolor,0,sizeof(intcolor));
  int noc,a,b,c;
  cin>>intlength>>noc;
  while (cin>>a>>b>>c)
  {
    color(1,0,intlength,a,b,c);
  //  cout<<findc(1,0,intlength,1)<<endl;
  }
  for (int i=0;i<=noc;i++) cout<<findc(1,0,intlength,i)<<endl;
  return 0;
}