#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 2e5 + 10;
const int M = 2 * N;
 
int n, ln, cf, ans;    // ln:离散化后点数, cf:当前覆盖 x 的区间数
 
int l1[N], r1[N], l2[N], r2[N];   // 输入的四元组
int dc[M];    // 离散化坐标（所有 l2 和 r2+1）
LL sumb, mna, mxa, mnc, mxc, sumf;         // 当前扫描到的累计值
 
LL bs[M], al[M], ar[M], cl[M], cr[M], f[M]; // 差分数组
// bs: 等于 x 
// al: amin
// ar: amax
// cl: cmin
// cr: cmax
// f: 覆盖x的区间数量的差分 (用于判断是否有区间包含x)
 
void solve() {
	cin >> n;
    for (int i = 1; i <= ln; i ++) {
		bs[i] = al[i] = ar[i] = cl[i] = cr[i] = f[i] = 0;
	}
    ln = sumb = mna = mxa = mnc = mxc = sumf = ans = 0;
 
    for (int i = 1; i <= n; i ++) {
    	cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
        dc[++ ln] = l2[i];
        dc[++ ln] = r2[i] + 1;
        // 我们将全闭区间变为左闭右开区间，方便计算差分 
    }
 
    sort(dc + 1, dc + 1 + ln);
    ln = unique(dc + 1, dc + 1 + ln) - dc - 1;
 
    // 构建差分数组，每个区间对四个量产生影响
    for (int i = 1; i <= n; i ++) {
    	// 这里的 x 和 y 对应着当前区间可选的最小值和最大值 
        int x = lower_bound(dc + 1, dc + 1 + ln, l2[i]) - dc;      // 左端点位置
        int y = lower_bound(dc + 1, dc + 1 + ln, r2[i] + 1) - dc;  // 右端点 + 1 位置
 
        // 等于当前值的区间贡献：在 [l2, r2] 内增加 r1
        bs[x] += r1[i];
        bs[y] -= r1[i];
 
        // 当前值区间作为别人的 a 
        al[y] += l1[i];   // 当别人的 amin，取最少的数量  
        ar[y] += r1[i];   // 当别人的 amax，取最多的数量  
 
        // 当前值区间作为别人的 c 
        cl[1] += l1[i];   // 当别人的 cmin，取最少的数量  
        cl[x] -= l1[i];   // 只有比 x 小的才能选为 c 
 
        cr[1] += r1[i];   // 当别人的 cmax，取最多的数量  
        cr[x] -= r1[i];   // 只有比 x 小的才能选为 c 
 
        // 覆盖当前值的区间数量计数
        f[x] ++; 
        f[y] --;   
    }
 
    for (int i = 1; i < ln; i ++) {
        // 累计当前点的值
        sumb += bs[i];   // 等于 x 的个数总和
        mna += al[i];   // 小于 x 的最小可能个数
        mxa += ar[i];   // 小于 x 的最大可能个数
        mnc += cl[i];   // 大于 x 的最小可能个数
        mxc += cr[i];   // 大于 x 的最大可能个数
        sumf += f[i];   // 覆盖 x 的区间数量
 
        // 必须有区间覆盖 x（否则 x 不会出现在集合中）
        if (sumf == 0) continue;
 
        LL lef = max(mna - sumb + 1, mnc);
        LL rig = min(mxa + sumb, mxc);
        if (lef <= rig) {
            // 这段区间内所有整数点都满足条件，加入长度
            ans += dc[i + 1] - dc[i];
        }
    }
    cout << ans << "\n";
}
 
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int c, T;
	cin >> c >> T;
	while(T --) {
		solve();
	}
	
	return 0;
}

day1t1题解

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)

const int N=200005,M=N*2;
int n,m; 
int a[N],b[N],c[N],d[N],v[M];
ll s[4][M],sum;
inline ll getsum(int l,int r,int t)
{
	return s[t][r]-s[t][l-1];
}
bool check(int x)
{
	ll xl=getsum(1,x-1,2),xr=getsum(1,x-1,3);
	ll yl=getsum(x+1,m,0),yr=getsum(x+1,m,1);
	ll z=sum-xr-yr;
	if (z==0) return 0;
	if (xr+z<yl) return 0;
	if (yr+z<=xl) return 0;
	return 1;
}

void work()
{
	m=0,sum=0;
	cin >> n;
	rep(i,1,n) cin >> a[i] >> b[i] >> c[i] >> d[i];
	rep(i,1,n) v[++m]=c[i],v[++m]=d[i]+1;
	sort(v+1,v+m+1);
	m=unique(v+1,v+m+1)-v-1;
	rep(i,0,3) rep(j,0,m) s[i][j]=0;
	rep(i,1,n)
	{
		int x=lower_bound(v+1,v+m+1,c[i])-v;
		int y=lower_bound(v+1,v+m+1,d[i]+1)-v-1;
		s[0][x]+=a[i],s[1][x]+=b[i],s[2][y]+=a[i],s[3][y]+=b[i];
		sum+=b[i];
	}
	rep(i,0,3) rep(j,1,m) s[i][j]+=s[i][j-1];
	int ans=0;
	rep(i,1,m-1) if (check(i)) ans+=v[i+1]-v[i];
	cout << ans << "\n";
}

