P11830 [省选联考 2025] 幸运数字 题解

· · 题解

这题从开始写到通过时间跨度有点大所以现在已经忘记怎么做的了（

反正只是卡了常就过了？

const ll N=2e5+10;
ll pren,n,siz,ans,l1[N],r1[N],l2[N],r2[N],pos[N*2],cnt[N*2],cur[N*2],le1[N*2],le2[N*2],gr1[N*2],gr2[N*2];

void input() {
//  cin>>n;
    n=read();

    rep(i,1,n) {
//      cin>>l1[i]>>r1[i]>>l2[i]>>r2[i];
        l1[i]=read();
        r1[i]=read();
        l2[i]=read();
        r2[i]=read();
        pos[++siz]=l2[i];
        pos[++siz]=r2[i]+1;
    }
}

void disc() {
    sort(pos+1,pos+siz+1);
    siz=unique(pos+1,pos+siz+1)-pos-1;
//  cout<<"pos[]:";
//
//  rep(i,1,siz) cout<<pos[i]<<' ';
//
//  endl;
//  pause;
}

void cal() {
    rep(i,1,n) {
        ll l=lower_bound(pos+1,pos+siz+1,l2[i])-pos,r=lower_bound(pos+1,pos+siz+1,r2[i]+1)-pos;
//      cout<<"l="<<l<<",r="<<r<<'\n';
//      pause;
        cur[l]+=r1[i];
        cur[r]-=r1[i];
        cnt[l]++;
        cnt[r]--;
        le1[r]+=l1[i];
        le2[r]+=r1[i];
        gr1[1]+=l1[i];
        gr1[l]-=l1[i];
        gr2[1]+=r1[i];
        gr2[l]-=r1[i];
    }

    ll curs=0,les1=0,les2=0,grs1=0,grs2=0,cnts=0;

    rep(i,1,siz-1) {
        curs+=cur[i];
        les1+=le1[i];
        les2+=le2[i];
        grs1+=gr1[i];
        grs2+=gr2[i];
        cnts+=cnt[i];

        if(cnts>0 and max(les1-curs+1,grs1)<=min(les2+curs,grs2)) ans+=pos[i+1]-pos[i];
    }
}

void ini() {
    //ll n,siz,ans,l1[N],r1[N],l2[N],r2[N],pos[N*2],cnt[N*2],cur[N*2],le1[N*2],le2[N*2],gr1[N*2],gr2[N*2];
    siz=ans=0;
//  init(l1,0);
//  init(r1,0);
//  init(l2,0);
//  init(r2,0);
//  init(pos,0);
//  init(cnt,0);
//  init(cur,0);
//  init(le1,0);
//  init(le2,0);
//  init(gr1,0);
//  init(gr2,0);

    rep(i,1,pren) l1[i]=l2[i]=r1[i]=r2[i]=0;//最后通过的关键 

    rep(i,1,2*N-1) pos[i]=cnt[i]=cur[i]=le1[i]=le2[i]=gr1[i]=gr2[i]=0;
}

int main() {
//  sync_off;
    ll testno=read(),Q=read();
//  cin>>testno>>Q;

    count(Q) {
        ini();
        input();
        disc();
        cal();
//      cout<<ans<<'\n';
        print(ans);
        putchar('\n');
        pren=n;
    }
}