ZOJ-1610 线段树+两种查询方法（弥补我线段树区间填充的短板）

短命女 2021-10-29 12:40 196阅读 0赞

# 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; }

转载于:https://www.cnblogs.com/alking1001/p/11326239.html