省选联考 2025 游记

· · 生活·游记

唉。

Day1 看了每道题，猜测 t1 的合法中位数一定为一段区间刨掉没出现的数，然后发现对于每一个值 check 需要一个查询每个 {l_2}_i > v 或者 {r_2}_i < v 的东西的 l_1 和 r_1 的和，这个东西可以直接排两边序维护前缀和然后 O(1) 做的吧。不知道在干嘛，写了个 fhq 来维护。不过这部分一遍就写对了，大概只用了 15min 左右。会了枚举值的 V\log n 做法。

发现 check 里面，如果 < v 和 > v 的个数区间有交，那么 v 一定合法。然后，然后，然后。线段交写错了，但一直没发现，就一直糊着一个错掉的 check。想着打表验证一下结论吧，然后因为错掉的 check 发现结论假掉了，感觉瞬间人就红了，想想想改改改调调调，一直过不去样例 3 的最后一个点，还看错了样例，以为这个点有性质 B，继续猜性质 A 会满足这个结论，假装有了 A 的分然后去看 t2，t3，结果都只会最低档暴力，继续滚回来看 t1。

继续调，把代码重构了几遍也没发现错在哪，day1 就这么草率的结束了。出来同学告诉我样例 3 最后一个点没有性质，以为自己的 A 和 B 都过了，发现被每个见到的人偏序。

忘记 day1，准备 day2。真的有人能做到吗？回家看到 luogu 有自测了，写了一下 V \log n 交了，30分！！把代码反反复复看了好几遍，希望是我复现时写错了，结果发现，线段交写错了，还因为 fhq 常数太大被卡了。哈哈。不过这个东西应该性质 B 不会错，希望评测机快一点啊。

Day2 更爆炸。看了一眼，发现有两个模 p 题，去看 t1，很快会了性质 AB，然后会了 O(n^2) 的暴力，具体先按 t 排序，把一堆相交的线段看作一个块，然后块内如果当前需要移的箱子会被阻挡，那么依次推到 b_i+1,b_i+2 之类的就对了。结果暴力因为写了一堆糖东西，调到 11 点多才调对，之后的 ds 维护也很简单，具体线段树区间推等差数列，然后单点查，二分一下上下界就对完了吧。

先写了 t2t3 的暴力，然后写 t1，这个东西改成线段树上二分，就能做到一只 \log 了吧，哈哈，感觉很对，结果写的很快，越调越红温，上了几次厕所冷静一下，看到窗户外面那些文化课的同学下课在底下三三两两的走，感觉我永远也不可能融入他们了。最后 t1 也没过，交了暴力和性质 AB。出来发现每个人都过了 t1，回去睡了一下午，就这样吧，真的还有一年吗？

希望大家一直记得我。

“希望大家永远忘了我。”

放一下 d1t1 的 V \log n 的代码，竟然只有 2k。

#include<bits/stdc++.h>
using ll = int;
#define For(i,j,k) for(int i = j;i <= k;i++)
#define Rep(i,j,k) for(int i = j;i >= k;i--)
#define pll pair<ll,ll>
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10;
struct FHQ{
    #define ls t[p].s[0]
    #define rs t[p].s[1]
    struct P{ll v,sz,dt,o1,o2,smo1,smo2,s[2];}t[N];ll x,y,z,to,rt;
    void it(ll n){rt = to = 0;For(i,1,n) t[i] = {0,0,0,0,0,0,0,{0,0}};}
    void psu(ll p){t[p].sz = t[ls].sz + t[rs].sz + 1;
        t[p].smo1 = t[ls].smo1 + t[rs].smo1 + t[p].o1;
        t[p].smo2 = t[ls].smo2 + t[rs].smo2 + t[p].o2;
    }void sptv(ll p,ll k,ll &x,ll &y){if(p == 0){x = y = 0;return;}
        t[p].v <= k ? (x = p,sptv(rs,k,rs,y)) : (y = p,sptv(ls,k,x,ls));psu(p);
    }ll mrg(ll u,ll v){if(!u || !v) return u | v;
        if(t[u].dt < t[v].dt) return t[u].s[1] = mrg(t[u].s[1],v),psu(u),u;
        else return t[v].s[0] = mrg(u,t[v].s[0]),psu(v),v;
    }ll nw(ll v,ll o1,ll o2){t[++to] = {v,1,rand(),o1,o2,o1,o2,{0,0}};return to;}
    void ist(ll v,ll o1,ll o2){sptv(rt,v,x,y),rt = mrg(mrg(x,nw(v,o1,o2)),y);}
    pll qryl(ll v){sptv(rt,v,x,y);pll tp = {t[x].smo1,t[x].smo2};rt = mrg(x,y);return tp;}
    pll qryr(ll v){sptv(rt,v - 1,x,y);pll tp = {t[y].smo1,t[y].smo2};rt = mrg(x,y);return tp;}
}trl,trr;ll n,o,sm,ans,l1[N],l2[N],r1[N],r2[N];bool chk(ll v){
    o = 0;ll mnx,mny,mxx,mxy;pll q1 = trl.qryr(v + 1),q2 = trr.qryl(v - 1);
    mxx = q1.fi,mxy = q1.se,mnx = q2.fi,mny = q2.se,o = sm - mxy - mny;if(!o) return 0;
    if((mxx <= mnx && mnx <= mxy) || (mxx <= mny && mny <= mxy)) return 1;ll o1,o2; 
    if(mxy < mnx) o1 = mnx,o2 = mxy;else o1 = mny,o2 = mxx;ll m = o + o1 + o2,tp = (m + 1) / 2;
    return tp > o1 && tp <= o1 + o;
}void sol(ll c){ans = sm = 0;
    cin >> n;For(i,1,n) cin >> l1[i] >> r1[i] >> l2[i] >> r2[i],sm += r1[i];
    For(i,1,n) trl.ist(l2[i],l1[i],r1[i]),trr.ist(r2[i],l1[i],r1[i]);
    For(v,1,n) if(chk(v)) ans++;cout << ans << '\n';trl.it(n),trr.it(n);
}int main(){
    freopen("lucky.in","r",stdin),freopen("lucky.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll T,c;cin >> c >> T;while(T--) sol(c);return 0;
}