Zju1610 Count the Colors（lazy标记详解）

Description

画一些颜色段在一行上，一些较早的颜色就会被后来的颜色覆盖了。
你的任务就是要数出你随后能看到的不同颜色的段的数目。

Input

每组测试数据第一行只有一个整数n, 1 <= n <= 8000,等于填色的次数
接下来的n行每行有三个非负整数，他们之间用一个空格分开。
x1 x2 c
x1和x2表示填色段最左边的点和最右边的点， c表示填进的颜色。
所有数字都是在[0..8000]这个范围里的整数。
输入有多组测试数据，最后以文件结束符为结束。

Output

输出的每一行都是最后能看到的颜色的数字，还有这种颜色的段数。
如果这种颜色最后不能见到，就不要打印出来。
每组数据后面跟一个空行。

Sample Input

Sample Output

郁闷，居然没找到什么好题来当线段树的板子

那就先丢这道水一点的lazy标记吧，看不懂就不要看了，本来就不是入门题

lazy标记：

意如其名，懒标记，就是想少干活（所以快）

区间修改操作最朴素的方法当然就是枚举这个区间中的每个点去单点修改，那么恭喜TLE了

那么有什么办法呢，是不是可以想到我们更新的一些点的值并不一定需要马上用

可能有人不是很懂，那我就举个例子：

如果我们要修改1-5，然后对3-5求和，再修改1-2，最后求和1-5，那么第一次求和中对于1-2这一段的修改是不是无用，我们可以暂时不修改他们，只打个标记，等到第二次再次修改1-2，那我们修改标记就好了，最后求和将标记下传，这样就省了一次修改的时间。

这种方法可以大大优化时间复杂度，也容易写挂，初学者小心行事

额，忽然间发现我选的题有毒，没事，这个就当让大家学学lazy了

题解：

就这题来说，我还是觉得这是道好题，这是我纯手写代码，线段树+暴力AC此题

详情看代码吧：

呼吁大家别学我，一定要写pushdown，不然代码太难看了，我被喷了很多次了

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 struct oo{int a,b,num,lazy;}s[50001];
 6 int n,m,ans[50001],v,sum[30001];
 7 void build(int now,int x,int y)
 8 {
 9     s[now].a=x,s[now].b=y;s[now].lazy=0;ans[now]=-10;
10     if(x==y)
11     {
12         s[now].num=-100;
13         return ;
14     }
15     else
16     {
17         build(now*2,x,x+y>>1);
18         build(now*2+1,(x+y>>1)+1,y);
19         s[now].num=s[now*2].num+s[now*2+1].num;
20     }
21 }
22 void change(int now,int x,int y,int z)
23 {
24     if(x<=s[now].a&&y>=s[now].b)
25     {
26         s[now].lazy=z;
27         s[now].num=z;
28         return ;
29     }
30     if(s[now].lazy!=0)
31     {
32         if(s[now].a!=s[now].b)
33             s[now<<1].lazy=s[now].lazy,s[(now<<1)+1].lazy=s[now].lazy,s[now<<1].num=s[now<<1].lazy,s[(now<<1)+1].num=s[(now<<1)+1].lazy;
34         s[now].lazy=0;
35     }
36     int mid=s[now].a+s[now].b>>1;
37     if(x<=mid)
38         change(now<<1,x,y,z);
39     if(y>mid)
40         change((now<<1)+1,x,y,z);
41     if(s[now<<1].num==-1||s[(now<<1)+1].num==-1)
42         s[now].num=-1;
43     else
44     if(s[now<<1].num!=s[(now<<1)+1].num)
45         s[now].num=-1;
46     else s[now].num=s[now<<1].num;
47 }
48 void get(int now,int x,int y)
49 {
50     if(x==y||s[now].num!=-1)
51     {
52         if(s[now].num>=0)
53             ans[++v]=s[now].num;
54         return ; 
55     }
56     if(s[now].num==-1)
57     {
58         get(now<<1,x,x+y>>1);
59         get((now<<1)+1,(x+y>>1)+1,y);
60     }
61 }
62 int main()
63 {
64     while(scanf("%d",&n)!=EOF)
65     {
66         memset(sum,0,sizeof(sum));
67         v=0;int maxx=0;
68         build(1,0,n*2+1);
69         for(int i=1,k,a,b;i<=n;i++)
70         {
71             scanf("%d%d%d",&k,&a,&b);
72             change(1,k,a-1,b);
73         }
74         get(1,0,n*2+1);
75         for(int i=1;i<=v;i++)
76             if(ans[i]==ans[i+1])
77                 ans[i]=-10;
78         for(int i=1;i<=v;i++)
79             if(ans[i]>=0)
80                 sum[ans[i]]++,maxx=max(ans[i],maxx);
81         for(int i=0;i<=maxx;i++)
82             if(sum[i]!=0)
83                 printf("%d %d
",i,sum[i]);
84         printf("
");
85     }
86 }