P9722 [EC Final 2022] Rectangle

yyyyxh · 2024-08-07 20:09:44 · 题解

数据结构好题，写死我了 QwQ……

这个题是可以用 segbeats 做到 O(n\log n) 的。

先离散化。我们只用考虑三条竖线和两竖一横的情况。三条竖线线性 DP 一下就行了。

两竖一横的情况可以考虑枚举更靠后的那条竖线，首先这条竖线后面还没有被覆盖的区间就只能用横线覆盖了，于是所有后面的区间另一维取个交，对于横线就是一个区间的限制。

从前往后扫更靠后的那条竖线，问题变成了每次加入一些矩形然后询问一条竖线一条横线的这种问题的答案。

开一颗线段树，维护对于每一种横线的位置竖线的区间限制。这样修改就变成了对于一个前缀/后缀与一个区间取交，求区间长度和。经典 segbeats 问题，由于没有区间加减所以复杂度是 O(n\log n)。

但是还有几个巨大的细节，首先你要保证新取的竖线在你枚举的竖线之前，这个限制不能被描述为区间取交因为这个限制不断在放宽。但是你发现只有没有被任何矩形限制也就是 [1,10^9] 这种区间才会被这个限制影响，分讨一下没被影响的区间就行了。

然后还有注意处理区间交为空的情况，此时需要把这个位置从线段树中剔除，注意这个操作对于 segbeats 存储的信息的影响！我就是这里调了一亿年！

由于 segbeats 的优秀常数跑得比其它单 \log 解法快点。

