欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【ssl2647】【线段树练习题4】【线段树变式】

程序员文章站 2022-05-11 18:09:01
...

Description

在平面内有一条长度为n的线段(不计入答案),可以对进行以下2种操作:
1、把从x到y的再加一条线段
2、查询从x到x+1有多少条线段

Input

第一行输入n,m
第2~m+1行,每行2个数x,y,表示从x到y再加一条线段
最后一行输入2个数,为x和x+1,查询x到x+1的线段数目

Output

输出x到x+1的线段数目

Sample Input

7 2
2 5
3 6
4 5

Sample Output

2

Hint

【数据规模】
100%满足1≤n≤100000,1≤x≤y≤n

分析

为线段树每个节点增加一个count域。表示所对应区间上重叠的线段数。

思考线段树的构造方法:当某线段能够完整覆盖某个结点所对应的区间时,则不再二分。因此要统计某个单位区间上重叠的线段总数,必须把从叶结点到根结点路径上所有结点的count域累加。
a[i].z表示当前节点表示的区间里线段的数量。

当前节点表示的区间里线段的数量+这个节点的父节点表示的区间里线段的数量+这个节点的父节点的父节点表示的区间里线段的数量+……+根节点表示的区间里线段的数量=这个节点表示的区间有多少条线段。

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int n,l,ans,x,y,h,t;
struct node
{
	int x,y,z;
}a[400001];
void insert(int k,int x,int y)
{
	int mid=(a[k].x+a[k].y)/2;
	if(a[k].x==x&&a[k].y==y)
	{
		a[k].z++;
		return;
	}
	else if(y<=mid)
	{
		insert(2*k,x,y);
	}
	else if(x>=mid)
	{
		insert(2*k+1,x,y);
	}
	else
	{
		insert(2*k,x,mid);
		insert(2*k+1,mid,y);
	}
}
void build(int i)//建立线段树的另一种方法 
{
	if(a[i].y-a[i].x>1)
	{
		int mid=(a[i].y+a[i].x)/2;
		a[i*2].x=a[i].x;
		a[i*2].y=mid;
		a[i*2+1].x=mid;
		a[i*2+1].y=a[i].y;
		build(i*2);
		build(i*2+1);
	}
}
int cnt(int k,int l,int r)
{
	ans=a[1].z;
	while(a[k].y-a[k].x>1)
	{
		int mid=(a[k].y+a[k].x)/2;
		if(l==a[k].x&&r==a[k].y)
		{
			break;
		}
		if(r<=mid)
		{
			k*=2;
			ans+=a[k].z;
		}
		if(l>=mid)
		{
			k=k*2+1;
			ans+=a[k].z;
		}
	}
	return ans;
}
int main()
{
	cin>>l>>n;
	a[1].x=1;
	a[1].y=l;
	build(1);
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		insert(1,x,y);
	}
	cin>>h>>t;
	cout<<cnt(1,h,t);
	return 0;
}

相关标签: 线段树 线段树