专栏文章

省队集训-0421模拟赛

aallenchoi
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipj1qzn
此快照首次捕获于
2025/12/03 12:49
3 个月前
此快照最后确认于
2025/12/03 12:49
3 个月前
查看原文
比赛链接

A.火力全开

题意：

有 nn 只怪，mm 个炸弹，给定常数 kk。
第 ii 个炸弹有代价 cic_i，威力 did_i，每个炸弹至多使用一次；
第 ii 只怪有血量 aia_i，等级 bib_i，杀死它要花 aia_i 的代价普攻，或者引爆至少 kk 个威力不小于 bib_i 的炸弹。
qq 次修改，每次修改一只怪的 (ai,bi)(a_i,b_i) 或一个炸弹的 (ci,di)(c_i,d_i)，每次修改后问杀死所有怪的最小代价。
n,m,q≤2.5×105,qk≤5×105n,m,q\le 2.5\times 10^5,qk\le 5\times 10^5。

Sol：

显然用恰好 kk 个炸弹或不用。把所有怪、炸弹按照 bib_i 或 did_i 升序排序，则代价为一个后缀中 aia_i 之和，加上最小的 kk 个 cic_i 之和。
可以离线，将所有东西排好序后丢到一个线段树上，维护两个东西：f1x,if1_{x,i} 表示 xx 子树内第 ii 小的 cc，f2x,if2_{x,i} 表示后缀左端点在子树中，且选了 ii 个 cc 时的最小代价。
显然第二维只用维护到 kk。
pushup 时，f1f1 归并排序即可，f2f2 有转移：
f2x,i=min⁡(f2rs,i,min⁡jf2ls,j+sumars+∑t=1jf1rs,t)f2_{x,i}=\min(f2_{rs,i},\min\limits_{j} f2_{ls,j}+suma_{rs}+\sum\limits_{t=1}^{j}f1_{rs,t})。
发现是一个卷积形式，所以可以做到 O(qk2log⁡)O(qk^2\log)，然后结合 O(qnlog⁡)O(qn\log) 的暴力（枚举后缀）可以做到 O(qkqklog⁡)O(qk\sqrt{qk}\log)。
进一步观察，发现 ∑t=1jf1rs,t\sum\limits_{t=1}^{j}f1_{rs,t} 有凸性，则它满足四边形不等式，所以 jj 对于 ii 有决策单调性，用二分队列即可做到 O(klog⁡)O(k\log) 的 pushup。
注意！！！ 最开始加入 n+mn+m 个点时不能用单调修改，否则复杂度会变成 nklog⁡nk\log 不一定对。
总复杂度：O((n+qk)log⁡2)O((n+qk)\log^2)。

Code：

