线段树 2018.5.9

本文主要是介绍线段树 2018.5.9，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

虽然这不是我第一次做线段树，但是……

SSL 2644 练习题一

题目

桌子上零散地放着若干个盒子，桌子的后方是一堵墙。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少。

分析

这道题首先会想到离散，但是$n\le 10^5$无能为力，所以使用线段树。

代码

#include <cstdio>
#include <cctype>
using namespace std; 
struct treenode{bool cover;}tree[300001]; int m,n;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void rn(int &a,int &b){a=in(); b=in();}
void build(int k,int l,int r){if (r-l>1) build(k<<1,l,(l+r)>>1),build((k<<1)+1,(l+r)>>1,r);}
void insert(int k,int l,int r,int x,int y){if (!tree[k].cover){if (l==x&&r==y) tree[k].cover=1;else{int mid=(l+r)>>1;if (y<=mid) insert(k<<1,l,mid,x,y);else if (x>=mid) insert((k<<1)+1,mid,r,x,y);else insert(k<<1,l,mid,x,mid),insert((k<<1)+1,mid,r,mid,y);}}
}
int count(int k,int l,int r){if (tree[k].cover==1) return r-l;//找到了else if (r-l==1) return 0;//找不到else return count(k<<1,l,(l+r)>>1)+count((k<<1)+1,(l+r)>>1,r);
}
int main(){rn(m,n); build(1,1,m); int x,y;for (int i=1;i<=n;i++) rn(x,y),insert(1,1,m,x,y);return !printf("%d",count(1,1,m));
}

SSL 2645 练习题二

题目

桌子上零散地放着若干个不同颜色的盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子。

分析

这道题可以假设颜色为i（i=0表示没有颜色），然后插入后统计时用flag就好了。

代码

#include <cstdio>
#include <cctype>
using namespace std; 
struct treenode{int cover;}tree[300001]; int m,n,ans; bool flag[100001];
inline int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
inline void rn(int &a,int &b){a=in(); b=in();}
void build(int k,int l,int r){tree[k].cover=-1; if (r-l>1) build(k<<1,l,(l+r)>>1),build((k<<1)+1,(l+r)>>1,r);}
void insert(int k,int l,int r,int x,int y,int i){if (tree[k].cover==i) return;if (l==x&&r==y) {tree[k].cover=i; return;}if (tree[k].cover>=0){tree[k<<1].cover=tree[(k<<1)+1].cover=tree[k].cover;tree[k].cover=-1;}int mid=(l+r)>>1;if (y<=mid) insert(k<<1,l,mid,x,y,i);else if (x>=mid) insert((k<<1)+1,mid,r,x,y,i);else insert(k<<1,l,mid,x,mid,i),insert((k<<1)+1,mid,r,mid,y,i);
}
void count(int k,int l,int r){if (tree[k].cover>=0) ans+=(!flag[tree[k].cover]),flag[tree[k].cover]=1;else if (r-l>1) count(k<<1,l,(l+r)>>1),count((k<<1)+1,(l+r)>>1,r);
}
int main(){rn(m,n); build(1,1,m); int x,y;for (int i=1;i<=n;i++) rn(x,y),insert(1,1,m,x,y,i);count(1,1,m); return !printf("%d",ans);
}

SSL 2646 练习题三

题目

给定一条长度为m的线段，有n个操作，每个操作有3个数字x,y,z表示把区间[x,y]染成颜色z，询问染完色之后，这条长度为m的线段一共有几种颜色。规定：线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成多少段。

分析

这道题关键是要找到颜色，所以就用lec和ric来找出颜色，注意处理根节点

##代码