int main()
{
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	ios_base::sync_with_stdio(False);
	cin.tie(0);
	int T;
	cin >> T >> T;
	while (T--) work();
	return 0;
}

考场思路，大样例过了，不知道对不对。

考虑对于一个数 $x$，它能成为中位数需要满足什么条件。

首先肯定要有区间包含它，否则 $x$ 连出现一次都不可能。

然后设如果有 $a$ 个数 $<x$，$b$ 个数 $=x$，$c$ 个数 $>x$，那么必须满足以下两个不等式：

• $a+b\ge c$。如果 $a+b<c$，第 $\lfloor\dfrac{m+1}2\rfloor$ 个数 $>x$。
• $a<b+c$。如果 $a\ge b+c$，第 $\lfloor\dfrac{m+1}2\rfloor$ 个数 $<x$。

有一个贪心策略是如果 $l_{i,2}\le x\le r_{i,2}$，即可以放 $x$，就尽量放 $r_{i,1}$ 个 $x$。因为把非 $x$ 改成 $x$，$a$ 和 $c$ 减小而 $b$ 增大，显然 $x$ 成为中位数可能性变大。而且 $x$ 的个数越多，$a$ 和 $c$ 不变而 $b$ 越大，两个不等式中要求大的那部分，即包含 $b$ 的那部分变大，也是更优的。

现在问题变成 $a$ 和 $c$ 取多少。受到个数的限制，$a$ 和 $c$ 都有个最小值和最大值，$a$ 的取值范围为 $[l,r]$，$c$ 的取值范围为 $[L,R]$。

考虑固定 $a$，求 $c$ 的取值范围。第一个不等式化为 $c\le a+b$，第二个不等式化为 $c>a-b$。联立可得 $c\in[a-b+1,a+b]$。

现在不固定 $a$。$a=l$ 时，$c$ 最小为 $l-b+1$。$a=r$ 时，$c$ 最大为 $r+b$。所以 $c\in[l-b+1,r+b]$。

又因为 $c$ 的取值范围为 $[L,R]$，所以 $c\in[\max(l-b+1,L),\min(r+b,R)]$。

对于 $x$，求出 $b,l,r,L,R$ 之后，若 $c$ 的取值范围非空，即 $\max(l-b+1,L)\le\min(r+b,R)$，则 $x$ 可以作为中位数。$b,l,r,L,R$ 可以枚举每个区间，判断其与 $x$ 的关系来求。

到目前为止期望得分 $50$。

我们的瓶颈在于算出 $b,l,r,L,R$，考虑用差分前缀和优化这一过程。具体来讲，一个区间 $[l_{i,2},r_{i,2}]$，会对 $[l_{i,2},r_{i,2}]$ 的 $b$ 产生 $r_{i,1}$ 的贡献，对 $(r_{i,2},\infty)$ 的 $l$ 产生 $l_{i,1}$ 的贡献，对 $(r_{i,2},\infty)$ 的 $r$ 产生 $r_{i,1}$ 的贡献，对 $[1,l_{i,2})$ 的 $L$ 产生 $l_{i,1}$ 的贡献，对 $[1,l_{i,2})$ 的 $R$ 产生 $r_{i,1}$ 的贡献。而 $x$ 能否成为中位数只与 $b,l,r,L,R$ 有关，即如果没有跨过任何区间，不改变 $x$ 能否成为中位数。

所以我们可以对由区间左右端点划分而成的一段进行计算，用前缀和算出 $b,l,r,L,R$ 即可。

需要排序+离散化，时间复杂度 $O(n\log n)$。

可以通过民间数据的代码：

int n,ln,cf,as,l1[N],r1[N],l2[N],r2[N],dc[N*2],f[N*2];
ll ca,cb,cc,cd,ce,a[N*2],b[N*2],c[N*2],d[N*2],e[N*2];
void QwQ() {
	n=rd();
	for(int i=1;i<=ln;i++) a[i]=b[i]=c[i]=d[i]=e[i]=f[i]=0;
	ln=ca=cb=cc=cd=ce=cf=as=0;
	for(int i=1;i<=n;i++)
		l1[i]=rd(),r1[i]=rd(),l2[i]=rd(),r2[i]=rd(),
		dc[++ln]=l2[i],dc[++ln]=r2[i]+1;
	sort(dc+1,dc+1+ln),ln=unique(dc+1,dc+1+ln)-dc-1;
	for(int i=1,x,y;i<=n;i++)
		x=lb(dc+1,dc+1+ln,l2[i])-dc,y=lb(dc+1,dc+1+ln,r2[i]+1)-dc,
		a[x]+=r1[i],a[y]-=r1[i],
		b[y]+=l1[i],c[y]+=r1[i],
		d[1]+=l1[i],d[x]-=l1[i],
		e[1]+=r1[i],e[x]-=r1[i],
		f[x]++,f[y]--;
	for(int i=1;i<ln;i++) {
		ca+=a[i],cb+=b[i],cc+=c[i],cd+=d[i],ce+=e[i],cf+=f[i];
		if(cf&&max(cb-ca+1,cd)<=min(cc+ca,ce)) as+=dc[i+1]-dc[i];
	}
	wr(as,"\n");
}