2022-9-28总结

会议选址

有一个很显然的贪心: 先随便选一个点，然后往它子树里会减小答案的方向走，走到最后一定是最优点。

维护这个步骤我们需要在一棵子树内查询编号在 $[l,r]$ 内的点的个数，这个可以用 dfs 序和主席树实现。

但是如果树是一条链的话会被卡成单次 $O(n)$ 询问，所以可以用树分治保证树高是 $\log n$ 级别的。

但是每走一个点要查询一遍它的所有子树，如果给个菊花图的话还是会被卡成单次 $O(n)$，我们可以用三度化来使每个点的度数最大为 $3$ ，保证时间复杂度是 $O(n \log^2 n)$ 的。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int SIZE = 1e5 + 10;
 
struct EDGE {
    int v, nxt;
} edge[SIZE << 1];
int head[SIZE], cnt;
 
void add_edge(int u, int v)
{
    edge[++cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
 
struct Query {
    int p, u, id, op;
    Query(int p = 0, int u = 0, int id = 0, int op = 0) : p(p), u(u), id(id), op(op) {}
    bool operator<(const Query& b) const
    {
        return p < b.p;
    }
};
 
namespace HLD {
 
int siz[SIZE], deep[SIZE], fa[SIZE], hson[SIZE];
int top[SIZE], dfn[SIZE], rnk[SIZE], tot;
 
void dfs1(int u, int dep)
{
 
    siz[u] = 1;
    deep[u] = dep;
 
    for(int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if(deep[v]) continue;
        dfs1(v, dep + 1);
        fa[v] = u;
        siz[u] += siz[v];
        if(siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
 
void dfs2(int u, int t)
{
 
    top[u] = t;
    dfn[u] = ++tot;
    rnk[tot] = u;
 
    if(hson[u])
        dfs2(hson[u], t);
 
    for(int i = head[u]; i; i = edge[i].nxt)
        if(edge[i].v != fa[u] && edge[i].v != hson[u]) dfs2(edge[i].v, edge[i].v);
}
 
int LCA(int a, int b)
{
 
    while(top[a] != top[b])
    {
        if(deep[top[a]] < deep[top[b]]) swap(a, b);
        a = fa[top[a]];
    }
    return deep[a] < deep[b] ? a : b;
}
 
void prework()
{
 
    dfs1(1, 1);
    dfs2(1, 1);
}
 
} // namespace HLD
using namespace HLD;
 
namespace HJT {
 
struct Laffey {
 
    int ls, rs;
    int cnt;
 
#define ls(i) (tree[i].ls)
#define rs(i) (tree[i].rs)
 
} tree[SIZE << 5];
int root[SIZE], postot;
 
void add(int nl, int nr, int s, int last, int& i, int k)
{
 
    i = ++postot;
    tree[i] = tree[last];
    tree[i].cnt += k;
 
    if(nl == nr) return;
    int mid = (nl + nr) >> 1;
    if(s <= mid)
        add(nl, mid, s, ls(last), ls(i), k);
    else
        add(mid + 1, nr, s, rs(last), rs(i), k);
}
 
int query(int nl, int nr, int l, int r, int p, int q)
{
 
    if(nl >= l && nr <= r) return tree[q].cnt - tree[p].cnt;
    int mid = (nl + nr) >> 1;
    int sum = 0;
    if(mid >= l) sum += query(nl, mid, l, r, ls(p), ls(q));
    if(mid + 1 <= r) sum += query(mid + 1, nr, l, r, rs(p), rs(q));
    return sum;
}
 
#undef ls
#undef rs
 
} // namespace HJT
using namespace HJT;
 
namespace SegmentTree {
 
struct Laffey {
 
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
 
    int l, r;
    int sum, add;
 
    Laffey(int l = 0, int r = 0, int sum = 0, int add = 0) : l(l), r(r), sum(sum), add(add) {}
 
    int len() { return r - l + 1; }
 
} tree[SIZE << 2];
 
void push_up(int i)
{
 
    tree[i].sum = tree[ls(i)].sum + tree[rs(i)].sum;
}
 
void update(int i, int k)
{
 
    tree[i].sum += tree[i].len() * k;
    tree[i].add += k;
}
 
void push_down(int i)
{
 
    if(!tree[i].add) return;
    update(ls(i), tree[i].add);
    update(rs(i), tree[i].add);
    tree[i].add = 0;
}
 
void build(int l, int r, int i)
{
 
    tree[i].l = l, tree[i].r = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, ls(i));
    build(mid + 1, r, rs(i));
}
 
void add(int l, int r, int i, int k)
{
 
    if(tree[i].l >= l && tree[i].r <= r)
    {
        update(i, k);
        return;
    }
    push_down(i);
    if(tree[ls(i)].r >= l) add(l, r, ls(i), k);
    if(tree[rs(i)].l <= r) add(l, r, rs(i), k);
    push_up(i);
}
 
int query(int l, int r, int i)
{
 
    if(tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
    push_down(i);
    int sum = 0;
    if(tree[ls(i)].r >= l) sum += query(l, r, ls(i));
    if(tree[rs(i)].l <= r) sum += query(l, r, rs(i));
    return sum;
}
 
#undef ls
#undef rs
 
} // namespace SegmentTree
using namespace SegmentTree;
 
int f[20][SIZE], pre[SIZE];
int ans[SIZE];
vector<Query> q;
int main()
{
 
    int n, m;
    cin >> n >> m;
 
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
 
    HLD::prework();
    SegmentTree::build(1, n, 1);
 
    for(int i = 1; i <= n; i++)
        f[0][i] = fa[i], pre[i] = pre[i - 1] + deep[i];
    for(int i = 1; i <= 19; i++)
        for(int j = 1; j <= n; j++)
            f[i][j] = f[i - 1][f[i - 1][j]];
 
    for(int i = 1; i <= n; i++)
        HJT::add(1, n, rnk[i], root[i - 1], root[i], 1);
 
    for(int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        int L = 1, R = n;
        int goal = r - l + 1;
        while(R - L > 0)
        {
            int mid = (L + R) >> 1;
            if(goal <= HJT::query(1, n, l, r, root[0], root[mid]) * 2)
                R = mid;
            else
                L = mid + 1;
        }
        int u = rnk[R];
        for(int j = 19; j >= 0; j--)
            if(f[j][u] && query(1, n, l, r, root[dfn[f[j][u]] - 1], root[dfn[f[j][u]] + siz[f[j][u]] - 1]) * 2 < goal)
                u = f[j][u];
        if(HJT::query(1, n, l, r, root[dfn[u] - 1], root[dfn[u] + siz[u] - 1]) * 2 <= goal) u = fa[u];
        ans[i] = pre[r] - pre[l - 1] + (r - l + 1) * deep[u];
        q.emplace_back(l - 1, u, i, 2), q.emplace_back(r, u, i, -2);
    }
 
    sort(q.begin(), q.end());
 
    int now = 0;
    for(auto v : q)
    {
        while(now < v.p)
        {
            now++;
            int u = now;
            while(u)
            {
                SegmentTree::add(dfn[top[u]], dfn[u], 1, 1);
                u = fa[top[u]];
            }
        }
        int u = v.u;
        while(u)
        {
            ans[v.id] += v.op * SegmentTree::query(dfn[top[u]], dfn[u], 1);
            u = fa[top[u]];
        }
    }
 
    for(int i = 1; i <= m; i++)
        cout << ans[i] << endl;
 
    return 0;
}

Combining Slimes

CF618G

直接 DP 需要记录 $n^2$ 个状态，显然无法接受。

考虑是浮点数输出，只需要保证 $4$ 位的精度，我们可以将大于 $50$ 的数的出现概率近似看为 $0$。

然后进行一个 DP 的做就 OK 了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef double db;
typedef long long ll;
const int N = 55;

namespace Matrix {
    struct matrix {
        double a[N][N];
        matrix() { memset(a, 0, sizeof(a)); }
        double& operator() (int x, int y) { return a[x][y]; }
    };
    matrix operator * (matrix a, matrix b)
    {
        matrix c;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    c(i,j) += a(i,k)*b(k,j);
        return c;
    }
    matrix qpow(matrix a, ll b)
    {
        matrix ans;
        for(int i = 0; i < N; i++)
            ans(i,i) = 1;
        for(; b; b >>= 1, a = a*a)
            if(b&1) ans = ans*a;
        return ans;
    }
}
using namespace Matrix;

int n; db p;
db f[N][N];
db a[N][N], A[N][N];
db b[N][N], B[N][N];
matrix F, G;

void prework();

int main()
{
    cin >> n >> p; p /= 1e9;
    prework();
    
    if(n <= 50)
    {
        db ans = 0;
        for(int i = 1; i <= n+1; i++)
            ans += f[n][i]*A[n][i];
        cout << setpcs(15) << ans;
    }
    else
    {
        F(0,0) = G(0,0) = 1;
        for(int i = 1; i <= 50; i++)
            F(0,i) = f[50][i];
        
        db sum = 0;
        for(int i = 2; i <= 50; i++)
        {
            G(i,1) += B[50][i];
            sum += B[50][i];
        }
        for(int i = 2; i <= 50; i++)
            G(i,1) /= sum;
        
        G(0,1) = 1;
        for(int i = 2; i <= 50; i++)
        {
            sum = 0;
            for(int j = 1; j < i; j++)
            {
                G(j,i) += A[50][j];
                sum += A[50][j];
            }
            for(int j = 1; j < i; j++)
                G(j,i) /= sum;
            G(0,i) = i;
        }
        
        F = F*qpow(G, n-50);
        db ans = 0;
        for(int i = 1; i <= 50; i++)
            ans += F(0,i)*A[50][i];
        cout << setpcs(18) << ans;
    }
}

void prework()
{
    a[1][1] = p;
    a[1][2] = 1-p;
    b[1][2] = 1-p;
    for(int i = 2; i <= 50; i++)
    {
        a[i][1] = p;
        a[i][2] = 1-p+p*p;
        b[i][2] = 1-p;
        for(int j = 3; j <= 50; j++)
        {
            a[i][j] = a[i][j-1]*a[i-1][j-1];
            b[i][j] = b[i][j-1]*a[i-1][j-1];
        }
    }
    for(int i = 1; i <= 50; i++)
        for(int j = 1; j <= 50; j++)
        {
            A[i][j] = a[i][j]*(1-a[i-1][j]);
            B[i][j] = b[i][j]*(1-a[i-1][j]);
        }
    f[1][1] = 1, f[1][2] = 2;
    for(int i = 2; i <= 50; i++)
    {
        db sum = 0;
        for(int j = 2; j <= 50; j++)
        {
            f[i][1] += f[i-1][j]*B[i-1][j];
            sum += B[i-1][j];
        }
        f[i][1] = 1 + f[i][1]/sum;
        for(int j = 2; j <= 50; j++)
        {
            sum = 0;
            for(int k = 1; k < j; k++)
            {
                f[i][j] += f[i-1][k]*A[i-1][k];
                sum += A[i-1][k];
            }
            f[i][j] = j+f[i][j]/sum;
        }
    }
}

A Stroll Around the Matrix

CF1609G

考虑拆开每一步的贡献，设从 $(i,j)$ 走到了 $(i+1,j)$，那么这一步会使总答案加上 $rest\_step * (a_{i+1} - a_i)$ ，我们在某个格子选择向右走或向下走其实就是选择 $a_{i+1}-a_i$ 或 $b_{j+1}-b_j$，也就是在选择差分值，因为题目保证数列 $a,b$ 的差分是严格单调上升的，所以我们在每个格子选择一个差分值小的方向走即是最优解。（感性理解一下就是因为差分严格单调上升，即使这一步选择一个较大的差分值走，后面也不会有更优的方案来补回来这一步的花费）

所以我们最终答案就是将 $a,b$ 的差分数组 $da,db$ 求出来，然后一块排序，得到一个长度为 $n+m-2$ 的数组 $d$，最终答案就是 $(a_1+b_1)*(n+m-1) + \sum\limits _{i=1}^{n+m-2} (n+m-i-1)*d_i$

但是不能每次都把差分数组求出来，考虑 $n \le 100$ 但 $m \le 10^5$，我们可以用线段树维护 $db$ ，然后把 $da$ 数组挨个插入 $db$，这个可以用线段树二分找出位置，然后就可以统计答案了。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 105;
const int M = 1e5+10;

int n, m, q;
ll a[N], b[M];
ll d[N+M];
ll bans, a1, b1;

namespace tree {
    struct node {
        int l, r;
        ll sum, min, lz;
    } a[M*4];
    ll *data;
    void build(int l, int r, int i = 1);
    void add(int ql, int qr, ll val, int i = 1);
    ll query(int ql, int qr, int i = 1);
    int getpos(ll val, int i = 1);
}

ll solve();

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i], a[i-1] = a[i]-a[i-1];
        if(i == 1) a1 = a[i];
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> b[i], b[i-1] = b[i]-b[i-1];
        if(i == 1) b1 = b[i];
    }

    tree::data = b; b[0] = 0;
    tree::build(0, m-1);

    for(int i = 1; i <= m-1; i++)
        bans += (n+m-1-i)*b[i];

    int opt, k, d;
    for(int i = 1; i <= q; i++)
    {
        cin >> opt >> k >> d;
        if(opt == 1)
        {
            for(int i = max(n-k,1); i <= n-1; i++)
                a[i] += d;
            if(k == n) a1 += d;
        }
        else
        {
            tree::add(max(m-k,1), m-1, d);
            int kk = min(k,m-1);
            bans += (ll)d*(n*2+kk-1)*kk/2;
            if(k == m) b1 += d;
        }
        cout << solve() << "\n";
    }
}


ll solve()
{
    ll ans = bans;
    for(int i = 1; i <= n-1; i++)
    {
        int p = tree::getpos(a[i]);
        int pos = p+i;
        ans += (n+m-1-pos)*a[i];
        if(p < m-1) ans -= tree::query(p+1, m-1);
    }
    return ans+(a1+b1)*(n+m-1);
}

namespace tree {
    #define ls (i<<1)
    #define rs (i<<1|1)
    inline void add(node &i, ll val)
    {
        i.sum += val*(i.r-i.l+1);
        i.min += val;
        i.lz += val;
    }
    inline void pushup(int i)
    {
        a[i].sum = a[ls].sum + a[rs].sum;
        a[i].min = min(a[ls].min, a[rs].min);
    }
    inline void pushdown(int i)
    {
        add(a[ls], a[i].lz);
        add(a[rs], a[i].lz);
        a[i].lz = 0;
    }
    void build(int l, int r, int i)
    {
        a[i].l = l, a[i].r = r;
        if(l == r)
        {
            a[i].sum = data[l];
            a[i].min = data[l];
            return void();
        }
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
        pushup(i);
    }
    void add(int ql, int qr, ll val, int i)
    {
        if(ql <= a[i].l && a[i].r <= qr)
            return add(a[i], val);
        pushdown(i);
        if(ql <= a[ls].r) add(ql, qr, val, ls);
        if(qr >= a[rs].l) add(ql, qr, val, rs);
        pushup(i);
    }
    ll query(int ql, int qr, int i)
    {
        if(ql <= a[i].l && a[i].r <= qr)
            return a[i].sum;
        pushdown(i); ll ans = 0;
        if(ql <= a[ls].r) ans += query(ql, qr, ls);
        if(qr >= a[rs].l) ans += query(ql, qr, rs);
        return ans;
    }
    
    // stop learning useless algorithms,
    // go and solve some problems,
    // learn how to use binaysearch
    int getpos(ll val, int i)
    {
        if(a[i].l == a[i].r)
            return a[i].l;
        pushdown(i);
        if(a[rs].min < val)
            return getpos(val, rs);
        else
            return getpos(val, ls);
    }
}