CPP
#include <bits/stdc++.h>
#define il inline
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define ls (x << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
#define calc(j,i) (f2[ls][j] + s[i - j] + sum[rs])
using namespace std;
typedef long long ll;
const int N = 7.5e5 + 5,M = 1000;
const ll INF = 1e18;
int n,m,q,k,tot,id1[N],id2[N],pos[N],vis[N];
ll sum;
il int read()
{
    int x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while('0' <= ch && ch <= '9') x = x * 10 + ch - '0',ch = getchar();
    return x;
}
il void write(ll x,char ch)
{
    int top = 0;
    static int st[30];
    while(x) st[++top] = x % 10,x /= 10;
    for(int i = top;i >= 1;i--) putchar('0' + st[i]);
    putchar(ch);
}
struct Node{int x,y,z,id;} p[N],opt[N];
bool cmp(Node x,Node y)
{
    if(x.y != y.y) return x.y < y.y;
    return x.z < y.z;
}
struct SgT
{
    int cnt[N << 2],q[N],L[N],R[N];
    ll sum[N << 2],s[N];
    vector <int> f1[N << 2];
    vector <ll> f2[N << 2];
    void pushup(int x)
    {
        cnt[x] = cnt[ls] + cnt[rs],sum[x] = sum[ls] + sum[rs];
        int u1 = min(cnt[ls],k),u2 = min(cnt[rs],k),u3 = min(cnt[x],k);
        for(int i = 1,a = 1,b = 1;i <= u3;i++)
            if(a <= u1 && (b > u2 || f1[ls][a] < f1[rs][b])) f1[x][i] = f1[ls][a++];
            else f1[x][i] = f1[rs][b++];
        for(int i = 0;i <= u3;i++) f2[x][i] = (i <= u2 ? f2[rs][i] : INF);
        for(int i = 1;i <= u2;i++) s[i] = s[i - 1] + f1[rs][i];
        int head = 1,tail = 0;
        for(int i = 1,p1,p2,l,r,lim;i <= u3;i++)
        {
            while(head <= tail && R[head] < i) head++;
            if(head <= tail) L[head] = i;
            if(i <= u1)
            {
                lim = min(i + u2,u3);
                while(head <= tail)
                {
                    p1 = q[tail],p2 = L[tail];
                    if(calc(i,p2) < calc(p1,p2)) tail--;
                    else break;
                }
                if(head > tail) q[++tail] = i,L[tail] = i,R[tail] = lim;
                else
                {
                    l = L[tail],r = R[tail] + 1,p1 = q[tail];
                    while(r - l > 1)
                    {
                        p2 = mid;
                        if(calc(i,p2) < calc(p1,p2)) r = p2;
                        else l = p2;
                    }
                    R[tail] = l;
                    if(r <= lim) q[++tail] = i,L[tail] = r,R[tail] = lim;
                }
            }
            if(head <= tail) p1 = q[head],f2[x][i] = min(f2[x][i],calc(p1,i));
        }
    }
    int build(int x,int l,int r)
    {
        int ret;
        if(l == r)
        {
            ret = p[l].z;
            f1[x].resize(ret + 1),f2[x].resize(ret + 1);
            if(vis[l])
                if(!p[l].z) sum[x] = p[l].x;
                else f1[x][1] = f2[x][1] = p[l].x,cnt[x] = 1;
            return ret;
        }
        ret = min(build(ls,l,mid) + build(rs,mid + 1,r),k);
        f1[x].resize(ret + 1);
        f2[x].resize(ret + 1);
        pushup(x);
        return ret;
    }
    void update1(int x,int l,int r,int p,int v)
    {
        if(l == r)
        {
            sum[x] = v;
            return ;
        }
        if(p <= mid) update1(ls,l,mid,p,v);
        else update1(rs,mid + 1,r,p,v);
        pushup(x);
    }
    void update2(int x,int l,int r,int p,int v)
    {
        if(l == r)
        {
            cnt[x] = (v > 0),f1[x][1] = f2[x][1] = v;
            return ;
        }
        if(p <= mid) update2(ls,l,mid,p,v);
        else update2(rs,mid + 1,r,p,v);
        pushup(x);
    }
} tr;
il void ins(int x)
{
    if(!p[x].z) tr.update1(1,1,tot,x,p[x].x);
    else tr.update2(1,1,tot,x,p[x].x);
}
il void ers(int x)
{
    if(!p[x].z) tr.update1(1,1,tot,x,0);
    else tr.update2(1,1,tot,x,0);
}
int main()
{
    freopen("fire.in","r",stdin);
    freopen("fire.out","w",stdout);
    n = read(),m = read(),q = read(),k = read();
    for(int i = 1;i <= n;i++) p[i].x = read(),p[i].y = read(),p[i].id = id1[i] = i,sum += p[i].x;
    for(int i = 1;i <= m;i++) p[i + n].x = read(),p[i + n].y = read(),p[i + n].z = 1,p[i + n].id = id2[i] = i + n;
    for(int i = 1;i <= q;i++)
    {
        opt[i].id = read() - 1,opt[i].x = read(),opt[i].y = read(),opt[i].z = read();
        p[i + n + m] = (Node){opt[i].y,opt[i].z,opt[i].id,i + n + m};
    }
    tot = n + m + q;
    sort(p + 1,p + tot + 1,cmp);
    for(int i = 1;i <= tot;i++) pos[p[i].id] = i;
    for(int i = 1;i <= n + m;i++) vis[pos[i]] = 1;
    tr.build(1,1,tot);
    for(int i = 1;i <= q;i++)
    {
        if(!opt[i].id) sum -= p[pos[id1[opt[i].x]]].x,sum += opt[i].y,ers(pos[id1[opt[i].x]]),ins(pos[id1[opt[i].x] = i + n + m]);
        else ers(pos[id2[opt[i].x]]),ins(pos[id2[opt[i].x] = i + n + m]);
        write(min(sum,(tr.cnt[1] >= k ? tr.f2[1][k] : INF)),'\n');
    }
    return 0;
}

B.异或症测试 3

题意：

给出 nn 个数 sis_i 和一个数 XX，满足 0≤si,X<2m0\le s_i,X<2^m，问有多少个 [1,X][1,X] 的子集满足 ss 为它的最小线性基。

Sol：

定义对线性基消元，意思是通过基之间的相互异或，使得每个基都不含除自己代表的主元外的其它主元。称消元后的线性基为消元线性基。
设 ss 自己的线性基为 pp，pp 能得到数集 SS 中，最大的不超过 XX 的数在 SS 中的排名为 xx，则问题转换为 [1,x][1,x] 中有多少子集 TT 的线性基大小为 nn。其实这是将 SS 内的数与它的排名一一对应，而排名又只和它所含的主元有关，所以如果 TT 的线性基大小为 nn，那就一定包含了 pp 内的所有主元，也就一定与 pp 相等。
xx 的话可以将 pp 消元，从大到小贪心地选。
不妨将全集改为 [0,x][0,x]。由于 00 不影响线性基大小，所以最后把答案除以 22 即可。
首先考虑怎么求出 CiC_i，表示 [0,2i)[0,2^i) 的子集中线性基大小为 ii 的数量。
假设 A⊆[0,2i)A\subseteq [0,2^i) 且线性基大小为 ii，则将 AA 中的所有元素除以 22 向下取整、去重得到集合 BB，BB 的线性基的大小一定为 i−1i-1。
由此延伸，考虑怎么用一个 BB 得到一个对应的 AA。
首先如果 x∈Bx\in B，则有 2x∈A2x\in A，2x+1∈A2x+1\in A 和 { 2x,2x+1 }⊆A\set{2x,2x+1}\subseteq A 三种情况。
而有些情况得到的 AA 线性基大小为 i−1i-1，考虑减去这些贡献。
观察到两个性质：
1.如果 AA 的线性基大小为 i−1i-1，那就是将 BB 的线性基内所有数乘上 22，然后最后一位乱填得到，这样的新线性基总共有 2i−12^{i-1} 种；
2.显然 2x,2x+12x,2x+1 不能同时属于 AA，否则线性基含有 11，则大小为 ii。
那么，如果我们确定了线性基 AA，就可以确定 2x,2x+12x,2x+1 中具体是那一个在 AA 中；同时，如果确定了 i−2i-2 个基末尾的填法，和 2x/2x+12x/2x+1 的决策，也能定下唯一的一个基。
所以 Ci=∑B(3∣B∣−2i−1)C_i=\sum\limits_B(3^{|B|}-2^{i-1})。 其中 3∣B∣3^|B| 表示每个 xx 的三种对应方式。
然后考虑上限 xx。
设 Ci,0/1C_{i,0/1} 表示从高到低考虑了 ii 为，xx 前 ii 位的上限 ⌊x2n−i⌋\left\lfloor\dfrac{x}{2^{n-i}}\right\rfloor 是否在集合内，B0/1B_{0/1} 表示对应的集合。
考虑从 i−1i-1 转移到 ii。分类讨论。
如果 xx 在 n−in-i 位为 00：
如果 xx 在上一位的上限在 BB 内，那么它只能加上 00，并成为 xx 在这一位的上限；否则，xx 在这一位的上限一定不在 AA 里。所以：
Ci,0=∑B0(3∣B0∣−2i−1)C_{i,0}=\sum\limits_{B_0}(3^{|B_0|}-2^{i-1})
Ci,1=∑B1(3∣B1∣−1×1−2i−2)C_{i,1}=\sum\limits_{B_1}(3^{|B_1|-1}\times1-2^{i-2})
如果 xx 在 n−in-i 位为 11：
如果 xx 在上一位的上限在 BB 内，那么它可以只加 00 不成为上限，或加上 11 成为上限；否则，xx 在这一位的上限一定不在 AA 里。所以：
Ci,0=∑B0(3∣B0∣−2i−1+∑B13∣B1∣−1×1−2i−2)C_{i,0}=\sum\limits_{B_0}(3^{|B_0|}-2^{i-1}+\sum\limits_{B_1}3^{|B_1|-1}\times1-2^{i-2})
Ci,1=∑B1(3∣B1∣−1×2i−2)C_{i,1}=\sum\limits_{B_1}(3^{|B_1|-1}\times 2^{i-2})
但是转移中有 3∣B∣3^{|B|} 状的东西，很难处理，于是可以设 Gx,i,0/1G_{x,i,0/1} 表示 ∑Bi,0/1x∣Bi,0/1∣\sum\limits_{B_{i,0/1}}x^{|B_{i,0/1}|}。
前面 3∣B∣3^{|B|} 意思是每个 xx 可以对应 2x/2x+12x/2x+1，加入一个元素，两种方案,以及而 xx 对应 2x,2x+12x,2x+1，加入两个元素，一种方案，所以应该改成：∑j=0∣B∣(∣B∣j)xj+2(∣B∣−j)×2j=(∣B∣j)(2x)j×(x2)∣B∣−j=(2x+x2)∣B∣\sum\limits_{j=0}^{|B|}\binom{|B|}{j}x^{j+2(|B|-j)}\times2^{j}=\binom{|B|}{j}(2x)^{j}\times(x^2)^{|B|-j}=(2x+x^2)^{|B|}。
其它形如 3∣B∣−1×1,3∣B∣−1×23^{|B|-1}\times1,3^{|B|-1}\times2 的式子也类似地修改，则得到转移式：
若上限 xx 的 n−in-i 位为 00：
Gx,i,0=Gx2+2x,i−1,0−2i−1Gx,i−1,0G_{x,i,0}=G_{x^2+2x,i-1,0}-2^{i-1}G_{x,i-1,0}
Gx,i,1=Gx2+2x,i−1,1×xx2+2x−2i−2Gx,i−1,1G_{x,i,1}=G_{x^2+2x,i-1,1}\times\frac{x}{x^2+2x}-2^{i-2}G_{x,i-1,1}
若上限 xx 的第 n−in-i 位为 11：
Gx,i,0=Gx2+2x,i−1,0−2i−1Gx,i−1,0+Gx2+2x,i−1,1×xx2+2x−2i−2Gx,i−1,1G_{x,i,0}=G_{x^2+2x,i-1,0}-2^{i-1}G_{x,i-1,0}+G_{x^2+2x,i-1,1}\times\frac{x}{x^2+2x}-2^{i-2}G_{x,i-1,1}
Gx,i,1=Gx2+2x,i−1,1×x2+xx2+2x−2i−2Gx,i,1G_{x,i,1}=G_{x^2+2x,i-1,1}\times\frac{x^2+x}{x^2+2x}-2^{i-2}G_{x,i,1}
令 a0=1,ai=ai−12+2ai−1a_0=1,a_i={a_{i-1}}^2+2a_{i-1}，Fx,i,0/1=Gax,i,0/1F_{x,i,0/1}=G_{a_x,i,0/1}，则总状态数 O(n2)O(n^2)，直接递推即可。
最后答案就是 G1,n,0+G1,n,1=F0,n,0+F0,n,1G_{1,n,0}+G_{1,n,1}=F_{0,n,0}+F_{0,n,1}，记得除以 22。
Sol 写了快 1h（（（

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 2010,mod = 998244353;
int n,m,cnt,ans,id[N],X[N],lim[N],a[N],inv[N],mi[N],f[N][N][2];
char ch[N];
bitset <N> v,p[N];
bool check(bitset <N> v)
{
    for(int i = m - 1;i >= 0;i--) if(v[i] != X[i]) return (v[i] < X[i]);
    return true;
}
int ksm(int x,int y)
{
    int ret = 1;
    while(y)
    {
        if(y & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod,y >>= 1;
    }
    return ret;
}
int main()
{
    freopen("basis.in","r",stdin);
    freopen("basis.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",ch + 1);
        for(int j = 1;j <= m;j++) v[m - j] = ch[j] - '0';
        for(int j = m - 1;j >= 0;j--)
        {
            if(!v[j]) continue;
            if(!p[j].count())
            {
                p[j] = v;
                break;
            }
            v ^= p[j];
        } 
    }
    scanf("%s",ch + 1);
    for(int i = 1;i <= m;i++) X[m - i] = ch[i] - '0';
    memset(id,-1,sizeof(id));
    for(int i = 0;i < m;i++)
    {
        if(!p[i].count()) continue;
        id[i] = cnt++;
        for(int j = i + 1;j < m;j++) if(p[j][i]) p[j] ^= p[i];
    }
    v = 0;
    for(int i = m - 1;i >= 0;i--)
    {
        if(id[i] == -1) continue;
        if(check(v ^ p[i])) v ^= p[i],lim[id[i]] = 1;
    }
    if(!lim[n - 1])
    {
        puts("0");
        return 0;
    }
    a[0] = 1;
    for(int i = 1;i <= n;i++) a[i] = (1LL * a[i - 1] * a[i - 1] + 2 * a[i - 1]) % mod;
    for(int i = 0;i <= n;i++) inv[i] = ksm(a[i],mod - 2);
    for(int i = 0;i <= n;i++) f[i][1][1] = (1LL * a[i] * a[i] + a[i]) % mod;
    mi[0] = 1;
    for(int i = 1;i <= n;i++) mi[i] = 2 * mi[i - 1] % mod;
    for(int i = 2;i <= n;i++)
        if(!lim[n - i])
            for(int j = 0;j <= n - i;j++)
            {
                f[j][i][0] = (f[j + 1][i - 1][0] - 1LL * mi[i - 1] * f[j][i - 1][0] % mod + mod) % mod;
                f[j][i][1] = (1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * a[j] % mod - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
            }
        else
            for(int j = 0;j <= n - i;j++)
            {
                f[j][i][0] = (f[j + 1][i - 1][0] - 1LL * mi[i - 1] * f[j][i - 1][0] % mod + mod) % mod;
                f[j][i][0] = (f[j][i][0] + 1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * a[j] % mod) % mod;
                f[j][i][0] = (f[j][i][0] - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
                f[j][i][1] = 1LL * f[j + 1][i - 1][1] * inv[j + 1] % mod * (1LL * a[j] * a[j] % mod + a[j]) % mod;
                f[j][i][1] = (f[j][i][1] - 1LL * mi[i - 2] * f[j][i - 1][1] % mod + mod) % mod;
            }
    ans = 1LL * (f[0][n][0] + f[0][n][1]) * (mod / 2 + 1) % mod;
    printf("%d\n",ans);
    return 0;
}

C.树上邻邻域数点

题意：

交互题。给一棵大小为 nn 的树和常数 LL，每个点有一个权值 ai∈[0,32)a_i\in[0,32)。每次可以询问 (x,d,v)(x,d,v)，表示距离 xx 恰好为 dd 的点中，ai≤va_i\le v 的点数，要求 d≥Ld\ge L。
n=50000,L≤2n=50000,L\le 2，要求至多 250000250000 次询问确定每个点的权值。保证树不是菊花。

Sol：

在值域上分治，每次确定 ai∈[l,r]a_i\in[l,r] 的点与 midmid 的关系（可以看作 0/10/1），不在分治区间内或已确定的点可以忽略掉。
考虑从下往上确定，如果一个点有孙子，则在孙子处问 d=2d=2 即可。
考虑其它情况。设这个点为 xx，xx 的爷爷为 ff，ff 的父亲为 tt，tt 的父亲为 gg。
考虑一次处理出 gg 子树内和 x,fx,f 同一层的所有点。
先处理有兄弟的 xx。
如果 ff 的值确定了，则询问 xx 和它的所有兄弟 d=2d=2 的答案，如果值有两种，则较小的为 11，较大的为 00；否则全部的值都一样，根据总和和 ff 判断即可。
如果 ff 没确定，上面的方法也几乎可行，除了一种特殊情况：xx 只有一个兄弟 yy，且两个查询的结果都是 11，此时有 f=1,x=y=0f=1,x=y=0 和 f=0,x=y=1f=0,x=y=1 两种情况。
如果 ff 子树内有没有兄弟的 xx，直接问 (x,2)(x,2) 即可。其它情况，发现如果能求出 ff 的所有这类孙子（下称特殊点）的和就好了，这个等于 (f,2)(f,2)，减去 ff 的所有兄弟和 gg 的值。如果 ff 的所有兄弟和 gg 都已经确定，后者可以直接得到；否则，先问一次 (t,2)(t,2)，然后把 ff 的所有兄弟和 gg 中未确定的全部确定。注意到 ff 所有特殊点的和一定是偶数，而把减去“ff 的所有兄弟和 gg 的值”改成减去 (t,2)(t,2)，最多会多减去 11，因此不会影响判断。
然后处理没有兄弟的 xx。可以用 (x,4)(x,4) 和 (f,2)(f,2) 差分一下得到。
精细实现可以做到刚好 nlog⁡Vn\log V 次，参考代码。

Code：

CPP
#include <bits/stdc++.h>
#include "tree.h"
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
typedef pair <int,int> pii;
namespace WORK
{
	const int N = 50010;
	int n,rt,dep[N],a[N],b[N],fa[N],p[N],d[N][5];
	vector <int> v[N];
	bool cmp(int x,int y){return dep[x] < dep[y];}
	void dfs1(int x,int lst)
	{
		dep[x] = dep[lst] + 1;
		for(int y : v[x]) if(y != lst) dfs1(y,x);
	}
	void dfs2(int x,int lst)
	{
		dep[x] = dep[fa[x] = lst] + 1;
		if(lst) v[x].erase(find(v[x].begin(),v[x].end(),lst));
		for(int y : v[x]) dfs2(y,x);
	}
	int qry(int x,int d,int v){return ask(x - 1,d,v);}
	void upd(int x,int v)
	{
		b[x] = v;
		for(int i = 0;i <= 4;i++) d[x][i] += v,x = fa[x];
	}
	void work1(int x,int sum,int tg,int mid)
	{
		for(int y : v[x])
		{
			vector <int> w;
			for(int z : v[y]) if(b[z] == -1) w.pb(z);
			if(w.size() == 1)
			{
				int z = w[0],c = qry(z,2,mid) - d[z][2] - d[y][1];
				upd(x,c);
				return ;
			}
		}
		vector <int> k;
		for(int y : v[x])
		{
			vector <int> w;
			for(int z : v[y]) if(b[z] == -1) w.pb(z);
			int m = (int)w.size();
			if(!m) continue;
			vector <int> C(m);
			int c1 = -1,c2 = -1;
			for(int i = 0;i < m;i++)
			{
				C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[y][1];
				if(c1 == -1) c1 = C[i];
				if(c1 != C[i]) c2 = C[i];
			}
			if(c2 != -1)
			{
				if(c1 > c2) swap(c1,c2);
				for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
			}
			else if(m > 2 || c1 != 1)
				for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
			else k.pb(w[0]),k.pb(w[1]);
		}
		if(!tg && !k.size())
			for(int y : v[x])
				if(v[y].size())
				{
					int z = v[y][0];
					upd(x,qry(z,2,mid) - d[z][2] - d[y][1] + d[z][0]);
					return ;
				}
		int c = qry(x,2,mid) - d[x][2] - sum;
		for(int i : k) upd(i,c > -tg);
		upd(x,c <= -tg);
	}
	void work2(int x,int sum,int mid)
	{
		vector <int> k;
		for(int y : v[x])
		{
			vector <int> w;
			for(int z : v[y]) if(b[z] == -1) w.pb(z);
			int m = w.size();
			if(!m) continue;
			if(m == 1)
			{
				k.pb(w[0]);
				continue;
			}
			vector <int> C(m);
			int c1 = -1,c2 = -1;
			for(int i = 0;i < m;i++)
			{
				C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[y][1] - d[x][0];
				if(c1 == -1) c1 = C[i];
				if(c1 != C[i]) c2 = C[i];
			}
			if(c2 != -1)
			{
				if(c1 > c2) swap(c1,c2);
				for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
			}
			else for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
		}
		if(!k.size()) return ;
		int c = qry(x,2,mid) - d[x][2] - sum;
		for(int i : k)
			if(i == k.back()) upd(i,c);
			else
			{
				int tmp = qry(i,4,mid) - d[i][4] - d[fa[i]][3] + d[i][2] - d[x][2] + d[fa[i]][1] - sum;
				tmp = c - tmp,upd(i,tmp),c -= tmp;
			}
	}
	void solve(int l,int r)
	{
		if(l == r) return ;
		int mid = (l + r) / 2;
		memset(d,0,sizeof(d));
		for(int i = 1;i <= n;i++)
			if(a[i] < l || a[i] > r) upd(i,a[i] < l);
			else b[i] = -1;
		for(int i = n;i >= 1;i--)
		{
			int x = p[i];
			if(b[x] != -1) continue;
			for(int y : v[x])
				if(v[y].size())
				{
					int z = v[y][0];
					upd(x,qry(z,2,mid) - d[z][2] - d[y][1] + d[z][0]);
					break;
				}
			if(b[x] != -1) continue;
			int f = fa[fa[x]],t = fa[f],g = fa[t];
			vector <int> k;
			for(int i : v[t]) if(i != f && b[i] == -1) k.pb(i);
			if(b[g] == -1) k.pb(g);
			int sum = 0;
			if(k.empty())
			{
				sum = b[g];
				for(int i : v[t]) if(i != f) sum += b[i];
				if(b[f] == -1) work1(f,sum,0,mid);
				sum += b[f];
			}
			else
			{
				sum = qry(f,2,mid);
				for(int u : v[f])
				{
					vector <int> w;
					for(int s : v[u]) if(b[s] == -1) w.pb(s);
					if(w.empty()) continue;
					int m = w.size();
					if(m == 1)
					{
						int s = w[0],c = qry(s,4,mid) - d[s][4] - d[u][3] + d[s][2];
						upd(s,sum - d[u][1] - c);
						continue;
					}
					int c1 = -1,c2 = -1;
					vector <int> C(m);
					for(int i = 0;i < m;i++)
					{
						C[i] = qry(w[i],2,mid) - d[w[i]][2] - d[u][1] - d[f][0];
						if(c1 == -1) c1 = C[i];
						if(c1 != C[i]) c2 = C[i];
					}
					if(c2 != -1)
					{
						if(c1 > c2) swap(c1,c2);
						for(int i = 0;i < m;i++) upd(w[i],C[i] == c1);
					}
					else if(m > 2 || c1 != 1 || b[f] != -1)
						for(int i = 0;i < m;i++) upd(w[i],c1 >= m - 1);
					else
					{
						int s = w[0],c = qry(s,4,mid) - d[s][4] - d[u][3] + d[s][2];
						c = sum - d[u][1] - c,upd(s,c > 0),upd(w[1],c > 0),upd(f,!c);
					}
				}
				if(b[f] == -1) upd(f,qry(x,2,mid) - d[x][2] - d[fa[x]][1] + d[x][0]);
				sum += b[f] - d[f][2];
				for(int i : k)
					if(i == k.back())
					{
						int c = sum;
						for(int j : v[t]) if(i != j) c -= b[j];
						if(i != g) c -= b[g];
						upd(i,c);
					}
					else work1(i,sum,1,mid);
			}
			for(int i : v[t]) work2(i,sum - b[i],mid);
			if(!t) work2(f,0,mid);
		}
		for(int i = 1;i <= n;i++) if(l <= a[i] && a[i] <= r) a[i] = (b[i] ? l : r);
		solve(l,mid),solve(mid + 1,r);
	}
	vector <int> tree(int N,vector <pii> E,int M,int L)
	{
		n = N;
		for(pii p : E) v[p.fi + 1].pb(p.se + 1),v[p.se + 1].pb(p.fi + 1);
		dfs1(1,0);
		for(int i = 1;i <= n;i++) if(dep[i] > dep[rt]) rt = i;
		dfs2(rt,0);
		for(int i = 1;i <= n;i++) p[i] = i;
		sort(p + 1,p + n + 1,cmp);
		solve(0,31);
		vector <int> ret;
		for(int i = 1;i <= n;i++) ret.pb(a[i]);
		return ret;
	}
}
vector <int> tree(int N,vector <pii> E,int M,int L){return WORK :: tree(N,E,M,L);}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...