记录编号	613923	评测结果	AAAAAAAAAA
题目名称	4372.区间	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	9.801 s
提交时间	2026-04-02 15:41:03	内存使用	28.08 MiB

#include <bits/stdc++.h>
using namespace std;
const int mod=666623333;
const int N=5e5+10;
typedef long long ll;
ll ksm(ll a,ll b){
	ll ans=1;
	a%=mod;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int n,m,b[N<<1],t;
ll w[N<<1],ans[N],ST;
struct node{int l,r,id;}q[N];
struct cht{
	int l,r,v;
	bool operator < (const cht &b)const{
		return l<b.l;
	}
};
set<cht>s;
typedef set<cht>::iterator iter;
struct sgt{
	ll sum[N<<2],tag[N<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	void pushup(int p){
		sum[p]=(sum[ls]+sum[rs])%mod;
	}
	void pushdown(int p,int l,int r){
		if(!tag[p])return;int m=(l+r)>>1;
		(sum[ls]+=tag[p]*(m-l+1)%mod)%=mod;
		(sum[rs]+=tag[p]*(r-m)%mod)%=mod;
		(tag[ls]+=tag[p])%=mod;
		(tag[rs]+=tag[p])%=mod;
		tag[p]=0;return;
	}
	void add(int p,int l,int r,int L,int R,ll v){
		if(L<=l&&r<=R){
			(sum[p]+=(r-l+1)*v%mod)%=mod;
			(tag[p]+=v)%mod;
		}else{
			pushdown(p,l,r);int mid=(l+r)>>1;
			if(L<=mid)add(ls,l,mid,L,R,v);
			if(R>mid)add(rs,mid+1,r,L,R,v);
			pushup(p);
		}
	}
	ll ask(int p,int l,int r,int L,int R){
		if(L<=l&&r<=R)return sum[p];
		int mid=(l+r)>>1;ll cnt=0;pushdown(p,l,r);
		if(L<=mid)cnt+=ask(ls,l,mid,L,R),cnt%=mod;
		if(R>mid)cnt+=ask(rs,mid+1,r,L,R),cnt%=mod;
		return cnt;
	}
}tra,trc;
void upd(int l,int r,int v){
	v%=mod;
	tra.add(1,1,n,l,r,v);
	trc.add(1,1,n,l,r,-v*ST%mod);
	return;
}
ll ask(int l,int r){
	ll ans=ST*tra.ask(1,1,n,l,r)%mod;
	ans+=trc.ask(1,1,n,l,r);
	return (ans%mod+mod)%mod;
}
iter split(int x){
	iter it=s.lower_bound(cht{x,0,0});
	if(it!=s.end()&&it->l==x)return it;it--;
	int L=it->l,R=it->r,v=it->v;
	s.erase(it),s.insert(cht{L,x-1,v});
	return s.insert(cht{x,R,v}).first;
}
void assign(int l,int r,int i){
	iter itr=split(r+1),itl=split(l);
	for(iter it=itl;it!=itr;it++){
		ll val=w[it->r]-w[it->l-1];
		upd(it->v+1,i,val);
	}
	s.erase(itl,itr);
	s.insert(cht{l,r,i});
	ST++;
}
int l[N],r[N];
int main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d %d",l+i,r+i);
		b[++t]=l[i],b[++t]=r[i];
	}
	sort(b+1,b+1+t);
	t=unique(b+1,b+1+t)-(b+1);
	for(int i=1;i<t;i++)w[i]=b[i+1]-b[i]+w[i-1];
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(b+1,b+1+t,l[i])-b;
		r[i]=lower_bound(b+1,b+1+t,r[i])-b-1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	s.insert(cht{1,t-1,0});
	sort(q+1,q+1+m,[&](node &u,node &v){
		return u.r<v.r;
	});
	for(int i=1,j=1;i<=n;i++){
		assign(l[i],r[i],i);
		while(j<=m&&q[j].r<=i){
			ans[q[j].id]=ask(q[j].l,q[j].r);
			ll L=q[j].r-q[j].l+1;
			ll inv=ksm((L+1)*L/2,mod-2);
			(ans[q[j].id]*=inv)%=mod;
			j++;
		}
	}
	for(int i=1;i<=m;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}