线段树练习四

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

解题思路

线段树或暴力
线段树练习题一

AC代码（线段树）

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,l,ans,x,y,h,t;
struct c
{
   
	int x,y,z;
}a[400010];
void insert(int dep,int x,int y)//线段树
{
   
	int mid=(a[dep].x+a[dep].y)/2;
	if(a[dep].x==x&&a[dep].y==y)
	{
   
		a[dep].z++;
		return;
	} 
	else if(y<=mid) insert(2*dep,x,y);
	else if(x>=mid) insert(2*dep+1,x,y);
	else 
	{
   
		insert(2*dep,x,mid);
		insert(2*dep+1,mid,y);
	}
}
void b(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;
		b(i*2);
		b(i*2+1);
	} 
}
int countt(int dep,int l,int r)//输出
{
   
	ans=a[1].z;
	while(a[dep].y-a[dep].x>1)
	{
   
		int mid=(a[dep].y+a[dep].x)/2;
		if(l==a[dep].x&&r==a[dep].y)
			break;
		if(r<=mid)
		{
   
			dep=dep*2;
			ans+=a[dep].z;
		}
		if(l>=mid)
		{
   
			dep=dep*2+1;
			ans+=a[dep].z;
		}
	}
	return ans;
}
int main()
{
   
	scanf("%d%d",&l,&n);
	a[1].x=1,a[1].y=l;
	b(1);
	for(int i=1;i<=n;i++)
	{
   
		scanf("%d%d",&x,&y);
		insert(1,x,y);
	}
	scanf("%d%d",&h,&t);
	printf("%d",countt(1,h,t));
}

AC代码（暴力）

#include<iostream>
using namespace std;
long long n,m,x1,y1,s,x[100005],y[100005];
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	 cin>>x[i]>>y[i];
	cin>>x1>>y1;
	for(int i=1;i<=m;i++)//如果输入的线段包含了x和x+1这两个点就+1
	 if(x1>=x[i]&&y1<=y[i])s++;
	cout<<s;
}

谢谢