被安利来做这套题。

backlight

Prob.

给一堆朝向左或右的花,花上有灯。关掉一盏灯会使当前花休眠,并且所有醒着的能看到这灯的花好感度减一。求失去的好感度的最小值。

Sol.

记朝右为(,朝左为),要使失去最小,可以发现相对位置为))...)或者((...(的从右往左或者从左往右关即可保证对答案无贡献。所有贡献来自于()的对数。(容易发现关闭顺序无关贡献)
(个数前缀和即可。

Code

不存在的。

issac

Prob.

一个点指向且仅指向另一个点,可以发出技能毁掉指向的点,被毁掉的点失去技能。
攻击顺序随意。问最多和最少被毁掉的点。

Sol.

基环外向树。
环里面最多毁剩1个,最少毁一半上取整,也可以直接贪心。
树部分最多毁剩叶子,最少从底层向上贪心攻击。

Code

不存在的。

endless

Prob.

一棵有根树每个点都有一个特定的数和其数量。询问每一棵子树的众数及其值。

Sol.

对每个点维护一个值域线段树,子树所有线段树合并即得答案。
从叶子往上边走边合并,最多合并$ O(n) $次,每次$ O(\lg m) $,复杂度仍然是$ O(n\lg m) $。


区间众数由于其不满足 additive 及 associative,换句话说所要求的信息不构成群的性质,故其不能用权值线段树高效维护。一般情况考虑分块。有空写份总结。分块做法十分显然。可以参考 CLJ 的论文。复杂度带根号,在这道题不是十分优秀。


标解是分治,我选择拒绝。
以常数上的牺牲换取思路上的绝对简单。
唯一的瓶颈在于空间开销及递归的栈开销。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 4e5 + 5;
int n, m;
struct N{int l, r, v, num;} T[maxn * 30];
int root[maxn], tc = 1;
void merge(int &o, int p, int L = 1, int R = m)
{
    if(!p) return;
    if(!o){o = p; return;}
    if(L == R) {T[o].v += T[p].v; return;}
    int M = (L + R) >> 1;
    merge(T[o].l, T[p].l, L, M); merge(T[o].r, T[p].r, M + 1, R);
    if(T[T[o].l].v >= T[T[o].r].v) T[o].v = T[T[o].l].v, T[o].num = T[T[o].l].num;
    else T[o].v = T[T[o].r].v, T[o].num = T[T[o].r].num;
}
int x, v;
void modify(int &o, int L = 1, int R = m)
{
    if(!o) o = tc++;
    if(L == R) {T[o].v += v, T[o].num = x; return;}
    int M = (L + R) >> 1;
    if(x <= M) modify(T[o].l, L, M);
    else modify(T[o].r, M + 1, R);
    if(T[T[o].l].v >= T[T[o].r].v) T[o].v = T[T[o].l].v, T[o].num = T[T[o].l].num;
    else T[o].v = T[T[o].r].v, T[o].num = T[T[o].r].num;
}
struct E{int v, n;} e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
int a[maxn], b[maxn];
void dfs(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        dfs(v, u), merge(root[u], root[v]);
    x = a[u], v = b[u], modify(root[u]);
    a[u] = T[root[u]].num, b[u] = T[root[u]].v;
}
int main()
{
    freopen("endless.in", "r", stdin);
    freopen("endless.out", "w", stdout);
    read(n, m);
    for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v), add_edge(v, u);
    for(int i = 1; i <= n; ++i) read(a[i], b[i]);
    dfs();
    for(int i = 1; i <= n; ++i) printf("%d %d\n", a[i], b[i]);
    return 0;
}

标签: segment tree, greedy, tree, mathematics, mode

添加新评论