会议选址

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

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

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

但是每走一个点要查询一遍它的所有子树,如果给个菊花图的话还是会被卡成单次 O(n)O(n),我们可以用三度化来使每个点的度数最大为 33 ,保证时间复杂度是 O(nlog2n)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 需要记录 n2n^2 个状态,显然无法接受。

考虑是浮点数输出,只需要保证 44 位的精度,我们可以将大于 5050 的数的出现概率近似看为 00

然后进行一个 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,j) 走到了 (i+1,j)(i+1,j),那么这一步会使总答案加上 rest_step(ai+1ai)rest\_step * (a_{i+1} - a_i) ,我们在某个格子选择向右走或向下走其实就是选择 ai+1aia_{i+1}-a_ibj+1bjb_{j+1}-b_j,也就是在选择差分值,因为题目保证数列 a,ba,b 的差分是严格单调上升的,所以我们在每个格子选择一个差分值小的方向走即是最优解。(感性理解一下就是因为差分严格单调上升,即使这一步选择一个较大的差分值走,后面也不会有更优的方案来补回来这一步的花费)

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

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

#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);
}
}