线段树模板-1204-影子的宽度

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int l,r,n,ans;
struct fdfdfd{int l,r,flag,sum;}a[800005];
void build(int x,int left,int right)
{
	a[x].l=left; a[x].r=right;
	if(left==right) return;
	int mid=(left+right)>>1;
	build(x<<1,left,mid);
	build(x<<1|1,mid+1,right);
}
void pushdown(int x)
{
	if(a[x].flag)
	{
		a[x<<1].flag=a[x<<1|1].flag=1;
		a[x<<1].sum=a[x<<1].r-a[x<<1].l+1;
		a[x<<1|1].sum=a[x<<1|1].r-a[x<<1|1].l+1;
		a[x].flag=0; a[x].sum=0;
	}
}
void add(int x,int left,int right)
{
	if(a[x].r<left||a[x].l>right) return;
	if(a[x].l>=left&&a[x].r<=right){a[x].flag=1; a[x].sum=a[x].r-a[x].l+1; return;}
	pushdown(x);
	add(x<<1,left,right);
	add(x<<1|1,left,right);
	if(a[x<<1].flag&&a[x<<1|1].flag){a[x].sum=a[x].r-a[x].l+1; a[x].flag=1;}
}
void ask(int x,int left,int right)
{
	if(a[x].r<left||a[x].l>right) return;
	if(a[x].l>=left&&a[x].r<=right&&a[x].flag){ans+=a[x].sum; return;}
	if(a[x].l==a[x].r) return;
	pushdown(x);
	ask(x<<1,left,right);
	ask(x<<1|1,left,right);
	if(a[x<<1].flag&&a[x<<1|1].flag){a[x].sum=a[x].r-a[x].l+1; a[x].flag=1;}
}
int main()
{
	scanf("%d%d%d",&l,&r,&n);
	build(1,l,r-1);
	for(int i=1;i<=n;++i)
	{
		int f1,f2; scanf("%d%d",&f1,&f2);
		add(1,f1,f2-1);
	}
	ask(1,l,r-1); printf("%d",ans);
	return 0;
}

线段树模板-1204-影子的宽度

原文：https://www.cnblogs.com/wuwendongxi/p/13159444.html