妙妙题。
题目链接。
发现中位数并不好刻画，需要转化。假设对于数字 \(x\)，设小于 \(x\) 的数个数为 \(a\)，等于 \(x\) 的数的个数为 \(b\)，大于 \(x\) 的数的个数为 \(c\)。则 \(x\) 为中位数的充分必要条件为 \(a+b\ge c\)，\(a < b+c\)。这可以推，也可以当成结论记下来。
显然的，对于 \(b\)，只要有区间覆盖到 \(x\)，就应该加上 \(r_1\)，这是最优的。
考虑对应确定的 \(a\)，应该怎么做。转化一下条件，就变成了 \(c > a-b\)。因此，\(c \in [a-b+1,a+b]\)。
但是显然的， \(c\) 自身的区间也是有上下限的，我们记为 \([L,R]\)，因此 \(c \in [max(L,a-b+1),min(R,a+b)]\)。只要这个区间存在， \(x\) 就是合法的。
然后再考虑 \(a\) ，类似的，\(a\) 的取值也存在上下限，记为 \([l,r]\)，\(a-b+1\) 的 \(min\) 显然为 \(l - b + 1\)，\(a+b\) 的 \(max\) 显然为 \(r+b\)。因此，也就是要 \(c \in [max(L,l-b+1),min(R,r+b)]\)。问题变成了如何高速计算 \(l,r,L,R,b\)。
可以考虑离散化+差分的思路。\(b\) 的统计思路是显然的，对于其他的，假设当前处理的区间为 \(l_{i,1},r_{i,1},l_{i,2},r_{i,2}\)，则让 \([0,l_{i,2}-1]\) 的 \(L,R\) 进行更新，让 \([r_{i,2}+1,+\infin]\) 的 \(l,r\) 更新。
注意：本题要开 long long。不然做的时候会看到祖宗。
Code
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
#define l1 l$
#define l2 l$$
#define r1 r$
#define r2 r$$
const int M = 4e5 + 10;
const int N = 2e5 + 10;
struct range{LL l1,l2,r1,r2;
};
int n;
int tot;
void solve(){cin >> n;vector< range > a(n);vector< LL > tmp(n);vector< LL > lsh;for(int i=0;i<n;i++){cin >> a[i].l1 >> a[i].r1 >> a[i].l2 >> a[i].r2;lsh.push_back(a[i].l2);lsh.push_back(a[i].r2);lsh.push_back(a[i].r2+1);tmp[i] = a[i].r2;}sort(lsh.begin(),lsh.end());auto lst = unique(lsh.begin(),lsh.end());lsh.erase(lst,lsh.end());int len = lsh.size();for(int i=0;i<n;i++){a[i].l2 = lower_bound(lsh.begin(),lsh.end(),a[i].l2) - lsh.begin()+1;a[i].r2 = lower_bound(lsh.begin(),lsh.end(),a[i].r2) - lsh.begin()+1;}vector<LL> sum(len+1),l(len+1),r(len+1),L(len+1),R(len+1);// b_cnt,l,r,L,Rfor(int i=0;i<n;i++){int x = lower_bound(lsh.begin(),lsh.end(),tmp[i]+1) - lsh.begin()+1;sum[a[i].l2] += a[i].r1;sum[x] -= a[i].r1;L[0] += a[i].l1;L[a[i].l2] -= a[i].l1;R[0] += a[i].r1;R[a[i].l2] -= a[i].r1;l[x] += a[i].l1;r[x] += a[i].r1;}for(int i=1;i<=len;i++){sum[i] += sum[i-1];l[i] += l[i-1];r[i] += r[i-1];L[i] += L[i-1];R[i] += R[i-1];}lsh.push_back(len+1);LL ans = 0;for(int i=1;i<=len;i++){// cout << l[i] << " " << r[i] << " " << L[i] << " " << R[i] << " " << sum[i] << "\n";if(sum[i] && max(l[i]-sum[i]+1,L[i]) <= min(r[i]+sum[i],R[i])){ans += lsh[i] - lsh[i-1];}}cout << ans << "\n";return ;
}
int main()
{IOS;int c,T;cin >> c >> T;while(T -- ) solve();return 0;
}