HDU 6183 Color it(动态开点线段树)

题目原网址:http://acm.hdu.edu.cn/showproblem.php?pid=6183

题目中文翻译:

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 1677 Accepted Submission(s): 500

Problem Description

你喜欢画画吗？ Little D不喜欢画画，特别是杂乱的彩色画。现在Little B正在画画。为了防止他画出凌乱的画作，Little D要求你写一个程序来维持以下的操作。这些操作的具体格式如下。

0：清除所有点。

1 x y c：在点（x，y）处添加颜色为c的点, 注意这里一个点可以有很多种颜色，是不会被覆盖的。

2 x y1 y2：计算方形（1，y1）和（x，y2）中有多少种不同的颜色。也就是说，如果存在着色点c（a，b），即1≤a≤x且y1≤b≤y2，则应计算颜色c。

3：退出。

Input

输入包含许多行。

每行包含一个操作。它可以是'0'，'1 x y c'（1≤x，y≤10⁶,0≤c≤50），'2 x y1 y2'（1≤x，y1，y2≤10⁶）或'3'。

x，y，c，y1，y2都是整数。

假设最后一个操作是3，它只出现一次。

操作1和操作2的连续操作最多为150000次。

最多有10个操作0。

Output

对于每个操作2，输出整数表示答案。

Sample Input

1 1000000 1000000 50

1 1000000 999999 0

1 1000000 1000000 49

2 1000000 1000000 1000000

2 1000000 1 1000000

1 1 1 1

2 1 1 2

1 1 2 2

2 1 1 2

1 2 2 2

2 1 1 2

1 2 1 3

2 2 1 2

2 10 1 2

2 10 2 2

1 1 1 1

2 1 1 1

1 1 2 1

2 1 1 2

1 2 2 1

2 1 1 2

1 2 1 1

2 2 1 2

2 10 1 2

2 10 2 2

Sample Output

解题思路:

这道题有50种颜色需要我们处理,比较麻烦,我们不妨先考虑只有一种颜色怎么解决.

因为这道题要我们求的方形是十分特殊的,为（1，y1）和（x，y2）,那就说明这个方形是紧贴y轴分布的:

然后我们就会清楚地发现,只要这个颜色的点纵坐标在y1和y2之间,并且横坐标小于x即可.

然后我们在y轴上维护一个线段树,记录x最小值即可(因为只要小于x即可,所以我们只需要记录最小的那一个).

回归正题,我们刚才成功的处理了一种颜色的情况,现在再来考虑50种颜色的情况.

最容易想到的就是维护50个线段树,对于这道题而言时间限制完全可以,但是对于空间则不满足要求,所以我们引用一个优化的方法

----动态开点线段树,它的工作原理就是每当我要用到一个点来维护一个区间时,现开一个空间给它,用不到的点我就不去开辟也不去访,只需提前开两倍的空间即可,大大降低空间浪费.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int noip,noi,root[51],flag;
 8 struct kkk {
 9     int ls,rs,value;//因为用一棵线段树维护50种颜色,所以不能用2i和2i+1表示左右儿子了 
10     kkk() {ls = rs = value = 0;}
11 }e[3000001];
12 
13 void update(int &c,int l,int r,int v,int h) {
14     if(!c) {//如果当前点没被开辟,现开辟一个 
15         c = ++noi;
16         e[c].value = v;
17     }
18     e[c].value = min(e[c].value,v);//因为要求最小值 
19     if(l == r) return ;//如果是叶子节点,就返回 
20     int mid = (l + r) >> 1;
21     if(h <= mid) update(e[c].ls,l,mid,v,h);//开左儿子 
22     else update(e[c].rs,mid + 1,r,v,h);//开右儿子 
23 }
24 
25 void yin_wei_bu_hui_zhe_ge_de_ying_wen_suo_yi_yong_zhong_wen_jiao_cha_xun(int c,int x,int l,int r,int ll,int rr) {
26     if(flag || !c) return ;//如果已经有一个点在方形内或这个点没被开辟,就返回 
27     if(ll <= l && rr >= r) {//如果纵坐标满足要求 
28         if(e[c].value <= x) flag = 1;//横坐标满足要求,说明在方形内,标记一下 
29         return ;
30     }
31     int mid = (l + r) >> 1;
32     if(ll <= mid) yin_wei_bu_hui_zhe_ge_de_ying_wen_suo_yi_yong_zhong_wen_jiao_cha_xun(e[c].ls,x,l,mid,ll,rr); 
33     if(rr > mid) yin_wei_bu_hui_zhe_ge_de_ying_wen_suo_yi_yong_zhong_wen_jiao_cha_xun(e[c].rs,x,mid + 1,r,ll,rr);
34 }
35 
36 int main() {
37     while(scanf("%d",&noip)) {
38         if(noip == 3) break;
39         if(noip == 0) {
40             for(int i = 1;i <= noi; i++) e[i].ls = e[i].rs = e[i].value = 0;
41             for(int i = 0;i <= 50; i++) memset(root,0,sizeof(root));
42             noi = 0;
43         }
44         if(noip == 1) {
45             int x,y,c;
46             scanf("%d%d%d",&x,&y,&c);
47             update(root[c],1,1000000,x,y);
48         }
49         if(noip == 2) {
50             int x,x1,y1;
51             scanf("%d%d%d",&x,&x1,&y1);
52             int ans = 0;
53             for(int i = 0;i <= 50; i++) {
54                 flag = 0;
55                 yin_wei_bu_hui_zhe_ge_de_ying_wen_suo_yi_yong_zhong_wen_jiao_cha_xun(root[i],x,1,1000000,x1,y1);
56                 if(flag) ans++;
57             }
58             printf("%d
",ans);
59         }
60     }
61     return 0;
62 }