P11830 [省选联考 2025] 幸运数字
后面忘了，随机分讨，讨论出每一段前面，当前，后面的可能数量区间，还需要对离散化后每个点和两个点之间的段进行分讨，应该是写烦了
#include<bits/stdc++.h>
#define fi first
#define se second
#define N 400005
#define int long long
using namespace std;
struct Ty{int l1,r1,l2,r2;bool operator <(const Ty &a)const{return l2<a.l2;}
}x[N];
priority_queue<pair<int,int> >q;
int z[N],n,m=0,prel[N],prer[N],sufl[N],sufr[N],xl[N],xr[N],pxl[N],pxr[N];
signed main(){int c,T;scanf("%lld%lld",&c,&T);while(T--){m=0;scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&x[i].l1,&x[i].r1,&x[i].l2,&x[i].r2);for(int i=1;i<=n;i++){z[++m]=x[i].l2;z[++m]=x[i].r2;}sort(z+1,z+m+1);m=unique(z+1,z+m+1)-z-1;for(int i=1;i<=n;i++){x[i].l2=lower_bound(z+1,z+m+1,x[i].l2)-z;x[i].r2=lower_bound(z+1,z+m+1,x[i].r2)-z;}sort(x+1,x+n+1);int now=1,pl=0,pr=0,l=0,r=0;while(!q.empty())q.pop();for(int i=1;i<=m+1;i++){pxl[i]=l;pxr[i]=r;while(now<=n&&x[now].l2<=i){l+=x[now].l1;r+=x[now].r1;q.push({-x[now].r2,now});now++;}xl[i]=l;xr[i]=r;while(!q.empty()&&-q.top().fi<=i){int u=q.top().se;pl+=x[u].l1;pr+=x[u].r1;l-=x[u].l1;r-=x[u].r1;q.pop();}prel[i]=pl;prer[i]=pr;}now=n;pl=pr=l=r=0;while(!q.empty())q.pop();for(int i=m+1;i;i--){while(now&&x[now].r2>=i){l+=x[now].l1;r+=x[now].r1;q.push({x[now].l2,now});now--;}while(!q.empty()&&q.top().fi>=i){int u=q.top().se;pl+=x[u].l1;pr+=x[u].r1;l-=x[u].l1;r-=x[u].r1;q.pop();}sufl[i]=pl;sufr[i]=pr;}int ans=0;for(int i=1;i<=m;i++){if(prer[i-1]>=sufl[i]&&prel[i-1]<=sufr[i]&&pxr[i]>0)ans+=z[i]-z[i-1]-1;else if(pxr[i]>0){if(prer[i-1]<sufl[i]){if(prer[i-1]+pxr[i]>=sufl[i])ans+=z[i]-z[i-1]-1;}else{if(sufr[i]+pxr[i]>prel[i-1])ans+=z[i]-z[i-1]-1;}}if(prer[i-1]>=sufl[i+1]&&prel[i-1]<=sufr[i+1]&&xr[i]>0)ans++;else if(xr[i]>0){if(prer[i-1]<sufl[i+1])ans+=(prer[i-1]+xr[i]>=sufl[i+1]);else ans+=(sufr[i+1]+xr[i]>prel[i-1]);}}printf("%lld\n",ans);}return 0;
}