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;
	}
}