C++(clang++11) 解法, 执行用时: 215ms, 内存消耗: 18948K, 提交时间: 2021-04-11 14:11:57

#include<cstdio>
#include<vector>
#include<set>
#define lowbit(x) x&(-x)
using namespace std;
typedef pair<int,int> P;
const int maxn=2e5+5;
int n,m;
int L[maxn],R[maxn],tr[maxn],ans[maxn];
vector<P>q[maxn];
set<P>s;
void add(int x,int k){
	while(x<=n){
		tr[x]+=k;
		x+=lowbit(x);
	}
}
void upd(int l,int r,int k){
	add(l,k);add(r+1,-k);
}
int query(int x){
	int res=0;
	while(x){
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&L[i],&R[i]);
	for(int i=1;i<=m;++i){
		int x,y;scanf("%d%d",&x,&y);
		q[y].push_back((P){x,i});
	}
	s.insert((P){1e9+1,0});
	for(int i=1;i<=n;++i){
		int l=L[i],r=R[i],fl=-1,l1=l-1;
		auto it=s.lower_bound((P){l-1,0});
		while(1){
			int x=it->first,y=it->second;
			int len=min(x,r)-l1;
			if(fl<0)fl=y;
			upd(y+1,i,len);
			if(x<=r){
				l1=x;
				auto it1=it;++it;s.erase(it1);
			}else break;
		}
		if(l>1)s.insert((P){l-1,fl});
		s.insert((P){r,i});
		for(int j=0;j<q[i].size();++j)
			ans[q[i][j].second]=query(q[i][j].first);
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	return 0;
}