#include <cstdio>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
typedef long long ll;
typedef __int128 lll;
int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=x*10+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=100003,M=200003;
const int L=1e9,P=998244353;
const int T=M<<2;
inline void chmn(int &x,int v){if(x>v) x=v;}
inline void chmx(int &x,int v){if(x<v) x=v;}
inline void inc(int &x,int v){if((x+=v)>=P) x-=P;}
inline void dec(int &x,int v){if((x-=v)<0) x+=P;}
int n,res;
int bx[M],nx;
int by[M],ny;
int lx[N],rx[N];
int ly[N],ry[N];
int mn[M],s[M][4];
inline int coe(int i,int t){
    int x=bx[i]-bx[i-1];
    if(t==1) return x;
    if(t==2) return ((ll)x*(x-1)>>1)%P;
    return (((lll)x*(x-1)>>1)*(x-2)/3)%P;
}
int pl[N],pr[N],buc[M];
void sol1(){
    for(int i=0;i<=nx;++i) mn[i]=nx+1;
    for(int i=1;i<=n;++i) chmn(mn[lx[i]-1],rx[i]);
    for(int i=nx-1;~i;--i) chmn(mn[i],mn[i+1]);
    for(int i=1;i<=nx+2;++i)
        for(int c=0;c<=3;++c) s[i][c]=0;
    for(int i=1;i<=nx+1;++i) s[i][0]=1;
    for(int i=nx;i;--i)
        for(int c=1;c<=3;++c){
            s[i][c]=s[i+1][c];
            for(int w=0;w<c;++w)
                s[i][c]=((ll)(s[i+1][w]-s[mn[i]+1][w]+P)*coe(i,c-w)+s[i][c])%P;
        }
    inc(res,s[1][3]);dec(res,s[mn[0]+1][3]);
}
int wl[M],wr[M];
void sol2(){
    for(int i=nx,j=n,l=1,r=ny;i;--i){
        while(j&&lx[pl[j]]>i) chmx(l,ly[pl[j]]),chmn(r,ry[pl[j]]),--j;
        wl[i]=l;wr[i]=r;
    }
    for(int i=1,j=1,l=1,r=ny;i<=nx;++i){
        while(j<=n&&rx[pr[j]]<i) chmx(l,ly[pr[j]]),chmn(r,ry[pr[j]]),++j;
        int sl=l,sr=r;
        chmx(sl,wl[i]);chmn(sr,wr[i]);
        if(sl<=sr) res=(res+(ll)(by[sr]-by[sl-1])*coe(i,2))%P;
    }
}
int lmn[T],lmx[T],lsec[T],lnum[T],tgl[T];
int rmn[T],rmx[T],rsec[T],rnum[T],tgr[T];
int sum[T];bool ban[T],leaf[T];
void pushups(int p){sum[p]=sum[lc]+sum[rc];if(sum[p]>=P) sum[p]-=P;}
void pushupl(int p){
    ban[p]=ban[lc]&&ban[rc];
    lmn[p]=min(lmn[lc],lmn[rc]);
    lmx[p]=max(lmx[lc],lmx[rc]);
    pushups(p);
    if(!ban[p]){
        if(!ban[lc]&&(lmn[lc]<lmn[rc]||ban[rc])){
            lmn[p]=lmn[lc];lnum[p]=lnum[lc];lsec[p]=lsec[lc];
            if(!ban[rc]) chmn(lsec[p],lmn[rc]);
            return;
        }
        if(!ban[rc]&&(lmn[lc]>lmn[rc]||ban[lc])){
            lmn[p]=lmn[rc];lnum[p]=lnum[rc];lsec[p]=lsec[rc];
            if(!ban[lc]) chmn(lsec[p],lmn[lc]);
            return;
        }
        lnum[p]=lnum[lc]+lnum[rc];
        lsec[p]=min(lsec[lc],lsec[rc]);
    }
    else sum[p]=0;
}
void pushupr(int p){
    ban[p]=ban[lc]&&ban[rc];
    rmn[p]=min(rmn[lc],rmn[rc]);
    rmx[p]=max(rmx[lc],rmx[rc]);
    pushups(p);
    if(!ban[p]){
        if(!ban[lc]&&(rmx[lc]>rmx[rc]||ban[rc])){
            rmx[p]=rmx[lc];rnum[p]=rnum[lc];rsec[p]=rsec[lc];
            if(!ban[rc]) chmx(rsec[p],rmx[rc]);
            return;
        }
        if(!ban[rc]&&(rmx[lc]<rmx[rc]||ban[lc])){
            rmx[p]=rmx[rc];rnum[p]=rnum[rc];rsec[p]=rsec[rc];
            if(!ban[lc]) chmx(rsec[p],rmx[lc]);
            return;
        }
        rnum[p]=rnum[lc]+rnum[rc];
        rsec[p]=max(rsec[lc],rsec[rc]);
    }
    else sum[p]=0;
}
void pushup(int p){pushupl(p);pushupr(p);}
void fresh(int p){
    ban[p]=1;sum[p]=0;
    lmn[p]=lmx[p]=1;lsec[p]=nx+1;
    rmn[p]=rmx[p]=nx;rsec[p]=0;
}
void procl(int p,int v){
    if(ban[p]) return;
    inc(sum[p],(ll)lnum[p]*bx[lmn[p]-1]%P);
    if(lmn[p]==lmx[p]) lmx[p]+=v;
    lmn[p]+=v;tgl[p]+=v;
    dec(sum[p],(ll)lnum[p]*bx[lmn[p]-1]%P);
}
void procr(int p,int v){
    if(ban[p]) return;
    dec(sum[p],(ll)rnum[p]*bx[rmx[p]]%P);
    if(rmn[p]==rmx[p]) rmn[p]-=v;
    rmx[p]-=v;tgr[p]+=v;
    inc(sum[p],(ll)rnum[p]*bx[rmx[p]]%P);
}
void pushdown(int p){
    if(leaf[p]||ban[p]) return;
    if(tgl[p]){
        int lim=min(lmn[lc],lmn[rc]);
        if(lmn[lc]==lim||ban[rc]) procl(lc,tgl[p]);
        if(lmn[rc]==lim||ban[lc]) procl(rc,tgl[p]);
        tgl[p]=0;
    }
    if(tgr[p]){
        int lim=max(rmx[lc],rmx[rc]);
        if(rmx[lc]==lim||ban[rc]) procr(lc,tgr[p]);
        if(rmx[rc]==lim||ban[lc]) procr(rc,tgr[p]);
        tgr[p]=0;
    }
}
void gol(int p,int v){
    pushdown(p);
    if(ban[p]||v<=lmn[p]) return;
    if(v<lsec[p]) return procl(p,v-lmn[p]);
    gol(lc,v);gol(rc,v);pushupl(p);
}
void gor(int p,int v){
    pushdown(p);
    if(ban[p]||v>=rmx[p]) return;
    if(v>rsec[p]) return procr(p,rmx[p]-v);
    gor(lc,v);gor(rc,v);pushupr(p);
}
void build(int p=1,int l=1,int r=ny){
    leaf[p]=(l==r);
    tgl[p]=tgr[p]=0;ban[p]=0;
    lmn[p]=lmx[p]=1;lsec[p]=nx+1;
    rmn[p]=rmx[p]=nx;rsec[p]=0;
    lnum[p]=rnum[p]=by[r]-by[l-1];
    sum[p]=(ll)(by[r]-by[l-1])*L%P;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
void seqban(int vl,int vr,int p,int l,int r){
    pushdown(p);
    if(rmn[p]>=vl&&lmx[p]<=vr) return;
    if(l==r) return fresh(p);
    int mid=(l+r)>>1;
    seqban(vl,vr,lc,l,mid);
    seqban(vl,vr,rc,mid+1,r);
    pushup(p);
}
void update(int sl,int sr,int vl,int vr,int p=1,int l=1,int r=ny){
    pushdown(p);
    if(sl<=l&&r<=sr){
        seqban(vl,vr,p,l,r);
        gol(p,vl);gor(p,vr);
        return;
    }
    int mid=(l+r)>>1;
    if(sl<=mid) update(sl,sr,vl,vr,lc,l,mid);
    if(sr>mid) update(sl,sr,vl,vr,rc,mid+1,r);
    pushup(p);
}
int query(int sl,int sr,int p=1,int l=1,int r=ny){
    pushdown(p);
    if(ban[p]) return 0;
    if(sl<=l&&r<=sr) return sum[p];
    int mid=(l+r)>>1,res=0;
    if(sl<=mid) inc(res,query(sl,sr,lc,l,mid));
    if(sr>mid) inc(res,query(sl,sr,rc,mid+1,r));
    return res;
}
void sol3(){
    build();
    for(int i=1,j=1,cl=1,cr=ny;i<=nx;++i){
        while(j<=n&&rx[pr[j]]<i){
            int e=pr[j++];
            chmx(cl,ly[e]);chmn(cr,ry[e]);
            if(ly[e]>1) update(1,ly[e]-1,lx[e],rx[e]);
            if(ry[e]<ny) update(ry[e]+1,ny,lx[e],rx[e]);
        }
        int dl=max(wl[i],cl),dr=min(wr[i],cr),tmp=0;
        if(dl<=dr){
            if(wl[i]<cl) inc(tmp,query(wl[i],cl-1));
            if(wr[i]>cr) inc(tmp,query(cr+1,wr[i]));
            inc(tmp,(ll)(by[dr]-by[dl-1])*bx[i-1]%P);
        }
        else inc(tmp,query(wl[i],wr[i]));
        inc(res,(ll)tmp*(bx[i]-bx[i-1])%P);
    }
}
void calc(){
    for(int i=1;i<=nx;++i) buc[i]=0;
    for(int i=1;i<=n;++i) ++buc[lx[i]];
    for(int i=1;i<=nx;++i) buc[i]+=buc[i-1];
    for(int i=1;i<=n;++i) pl[buc[lx[i]]--]=i;
    for(int i=1;i<=nx;++i) buc[i]=0;
    for(int i=1;i<=n;++i) ++buc[rx[i]];
    for(int i=1;i<=nx;++i) buc[i]+=buc[i-1];
    for(int i=1;i<=n;++i) pr[buc[rx[i]]--]=i;
    sol1();sol2();sol3();
}
void solve(){
    n=read();nx=ny=0;res=0;
    for(int i=1;i<=n;++i){
        lx[i]=read();ly[i]=read();
        rx[i]=read();ry[i]=read();
        if(lx[i]>1) bx[++nx]=lx[i]-1;
        if(ly[i]>1) by[++ny]=ly[i]-1;
        bx[++nx]=rx[i];by[++ny]=ry[i];
    }
    bx[++nx]=L;by[++ny]=L;
    sort(bx+1,bx+nx+1);nx=unique(bx+1,bx+nx+1)-bx-1;
    sort(by+1,by+ny+1);ny=unique(by+1,by+ny+1)-by-1;
    for(int i=1;i<=n;++i){
        lx[i]=lower_bound(bx+1,bx+nx+1,lx[i])-bx;
        ly[i]=lower_bound(by+1,by+ny+1,ly[i])-by;
        rx[i]=lower_bound(bx+1,bx+nx+1,rx[i])-bx;
        ry[i]=lower_bound(by+1,by+ny+1,ry[i])-by;
    }
    calc();
    swap(nx,ny);
    for(int i=1;i<=nx||i<=ny;++i) swap(bx[i],by[i]);
    for(int i=1;i<=n;++i) swap(lx[i],ly[i]),swap(rx[i],ry[i]);
    calc();
    printf("%d\n",res);
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}