主要思路

这道题的\(w\)很大，且要求出二维和。一种可行的办法就的是嵌套数据结构，第一想法是树状数组套线段树动态开点，时间复杂度为\(O(log^2 m)\)。但是空间依旧很大，可以发现线段树空间庞大，可以考虑替换为平衡树，空间极大减小，且时间复杂度不变。

进一步优化可以考虑对下标进行哈希。

思路

显然需要树链剖分。

对于每一个 \(a \times dis + b\) 的操作，向懒惰标记里添加。如果碰上已经有懒惰信息，那么我们只需要把这样的操作理解为加上直线，把直线下边缘下传到左右子节点即可。（计算长度进行左右决策下传）对于每一个节点，懒惰加法为等差数列求和，计算 \(b \times subtreeSize + a \times \frac{subtreeSize*(subtreeSize-1)}{2}\)。

「APIO2012」派遣题解

思路

可并堆思路：自顶向上做大根堆，然后弹出堆顶直到整个堆的和小于 m。（性质：父亲节点不会选择子树不包含的忍者）。

线段树合并思路：没看懂，不写了。

代码

// P1552.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int MAX_N = 100100;
struct node
{
    int lson, rson;
    ll dist;
} nodes[MAX_N];
ll n, m, li[MAX_N], ci[MAX_N], master, ans = -2e9;
ll sum[MAX_N], siz[MAX_N], pt[MAX_N];
vector<int> G[MAX_N];
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (ci[x] < ci[y])
        swap(x, y);
    nodes[x].rson = merge(nodes[x].rson, y);
    if (nodes[nodes[x].lson].dist < nodes[nodes[x].rson].dist)
        swap(nodes[x].lson, nodes[x].rson);
    nodes[x].dist = nodes[nodes[x].rson].dist + 1;
    return x;   
}
void dfs(int u)
{
    sum[u] = ci[u], siz[u] = 1, pt[u] = u;
    int siz_ = G[u].size();
    for (int i = 0; i < siz_; i++)
    {
        int to = G[u][i];
        dfs(to);
        sum[u] += sum[to], siz[u] += siz[to];
        pt[u] = merge(pt[u], pt[to]);
    }
    while (sum[u] > m && siz[u])
    {
        sum[u] -= ci[pt[u]];
        pt[u] = merge(nodes[pt[u]].rson, nodes[pt[u]].lson);
        siz[u]--;
    }
    ans = max(ans, li[u] * siz[u]);
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        ll fa;
        scanf("%lld%lld%lld", &fa, &ci[i], &li[i]);
        if (fa == 0)
            master = i;
        else
            G[fa].push_back(i);
    }
    dfs(master);
    printf("%lld", ans);
    return 0;
}

我之前把数据结构搞复杂了，看了题解发现好简洁。还是要做减法啊。

复活

嘿嘿不用退役了。

记在期末考试和退役之前

···二是严格制定录取标准，高校在现有基础上进一步降低给予自主招生考生的优惠分值。三是严格控制招生规模，高校在上一年录取人数基础上适度压缩招生名额。

人生真的好难啊。

今天下午 PKUWC 2019 和 THUWC 2019 的签约结果就会发布，尽管这跟我这个蒟蒻无关。但是在新政发布之后，这两个比赛的签约结果意味着之后竞赛生自主招生的政策走向，直接决定我是否退役。光凭一腔热血完全不够，功利化的因素仍然需要放在第一位。

这三个星期，我一直都泡在文化课的学习上，除了偶尔想想 crazydave 给的神仙题之外，没有怎么碰 OI。期末考试很重要，由于对于上一次考试翻车，这一次必须要证明自己的脑子是没有问题的。

可能真的要对 OI 说再见了，尽管我不知道为什么我们这个地区的年轻人要活的这么累。

文化课啊，我颓爆

文化课好像比较简单

学了两个月的 OI 感觉整个人智商回到了平均水平，回附中之后感觉文化课相对于 OI 那些什么毒瘤的虚树之类的要容易得多。看了一些书把一些基本的知识补了回来，但是没做题还是非常的亏。

没做题吃亏主要体现在生物、化学和数学上（对基本上全炸，物理不知道为什么现在还行，跟大佬比肯定菜的一笔），之后就安排搞课外书和作业，在两个星期内整个进度都跟上了。不过还是做不到每个科目做 2 本课外书…这个真的做不到。

还剩下一周，准备周六通宵颓选择题，周日写大题…提高速度才是坠吼的。感觉需要有人陪我一起肝才行，指不定就睡着了。

但是难啊

文化课并不考察人的智力，而是考察熟练程度。要把有一点落下的 6 门瞬间补起来还是比较困难的，况且我的 OI 也落下了很多。面对新的政策，这一段时间只能这样了。只能眼睁睁看着别人在属于神仙的天上遨游。

Kalorona

BZOJ1176:「Balkan2007」Mokia 题解