#include <cstdio>
#include <cctype>
using namespace std; 
struct treenode{int cover;}tree[300001]; int m,n,ans,lec,ric; 
inline int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
inline void rn(int &a,int &b){a=in(); b=in();}
void build(int k,int l,int r){if (r-l>1) build(k<<1,l,(l+r)>>1),build((k<<1)+1,(l+r)>>1,r);}
void insert(int k,int l,int r,int x,int y,int i){if (tree[k].cover==i) return;//找过了if (l==x&&r==y) {tree[k].cover=i; return;}//找到了if (tree[k].cover>=0){tree[k<<1].cover=tree[(k<<1)+1].cover=tree[k].cover;tree[k].cover=-1;//标记根节点}int mid=(l+r)>>1;if (y<=mid) insert(k<<1,l,mid,x,y,i);else if (x>=mid) insert((k<<1)+1,mid,r,x,y,i);else insert(k<<1,l,mid,x,mid,i),insert((k<<1)+1,mid,r,mid,y,i);
}
int count(int k,int l,int r,int &lec,int &ric){int tl=lec,tr=ric;if (tree[k].cover>=0) {lec=ric=tree[k].cover;return 1;}//返回左区间和右区间else if (r-l>1){int ans=count(k<<1,l,(l+r)>>1,lec,tl)+count((k<<1)+1,(l+r)>>1,r,tr,ric);return ans-(tl==tr&&tl>0);//处理重复}
}
int main(){rn(n,m); build(1,1,m); int x,y;for (int i=1;i<=n;i++) rn(x,y),insert(1,1,m,x,y,in());return !printf("%d",count(1,1,m,lec,ric));
}

SSL 2647 练习题四

题目

在平面内有一条长度为n的线段（也算一条线段），可以对进行以下2种操作：
1 x y 把从x到y的再加一条线段
2 x y 查询从x到y有多少条线段

分析

这道题比较容易，插入后查找时找到那个点，然后往父节点求和就可以了。

代码

#include <cstdio>
#include <cctype>
using namespace std; 
struct treenode{int w;}tree[300001]; int h,m,n;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void rn(int &a,int &b){a=in(); b=in();}
void build(int k,int l,int r){if (r-l>1) build(k<<1,l,(l+r)>>1),build((k<<1)+1,(l+r)>>1,r);}
void insert(int k,int l,int r,int x,int y){if (l==x&&r==y) tree[k].w++;else if (r-l>1){int mid=(l+r)>>1;if (y<=mid) insert(k<<1,l,mid,x,y);else if (x>=mid) insert((k<<1)+1,mid,r,x,y);else insert(k<<1,l,mid,x,mid),insert((k<<1)+1,mid,r,mid,y);}
}
void findqj(int k,int l,int r,int x,int y){if (l==x&&r==y) h=k;else if (r-l>1){int mid=(l+r)>>1;if (y<=mid) findqj(k<<1,l,mid,x,y);else if (x>=mid) findqj((k<<1)+1,mid,r,x,y);else findqj(k<<1,l,mid,x,mid),findqj((k<<1)+1,mid,r,mid,y);}
}
int count(int x){int ans=0;while (x){ans+=tree[x].w;x/=2;}return ans;
}
int main(){rn(m,n); build(1,1,m); int x,y;for (int i=1;i<=n;i++) rn(x,y),insert(1,1,m,x,y);rn(x,y); findqj(1,1,m,x,y);return !printf("%d",count(h));
}

SSL 2648 练习题五

题目

一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。

分析&&代码

#include <cstdio>
#include <cctype>
using namespace std;
struct node{int w;}tree[300001]; int n,m,ans;
inline int in(){int ans=0,f=1; char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') f=-f,c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans*f;
}
void update(int l,int r,int x,int y,int k){if (l==x&&r==x) {tree[k].w+=y; return;}int mid=(l+r)>>1;if (x<=mid) update(l,mid,x,y,2*k); else update(mid+1,r,x,y,2*k+1);tree[k].w=tree[2*k].w+tree[2*k+1].w;
}
void find(int l,int r,int x,int y,int k){if (x==l&&y==r) {ans+=tree[k].w;return;}int mid=(l+r)>>1;if (y<=mid) find(l,mid,x,y,2*k);else if (x>mid) find(mid+1,r,x,y,2*k+1);else find(l,mid,x,mid,2*k),find(mid+1,r,mid+1,y,2*k+1);return;
}
void in1(int &x,int &y){x=in();y=in();}
int main(){in1(n,m);while (m--){char q=getchar(); int x,y;ans=0;in1(x,y); if (q=='M') update(1,n,x,y,1);else find(1,n,x,y,1),printf("%d\n",ans);}return 0;
} 

这篇关于线段树 2018.5.9的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！