PTZ summer 2021 Day 5 D Interval

记 \([l,r]\times [a,b]\) 表示区间所有的 \((x,y),x \in [l,r],y \in [a,b]\)

先考虑离散化，对每一个极小区间 \((x,y)\) 分别求解，假设有 \(n\) 给定区间包含它

若 \(n=1\)，那么可以使 \([1,i_1]\times [i_1,n]\) 加上 \(1\)

如果 \(n =2\)，如果按照 \(n=1\) 的做法会重复计算，那么可以使 \([1,i_1]\times [i_2,n]\) 减去 \(1\)，那么 \(n>2\) 同理，可以看作有 \(n\) 个点的链，那么点数减去边数恰好为 \(1\)

可以发现一些相邻的极小区间可以合并起来，那么可以直接拿给定的区间进行操作，使用珂朵莉树维护，具体来说编号从小到大插入区间，当前应该插入 \(i\)，且 \(i\) 覆盖的区间三元组为 \((l_j,r_j,id_j)\)（有些给定区间不会被完全覆盖），使 \([1,id_j]\times [i,n]\) 减去 \(r_j-l_j+1\)，最后 \([1,i]\times [i,n]\) 加上区间长度即可，可以发现所有区间的加入和删除总次数为 \(\texttt{O}(n)\) 的

而 \([l,r]\times [a,b]\) 可以看作矩阵，那么扫描线加历史和维护矩阵加矩阵求和即可

具体细节看代码

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
struct node{
    int l,r,v;
    node(int l=0,int r=0,int v=0):l(l),r(r),v(v){}
    bool operator<(const node &k)const{return l<k.l;}
};
struct his{
    long long h,v,a,b,c;
    his(long long h=0,long long v=0,long long a=0,long long b=0,long long c=0):h(h),v(v),a(a),b(b),c(c){}
}t[800001];
set <node> s;
int n,m,x,y;
long long ans[200001],w[200001];
vector <node> G[200001];
const int mod=998244353;
long long power(long long a){
    long long res=1;
    for(int b=mod-2;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;
    return res;
}
set <node> ::iterator split(int pos){
    auto it=s.lower_bound(node(pos,0));
    if(it!=s.end()&&(*it).l==pos) return it;
    int l=(*--it).l,r=(*it).r,v=(*it).v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;
}
void upd(int x,long long a,long long b,long long c,long long l){
    t[x].h=(t[x].h+t[x].v*a+l*b)%mod;
    t[x].v=(t[x].v+l*c)%mod;
    t[x].a=(t[x].a+a)%mod;
    t[x].b=(t[x].b+t[x].c*a+b)%mod;
    t[x].c=(t[x].c+c)%mod;
}
void push_down(int rt,int l,int r){
    upd(rt*2,t[rt].a,t[rt].b,t[rt].c,mid-l+1);
    upd(rt*2+1,t[rt].a,t[rt].b,t[rt].c,r-mid);
    t[rt].a=t[rt].b=t[rt].c=0;
}
void update(int rt,int l,int r,int L,int R,long long a,long long b,long long c){
    if(L<=l&&r<=R) return (void)(upd(rt,a,b,c,r-l+1));
    push_down(rt,l,r);
    if(L<=mid) update(rt*2,l,mid,L,R,a,b,c);
    if(R>mid) update(rt*2+1,mid+1,r,L,R,a,b,c);
    t[rt].h=(t[rt*2].h+t[rt*2+1].h)%mod;
    t[rt].v=(t[rt*2].v+t[rt*2+1].v)%mod;
}
long long query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return t[rt].h;
    push_down(rt,l,r);
    return ((L<=mid?query(rt*2,l,mid,L,R):0)+(R>mid?query(rt*2+1,mid+1,r,L,R):0))%mod;
}
int main(){
	scanf("%d%d",&n,&m),s.insert(node(0,1e8,0));
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        auto r=split(y),l=split(x);
        for(auto j=l;j!=r;j++) if((*j).v!=0) G[i].push_back(node((*j).v,mod-((*j).r-(*j).l+1),0));
        s.erase(l,r);
        s.insert(node(x,y-1,i));
        G[i].push_back(node(i,y-x,0));
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        w[i]=power(1ll*(y-x+1)*(y-x+2)/2%mod);
        G[y].push_back(node(x,y,i));
        G[x-1].push_back(node(x,y,-i));
    }
    for(int i=1;i<=n;i++){
        for(auto j:G[i]) if(!j.v) update(1,1,n,1,j.l,0,0,j.r);
        update(1,1,n,1,n,1,0,0);
        for(auto j:G[i]){
            if(j.v>0) ans[j.v]=(ans[j.v]+query(1,1,n,j.l,j.r))%mod;
            if(j.v<0) ans[-j.v]=(ans[-j.v]-query(1,1,n,j.l,j.r)+mod)%mod;
        }
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]*w[i]%mod);
	return 0;
}