B1031 T3 区间
波神说这很板，破防了。
考虑如何维护区间的并。
离线，然后扫描线，并把询问挂到右端点。
从左往右，考虑加入一条线段的影响。
假设现在加入第 \(i\) 条线段，对于 \(j\leq i\)，维护 \(f(j)\) 表示线段 \(j\sim i\) 的并的长度。
某段位置上一次是在 \(lst\) 被覆盖，那么只要询问左端点在 \(lst+1 \sim i\) 这个范围内，当前这段就会产生贡献，其实就是个区间加的操作。
用树状数组 + ODT 维护即可。
那么对于一个询问 \(ql,qr\)，目前就可以算出以 \(qr\) 为右端点，左端点在 \([ql,qr]\) 的答案。
那么如何算出 \(\sum\limits_{ql\leq r\leq qr} \sum\limits_{ql\leq l\leq r} ans(l,r)\) 呢？
你发现这其实是个历史版本和。
由于这题 \(n\leq 8\times 10^5,q\leq 2\times 10^6\)，线段树多半要寄。
其实历史版本和某些情况可以用树状数组维护，还特别方便。
先考虑树状数组如何区间求和区间修改，详见。
假设现在是 \(i\) 时刻（加入第 \(i\) 条线段），当前位置为 \(j\)，这个位置之前有 \(c\) 次修改，第 \(k\) 次修改时间为 \(t_k\)，加的权值是 \(v_k\)（加入第 \(t_k\) 条线段的时候让某个区间加了 \(v_k\)），那么位置 \(j\) 的贡献为：
\(\sum (i-t_k+1)\times v_k\)
即：
\((i+1)\sum v_k-\sum t_k\times v_k\)
分别维护 \(\sum v_k\) 和 \(\sum t_k\times v_k\) 即可。
注意这题对于一个区间 \([l,r]\) 长度是 \(r-l\) 的，直接令所有左端点 +1，区间长度还是按 \(r-l+1\) 算。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e5+5,Q=2e6+5,inf=2e9,p=998244353;
int n,m,L[N],R[N],ans[Q];
struct query{int l,r,id;} q[Q];
struct node{
int l,r,lst;
bool operator<(const node&x)const{
return l==x.l?r<x.r:l<x.l;
}
};
set<node> s;
void inc(int &x,int y) {if((x+=y)>=p) x-=p;}
int qpow(int a,int b) {int r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r;}
struct BIT{
int c1[N],c2[N];
void upd(int x,int v) {for(int V=x*v%p;x<=n;x+=x&-x) inc(c1[x],v),inc(c2[x],V);}
int sum(int x) {int s1=0,s2=0;for(int y=x;y;y^=y&-y) inc(s1,c1[y]),inc(s2,c2[y]);return ((x+1)*s1-s2+p)%p;}
int qsum(int l,int r) {return (sum(r)-sum(l-1)+p)%p;}
}tr1,tr2;
void upd(int l,int i,int v)
{
tr1.upd(l,v),tr1.upd(i+1,-v);
tr2.upd(l,v*i%p),tr2.upd(i+1,-v*i%p);
}
inline int rd()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
signed main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) L[i]=rd()+1,R[i]=rd();
for(int i=1;i<=m;i++) q[i]={rd(),rd(),i};
sort(q+1,q+1+m,[&](auto a,auto b){return a.r<b.r;});
s.insert({-inf,inf,0});s.insert({inf,inf,0});
for(int i=1,j=1;i<=n;i++)
{
int l=L[i],r=R[i];
auto it=s.lower_bound({l,r,0});--it;
auto [_l,_r,lst]=*it;
if(l<=_r)
{
s.erase(it);
s.insert({_l,l-1,lst});
if(r<_r) upd(lst+1,i,r-l+1),s.insert({r+1,_r,lst});
else upd(lst+1,i,_r-l+1);
}
for(it=s.lower_bound({l,r,0});it!=s.end()&&it->l<=r;++it,s.erase(prev(it)))
{
auto [_l,_r,lst]=*it;
if(r<_r) upd(lst+1,i,r-_l+1),s.insert({r+1,_r,lst});
else upd(lst+1,i,_r-_l+1);
}
s.insert({l,r,i});
while(j<=m&&q[j].r==i)
{
auto [l,r,id]=q[j];
int cnt=(r-l+1)*(r-l+2)/2%p;
ans[id]=(i+1)*tr1.qsum(l,r)-tr2.qsum(l,r);
ans[id]=(ans[id]%p+p)%p*qpow(cnt,p-2)%p;
j++;
}
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}