本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-17 14:52:38

校门外的树扩展

离散化学习：oiwiki

方法一：离散化后用校门外的树方法

#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int x[N<<1];
int a[N],b[N],c[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		x[2*i-1]=a[i];
		x[2*i]=b[i];
	}
	sort(x+1,x+1+2*n);
	int m=unique(x+1,x+2*n+1)-x-1;
	for(int i=1;i<=n;i++)
	{
		int L=lower_bound(x+1,x+m+1,a[i])-x;
		int R=lower_bound(x+1,x+m+1,b[i])-x;
		for(int j=L;j<R;j++)c[j]+=1;

	}
	int h=0,t=0,ans=0;
	for(int i=1;i<=m;i++)
	{
		if(!c[i-1]&&c[i])ans+=1;
		if(c[i]&&c[i-1])  ans+=x[i]-x[i-1];
		else if(c[i-1]&&!c[i]) ans+=x[i]-x[i-1]-1;
	}
	cout<<ans;

	return 0;
 }

方法二 ：利用前缀和，区间修改，再求前缀和

#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int x[N<<1];
int a[N],b[N],c[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		x[2*i-1]=a[i];
		x[2*i]=b[i];
	}
	sort(x+1,x+1+2*n);
	int m=unique(x+1,x+2*n+1)-x-1;
	for(int i=1;i<=n;i++)
	{
		int L=lower_bound(x+1,x+m+1,a[i])-x;
		int R=lower_bound(x+1,x+m+1,b[i])-x;
	\/\/	for(int j=L;j<R;j++)c[j]+=1;
		 c[L]++,c[R]--;

	}

	int h=0,t=0,ans=0;
	for(int i=1;i<=m;i++)
	{   c[i]+=c[i-1];
		if(!c[i-1]&&c[i])ans+=1;
		if(c[i]&&c[i-1])  ans+=x[i]-x[i-1];
		else if(c[i-1]&&!c[i]) ans+=x[i]-x[i-1]-1;
	}

	cout<<ans;

	return 0;
 }

最后的处理还可以只记录起点和终点

int h=0,t=0,ans=0;
	for(int i=1;i<=m;i++)
	{   c[i]+=c[i-1];
		if(!c[i-1]&&c[i])h=x[i];

		else if(c[i-1]&&!c[i]) t=x[i],ans+=t-h;
	}