在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。
问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色
Input
第一行两个整数n，m，表示数轴从0到n，操作数为m
接下来m行，每行三个整数op，a，b，op=0时表示将[a,b]上的颜色擦去，op=1时表示在线段[a,b]上涂上颜色
n,m<=100000
Output
输出一个整数，表示有多少条单位线段[k,k+1]被涂上了颜色
Sample Input
10 10
1 0 8
0 2 8
1 0 1
1 2 10
1 9 10
0 2 7
0 3 6
1 0 2
0 2 7
0 2 7
Sample Output
5
Sol:
简单的线段树入门题
对于每条线段可能有三种状态
1:这条线段color不统一
2:为空白的color
3:染色了
于是在染色操作时
如果本线段已染成规定的color，则直接退出
如果要操作的区间，不在当前区间，也退出
否则要进行染色
染色前先将当前线段的标记下传，然后进行染色
染色时可能一次完成，即要染色的区间在当前区间中
也可以要递归分段完成
染色完成后，检查下子树的color是否一样，完成对本段color的一个总结
在统计color时
如果本段的color是统一的，直接返回结果
如果本段没有染色过，或者到了叶子点时，也返回
否则递归完成对子树的统计
#include<cstdio>
using namespace std;
int color[400001],ans;
void colors(int num,int l,int r,int x,int y,int c)
{
if(color[num]==c)return; //如果这一段已染成c这种color了
if(y<=l||x>=r)return; //如果要操作的区间，不在目前的区间中
if (color[num]!=0) //标记下传
{
color[num*2]=color[num];
color[num*2+1]=color[num];
}
if(x<=l&&r<=y)
{
color[num]=c;
//color[num*2]=c;
//color[num*2+1]=c;
return;
}
int mid=(l+r)/2;
colors(num*2,l,mid,x,y,c);
colors(num*2+1,mid,r,x,y,c);
if(color[num*2]==color[num*2+1]) //如果子树的color是一样的，则当前段的color是一致的
color[num]=color[num*2];
else
color[num]=0;
return;
}
void find(int num,int l,int r)
{
if(color[num]==2) //如果这一段已染了色了
{
ans=ans+r-l;
return;
}
if(color[num]==1||l+1==r) //这一段没有染色，或已到了叶子点时
return;
int mid=(l+r)/2;
find(num*2,l,mid);
find(num*2+1,mid,r);
return;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==1)
colors(1,1,n+1,x+1,y+1,2);
else
colors(1,1,n+1,x+1,y+1,1);
}
ans=0;
find(1,1,n+1);
printf("%d",ans);
return 0;
}
线段树之Light
一天，Mpq的物理老师找到Mpq说：“你学过光现象的一些知识了，我知道你是学信息学的，现在我结合物理来问你
一个信息学的问题(我晕，物理老师也懂信息学)。” Mpq很爽快的答应了，他认为物理老师的问题不会很难的。王
老师接着说：“你知道光在同一均匀物质中是沿直线传播的。我现在有一些箱子，放在一堵长N米的墙前面，然后
我向它们的正面射光线，那么在墙上就会有箱子的影子，问最后所有箱子影子的总长度是多少。”Mpq听了问题之
后就觉得这是一个非常简单的题，就用最一般的方法就可以解决了，所以他暗暗的笑。王老师看到他得意的样子，
笑着说：“你先别得意，我还没说出墙的范围和箱子的长度范围呢，下面我说说他们的范围，你可别吓个半死啊！
。”
Input
第一行有两个正数N(n<=10000000)表示抢的长度。M(m<=1000000)，表示有多少个箱子。
然后下面有M行，每行两个数x,y(x<y<=n);分别表示箱子的起始位置和终止位置。
比如一个箱子的起始位置是1,终止位置是5,那么这个箱子的长度是5-1=4.
Output
输出一个整数，表示箱子影子的总长度。
Sample Input
6 4
1 2
3 5
4 6
5 6
Sample Output
4
#include<cstdio>
using namespace std;
int n,m,ans;
bool shadow[40000010];
void insert(int num,int l,int r,int x,int y)
{
if(shadow[num])return;
if(l>=x&&r<=y)
{
shadow[num]=1;
return;
}
if(r<=x||l>=y)return;
int mid=(l+r)/2;
insert(num*2,l,mid,x,y);
insert(num*2+1,mid,r,x,y);
shadow[num]=shadow[num*2]&&shadow[num*2+1];
return;
}
void find(int num,int l,int r)
{
if(shadow[num])
{
ans=ans+r-l;
return;
}
if(l+1==r)return;
int mid=(l+r)/2;
find(num*2,l,mid);
find(num*2+1,mid,r);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
insert(1,1,n,x,y);
}
ans=0;
find(1,1,n);
printf("%d",ans);
return 0;
}
Zju1610 Count the Colors
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 93 Solved: 43
[Submit][Status][Web Board][Edit] [TestData]
Description
画一些颜色段在一行上，一些较早的颜色就会被后来的颜色覆盖了。
你的任务就是要数出你随后能看到的不同颜色的段的数目。
Input
每组测试数据第一行只有一个整数n, 1 <= n <= 8000,等于填色的次数
接下来的n行每行有三个非负整数，他们之间用一个空格分开。
x1 x2 c
x1和x2表示填色段最左边的点和最右边的点， c表示填进的颜色。
所有数字都是在[0..8000]这个范围里的整数。
输入有多组测试数据，最后以文件结束符为结束。
Output
输出的每一行都是最后能看到的颜色的数字，还有这种颜色的段数。
如果这种颜色最后不能见到，就不要打印出来。
每组数据后面跟一个空行。
Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1
Sample Output
1 1
2 1
3 1
1 1
0 2
1 1
//tree的标记：-2代表这一段不是统一的color,-1代表没有染色
//大于0的数字，代表这一段已被染色
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=8e3;
int tree[N*5+100],kind[N*5+100];
int cnt;
int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
void updata(int p)
{
if (tree[p]>=0)
{
tree[p*2]=tree[p];
tree[p*2+1]=tree[p];
}
tree[p]=-2;
}
void change(int p,int l,int r,int x,int y,int t)
{
if (tree[p]==t) return;
if (x<=l&&r<=y)
{
tree[p]=t;
return;
}
updata(p);
int mid=(l+r)>>1;
if (x<mid) change(p*2,l,mid,x,y,t);
if (y>mid) change(p*2+1,mid,r,x,y,t);
}
void get(int p)
{
if (tree[p]>=0) //这一段已被染色
{
if (tree[p]!=cnt) //如果不等于从前的值
{
kind[tree[p]]++;
cnt=tree[p];
}
return;
}
if (tree[p]==-1) //这一段没有被染色
{
cnt=-1;
return;
}
get(p*2);
get(p*2+1);
}
int main()
{
int n;
while (~scanf("%d",&n))
{
memset(tree,255,sizeof(tree)); //全打上-1的标记
memset(kind,0,sizeof(kind));
for (int i=1;i<=n;i++)
{
int x=read()+1,y=read()+1,t=read();
change(1,1,N+1,x,y,t);
}
cnt=-1;
get(1);
for (int i=1;i<=N+1;i++)
if (kind[i])
printf("%d %d
",i,kind[i]);
printf("
");
}
return 0;
}