ZOJ-1610 线段树+两种查询方法（弥补我线段树区间填充的短板）
题意
题意：给一个n，代表n次操作，接下来每次操作表示把[l，r]区间的线段涂成k的颜色其中,l,r,k的范围都是0到8000
这题比较坑的是不能拿n建树，不然就会segmentation fault，我也是错了好多遍看的博客才知道，必须拿8000建树，也就是树是固定的。
解题思路一
线段树来维护点的颜色
单点查询，从左到右一个一个点的查询，这个有点暴力，但是因为每次查询都是\(logn\)也不是很大，跑了一下是60ms
代码实现一
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=8e3+7;
struct node{
int l, r;
int lazy;
}a[maxn<<2];
int ans[8007];
void down(int rt)
{
int l=rt<<1, r=rt<<1|1;
a[l].lazy=a[rt].lazy;
a[r].lazy=a[rt].lazy;
a[rt].lazy=-1;
}
void build(int rt, int l, int r)
{
a[rt].l=l;
a[rt].r=r;
a[rt].lazy=-1; //表示当前点的范围颜色不统一
if(l==r) return ;
int mid=(l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
void update(int rt, int L, int R, int x)
{
if(L<=a[rt].l && a[rt].r<=R)
{
a[rt].lazy=x;
return ;
}
int mid=(a[rt].l+a[rt].r)>>1;
if(a[rt].lazy!=-1)
down(rt);
if(L<=mid) update(rt<<1, L, R, x);
if(R>mid) update(rt<<1|1, L, R, x);
}
int query(int rt, int x) //单点查询
{
if(a[rt].l==a[rt].r)
{
return a[rt].lazy;
}
if(a[rt].lazy!=-1) //记得一定要down一下，因为是单点查询，如果不down，这个点可能还是上一次的状态
down(rt);
int mid=(a[rt].l+a[rt].r)>>1;
if(x<=mid) return query(rt<<1, x);
else return query(rt<<1|1, x);
}
int main()
{
int n, a, b, c;
while(scanf("%d", &n)!=EOF)
{
build(1, 1, 8000);
memset(ans, 0, sizeof(ans));
for(int i=1; i<=n; i++)
{
scanf("%d%d%d", &a, &b, &c);
update(1, a+1, b, c);
}
int p1, p2;
p1=query(1, 1);
if(p1!=-2 && p1!=-1) ans[p1]++;
for(int i=2; i<=8000; i++)
{
p2=query(1, i);
if(p1!=p2){
ans[p2]++;
}
p1=p2;
}
for(int i=0; i<=8000; i++)
{
if(ans[i]!=0)
{
printf("%d %d\n", i, ans[i]);
}
}
printf("\n");
}
return 0;
}
解题思路二
类似区间查询，如果某一个点的lazy标记不是-1，那个这个区间就都是一种颜色，就不用往下递归了
如果lazy是-2，那个这个区域没有颜色，相当于中间隔开了一块区域。
查询是从左到右进行的，pre表示先前点左边的颜色，需要判断当前点与左边的点的颜色是否相同。
这个代码跑的是50ms。
代码实现二
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=8e3+7;
struct node{
int l, r;
int lazy;
}a[maxn<<2];
int ans[8007];
int pre; //pre表示先前块的颜色
void down(int rt)
{
int l=rt<<1, r=rt<<1|1;
a[l].lazy=a[rt].lazy;
a[r].lazy=a[rt].lazy;
a[rt].lazy=-1;
}
void build(int rt, int l, int r)
{
a[rt].l=l;
a[rt].r=r;
a[rt].lazy=-2; //表示没有颜色
if(l==r) return ;
int mid=(l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
void update(int rt, int L, int R, int x)
{
if(L<=a[rt].l && a[rt].r<=R)
{
a[rt].lazy=x;
return ;
}
int mid=(a[rt].l+a[rt].r)>>1;
if(a[rt].lazy!=-1 && a[rt].lazy!=-2)
down(rt);
if(L<=mid) update(rt<<1, L, R, x);
if(R>mid) update(rt<<1|1, L, R, x);
if(a[rt<<1].lazy==a[rt<<1|1].lazy)//相当于up 看下属左右两点的颜色是否相同
{
a[rt].lazy=a[rt<<1].lazy; //相同的话，这个点就可以代表下面的两个点
}
else a[rt].lazy=-1;//否则-1表示下属两个点的颜色不统一，需要以后特殊标记
}
void query(int rt)//先当于区间查询，从左到右
{
if(a[rt].lazy==-2) //说明这个点控制的区域没有刷颜色，那么它右边的点也可以和左边的点有相同颜色
{
pre=-1;//这个标记-1
return ; //结束
}
if(a[rt].lazy!=-1)
{
if(a[rt].lazy!=pre)
{
ans[a[rt].lazy]++;
pre=a[rt].lazy;
}
return ;
}
query(rt<<1);
query(rt<<1|1);
}
int main()
{
int n, a, b, c;
while(scanf("%d", &n)!=EOF)
{
build(1, 1, 8000);
memset(ans, 0, sizeof(ans));
for(int i=1; i<=n; i++)
{
scanf("%d%d%d", &a, &b, &c);
update(1, a+1, b, c);
}
pre=-2;
query(1);
for(int i=0; i<=8000; i++)
{
if(ans[i]!=0)
{
printf("%d %d\n", i, ans[i]);
}
}
printf("\n");
}
return 0;
}