为了去隔壁给 talk，不得不又重温了本作 = =。

• 游戏说 99：我只负责调酒，不负责拯救世界

我觉得要是游戏也和隔壁 NeurIPS 一样，发时间检验奖（Test-of-Time Award）的话，一个评判标准我觉得大概得是这个游戏是否引领了很多 xxx-like，那按照这个标准 rogue 是必然能上榜的，《银河战士》和《恶魔城月下夜想曲》大概也能的！

在调研了一番之后，很神奇的是我觉得《赛博行动酒保行动》后续也有很多酒保行动-like 的！

首先我觉得本作的设计在一个 game jam 体量的作品里还是非常特别的！你说它是模拟经营吧，不能说没有但是怎么看也不如今年爆红的《沙威玛传奇》，这个游戏绝对是 AI 游戏的代表作了，哈哈玩法我觉得是那种经典古早 flash 游戏，最后一看人家作者还真写 flash（什么，《沙威玛传奇》都能玩出竞速模式吗？）。

你说它是 galgame 吧，hmmm，它居然连对话选项都没有，但分支剧情又都是通过调酒玩法和经营的分数去触发的，这点又类似《仙剑客栈》那样的传统模拟经营了。

我觉得整体氛围最接近显然是 Coffee Talk 系列，虽然背景设定类似《奥秘：蒸汽与魔法》那样有点偏奇幻。

然后同样赛博朋克世界观下的有《红弦俱乐部》以及之前在游机会玩到的《爱&机器人维修技术》。

居然还有这么多联动。。。
– 如何评价少女前线与VA-11 Hall-A赛博朋克酒保行动的联动活动？
– 赛博朋克酒保行动和赛博朋克红究竟联动了啥？（特别节目）【夜之城求生指南】

由于最近在填坑，所以刚好记录一下剧情。

（剧透警告!）

剧情

首先感觉两部的核心除了尼克和朱迪这一对 cp 的性格和阵营上的冲突，还有一个是如何维护 Zootopia 的 DEI（尽管这好像是一个被用坏掉了的词），第一部是肉食动物与草食动物之间，第二部则是哺乳动物和爬行动物之间。

故事开场利用了一场马里奥赛车一样的追逐戏快速的让我进入了状态，并且通过留下的蛇皮也制造了十足的悬念。使得我开始期待一个梅兰妮或是神偷卡门那样的展开，可结果光速发生第一次剧情上的反转，此时朱迪和尼克的阵营上的冲突也开始显现，尼克作为混乱中立显然不想掺和进去，而朱迪作为守序善良自然要贯彻自己 make the world a better place 的信念自然不惜深入险境。

不过我这里感觉是这个翻转比隔壁阿兹卡班的囚徒还要快，凭借蛇蛇的一面之词朱迪的立场就光速翻转，还险些害死了 Chief Bogo！接下来就进入死亡圣器的逃亡环节，朱迪像 cyberpunk 2077 里流浪者阵营一样开始了大逃亡，经过一个神似长弓溪谷坠机之地的水上集市（但是人很多）的地方之后，来到了一个有点像元组星球大战那样的地下酒吧，然后莫名其妙任务道具就丢了。中间一段踩河马脑袋的演出真的就像这类3D平台跳跃游戏的解谜一样，前面甚至还有铺垫的，你肯定在奥德赛 or 古惑狼里遇到过类似的关卡。

钻管子的演出也让人感觉有点梦回超级马里奥大电影。然后尼克就被抓了，说实话我要是朱迪这个时候我肯定已经后悔自责的要死了，第一要务肯定是去救尼克，而不是信任这个蛇蛇。不过尼克遇到了神仙队友居然这么轻易的就越狱成功了。

话说这只竹叶青居然叫 garry，ib 里的 garry 也恰好代表色是蓝色。

然后第二波翻转我方小队里迅速的出现了一个内鬼，说实话我一开始还以为蛇蛇和这个猞猁是 cp 关系，然后上演一场出类似隔壁叙拉古人那样对家族的反抗的剧情，结果居然跳反了？不过这期反派实在战斗力不太行，被有惊无险的光速击败了。

女性主义

回来的路上 m200 说到，尼克在本作不就是一般意义上的女主位置么。确实，不过这种创作手法也不是第一次见到了，最经典的例子可能就是《空之轨迹FC》里的艾丝蒂尔和约修亚了吧。然后尼克本作完全就是宠妻狂魔，朱迪感觉完全就像是少根筋的直男似的，拜托我都没你这么焦虑！也就是你是迪士尼童话故事的主角不然感觉中间我们都死好几次了都。

• 逗比的预言家，这款19年前的游戏为何能一战成名？带你笑着看完神作《空之轨迹》
• 游戏说 27：电子游戏与性别歧视

上面这个视频居然没提到寄生前夜的女主 Aya，她可是我小时候玩过的觉得印象最深刻的女主角了，可能原因之一是她除了要和 boss 作战，还要面对来自身体内部线粒体内部的对抗与挣扎。

总之我觉得本作无论是对女性主义，对 DEI，对刻板印象的反击（神话、寓言故事里蛇通常是邪恶的）都处理的非常自然，感觉比《冰雪奇缘》还要棒！（除了没有女同）

先把所有数都减一，n 表示进行了 n 个回合。

设 E[i] 为最后 i 出现的期望次数。那么显然 E[n] 最容易求，就是每次都 p，E[0] 也容易求，每个回合的 delta 只与当前有多少个 0 有关，看起来可以递推。
E[n-1] 则需要讨论一下，E[n-2] 就更要讨论了。

仔细观察，我们发现不得不枚举第一次出现 i 的时刻，设 A[i][j] 等于 i 第一次出现在 j 时刻的概率，我们有：

E[i] = A[i][j] B[n-j] | j = 0..n

这里 B[i] 表示当前最高位后续再进行 i 个回合期望出现多少次，和求 E[0] 类似，这个值只与后续进行的回合数有关！

进一步，考察 A[i][j]，最后第 j 时刻必然是 p 事件，前面二项分布即可：

A[i][j] = C(j-1, i-1) p^i (1-p)^(j-i)

考察 B[i] 有：

B[0] = 1
B[i] = B[i-1] + B[i-1] / n-i

于是可以得到暴力 O(n2) dp。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;

const int N = 1009;
Int Fact[N], iFact[N];
Int E[N], A[N], B[N];
int n, p, q;

Int Binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return Fact[n] * iFact[m] * iFact[n-m];
}

int main(){
    MOD = 998244353; RD(n, p); p = Int(p) / 100; q = Int(1) - p;
    Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;
    iFact[n] = _I(Fact[n]); DWN_1(i, n, 1) iFact[i-1] = iFact[i] * i;
    B[0] = 1; FOR(i, 1, n) B[i] = B[i-1] * (q+n-i) / (n-i);

<pre><code>E[0] = B[n-1]; FOR(i, 1, n) {
    FOR(j, i, n) E[i] += Binom(j-1, i-1) * pow(p, i) * pow(q, j-i) * B[n-1-j];
}

REP(i, n) printf(&amp;quot;%d\n&amp;quot;, E[i]);
</code></pre>

}

再卷积即可。

题意：次小素因子前缀和。

类似 PE 521 求最小素因子前缀和，虽然不是积性函数，但不妨碍我们筛。

令 S(n, k) 表示次小质因子 >= P[k] 时的前缀和（P[0] = 0)。
转移，分两种情况：
1. 剩余部分是一个更大的素数，贡献是，p * (g[id(n)] – g[p])。
2. 枚举最小因子分解，递归。

#include <lastweapon/io>
using namespace std;

const int N = int(1e6) + 9;
LL n; int nn; int P[N], Pn;
LL di[N], g[N]; int dn;
inline int id(LL x) {return x <= nn ? x : dn-n/x+1;}

LL S(LL n, int k) {
    int p = P[k]; if (n <= p) return 0;
    LL z = p * (g[id(n)] - g[p]);
    FOR_1(i, k+1, Pn) {
        LL p = P[i]; if (p*p > n) break;
        for (LL j=n/p;j>=p;j/=p) {
            z += S(j, i) + p;
        }
    }
    return z;
}

LL S(LL n) {
    ::n = n; nn = sqrt(n); Pn = dn = 0;
    for (LL i=1,j;i<=n;i=j+1) {
        di[++dn] = j = n/(n/i);
        g[dn] = j-1;
    }
    FOR_1(p, 2, nn) if (g[p] != g[p-1]) {
        P[++Pn] = p; for (LL i=dn,ii=di[i];(LL)p*p<=ii;ii=di[--i]) {
            g[i] -= g[id(ii/p)] - g[p-1];
        }
    }
    if (!Pn) return 0;
    return S(n, 0);
}

int main(){
    LL l, r; RD(l, r);
    cout << S(r) - S(l-1) << endl;
}

• https://uoj.ac/problem/164

Kimi 居然会做这个题的暴力 https://kimi.moonshot.cn/share/cvaqfgsjc3febjghkqh0，
除了一些细节问题（欧姆定律和电阻公式实际不需要，要开 long long），实际能拿 40 分！

然后注意到本题的这个区间减操作，是不能减成负值的（AI 居然也能注意到？），所以我们还需要支持区间最值操作，而区间赋值操作是可以用区间最值模拟的，具体说来我们需要维护一个双半群，标记合并是：

struct F{LL a0, b0, a1, b1;};
F comp(F r, F l) {
    return F{
        max(l.a0+r.a0,-INFF),
        max(l.b0+r.a0, r.b0),
        max(l.a1,l.a0+r.a1),
        max(l.b1,l.b0+r.a1,r.b1)
    };
}

注意这里历史标记需要当前标记的信息来维护，所以不能开两个线段树分别维护。

https://uoj.ac/submission/745579

• Codeforces, The history of some recurring problem
• Luogu P6292 区间本质不同子串个数
• https://uoj.ac/problem/608
• https://www.fzoi.top/problem/4449

初见杀，实际套路，应该放一起做！

首先能离线当然考虑离线（Ukkonen 可以魔改支持左删，但是好像还是不能很好的支持左加和右删，否则我们甚至能莫队？），
那么我们只要维护一个线段树记录询问左端点在不同位置的答案，考察增加操作对线段树的影响，发现只影响 fail 树向上的节点，最后一步动态树优化即可，复杂度 O(nlog2n + mlogn)。

和 BZOJ_2555 相比，这里由于我们不需要强制在线，动态树不需要在后缀自动机插入字符时候跟随 SAM 变化形态，只需要在全部插入完后根据 fail 树构建即可，因而也可以树链剖分啊启发式合并啊替代动态树的环节。

具体来看，先考察 Luogu P6292 区间本质不同子串个数，每次添加新字符时，先把所有位置都加 1，然后类似 dquery 一题的搞法，我们记录上次添加的时刻以去掉重复计数的部分，而这只需要沿着 fail 树向上，并记录每个状态上次计数的时刻即可。这里的线段树只需要支持区间加减，区间求和，因而也可以用树状树组替代。

观察这里的动态树这里其实唯一的用处就只有压缩 fail 树 = =，我们只需要维护上次访问的标记即可，其它信息都可以从 SAM 中拿到，因为 Splay 之后父节点和自己刚好形成压缩后的 endpos 区间。

fzoi 那枚只需要把线段树从区间加常数变成加等差数列。再看 uoj 608，这里我们线段树需要支持的是区间等差数列 checkMax，由于这个标记是单调的，所以可以简单标记持久化，动态树同样只起到压缩 fail 树的功能，完全不用改！

Problem E. I Hate Sigma Problems

询问区间不同元素数目有各种经典离线和函数式线段树做法，但是这个题要统计整体，直接上数据结构复杂度反而不太对。
我们可以单独统计每种元素对答案的贡献，而这个只要计算其补集即可，复杂度 O(n)。
https://atcoder.jp/contests/abc371/submissions/57884316

Problem G. Lexicographically Smallest Permutation

原题等价于求字典序最小的 AP^x，由于 P 是个排列，显然可以只考察它的循环分解。我们从左到右贪心的确定 AP^x 的每一位以及打包得到其所在的循环所有位置的结果，按顺序考察每一组这样的循环。我们总能得到一组形如 x = r (mod c) 的限制，这里的 c 是循环的长度，我们要在贪心结果尽可能小的同时，不破坏之前得到的所有限制条件。

我们可以合并这些条件，计算所有这些 c 形成的 lcm，但是这样这个 lcm 可能会特别大。注意到我们并不需要计算具体的 x，并且对于所有互素的 c，显然这些限制是不互相影响的，这提醒我们只需要考察和更新所有 c 的因子所形成的限制条件，进一步我们只需要维护所有素数幂的限制即可。
https://atcoder.jp/contests/abc371/submissions/57872303

旧约

说来惭愧，我最早是从某本软件工程的书里了解到的巴别塔这个典故的（因为我毕竟真的是软件工程系嘛。。。我系的经典作品还是要读一下的！虽然我更喜欢理论但是毕竟 math 太鶸 = =。。）那本书自然就是 —— 《人月神话》了。当然，那本书的角度，是认为交流导致信任的缺失、而信任的缺失进而导致工程的失败，和原本的命题 —— 人类是无法相互理解的，关联并不大。

直到今天我依然十分喜欢那本书的各种隐喻的，无论是焦油坑还是巴别塔，但是那本书的结论，放在今天依然成立吗？
这似乎是要打个问号的，面向对象自然不是，开源软件也有一些问题，区块链嘛当然也不够成熟、但今天我们还有 llama3 呢！

新约

所以前段时间偶然读到《二次元手游与萌文化的歧路》那篇文章的时候，起初我并没有十分理解，囫囵吞枣的就翻过去了 —— 这也容易解释，我是杂食动物，主机、PC、二游、同人、黄油、链游… 就没有我不涉猎的。但我毕竟没有深入的玩过原神（太肝了的就不是我的菜），也不玩社区，所以那篇文章里很多东西读的云里雾里。

但是随着最近麻辣仙人的这波攻势，使得很多原本文章里的观点，变得不言自明了。= = （不愧是先知啊！）

• 【没补档】史黄色精英论坛是如何通过循环论证批量生产谣言的
• 【吐槽向】麻辣人是如何扰乱社区的

作为一个杂食动物，其实我很多时候还是无法理解麻辣仙人的逻辑 —— 为什么我们不去玩《兰斯》系列，或者《ドーナドーナ》？珀尔诺她的身体难道不更香吗… 一些分析尝试解答上面的问题，它们认为：

1. 麻辣仙人与其说玩游戏，不如说玩的是社区。
2. 麻辣仙人享受自己受害人的身份。
3. 麻辣仙人的诉求不在于二次元纸片人ml，而是要让所有厂商和其他玩家对自己ml。

这也是区分麻辣仙人和 ml 玩家的核心 criteria。

「你们为什么胆怯？」

当然，按照歧路先知的观点，我们不应该再继续挖掘下去了 —— 因为再继续看下去就要有害身心健康了 —— 但是越是这样反而越令人好奇，毕竟人类就是这样，好奇心害死猫。另一方面这一群体居然现在是如此的庞大，使得我们不得不去解构背后的原理和成因了。我们不禁要问，造成这一切的原点是什么？简单的用巴别塔的隐喻来说明似乎是远远不够的。。。

那么我的观点是，原点就是这个！随着时间的演变，用今天流行的话来说，就是 —— 引天雷。

单纯从战术层面上说，这个肯定是一个高级技巧，很多作品里的角色都有引天雷的技能，最符合字面的例子可能是《火影忍者》里的雷遁麒麟，佐助在和鼬决战的时候用这招打掉鼬一条命。其次想到的是《三国杀》里的张角、还有司马懿也都可以通过改判定的方式 literally 引天雷。btw 张角在《三国志11》里直接就有妖术和落雷，但那是主动技所以不算～一定要利用环境才算～比如最近的一些《魔兽争霸3》单侍僧挑战电脑（令人发狂的）的视频里利用野怪坑死电脑英雄的战术就比较符合这种设定。

• 【魔兽争霸3】 挑战发狂电脑下限的新世界纪录

当然我们这里的情况 —— 无论它的表现形态是审查制度、取消文化还是政治正确 —— 这个天雷可要比上面的野怪甚至《沙丘》里的沙虫都要强大太多，可能更类似《三体》里的引力波发射器囧。。。

威慑纪元

公設一：人需要安全感。
公設二：人想要優越感。
安全感對應「生存」，優越感對應「發展」。當然，感覺不等於事實，安全感不等於安全，優越感不等於優越；這是很淺顯的道理，但大多數人都難免掉到坑裡，也都會有意無意地運用感覺與事實的錯位來自欺欺人、誤國誤民。當前世界政治的主要問題與通行答案，就是在和這個心魔共舞。
—— Hu Youtien

与开源软件让世界上的每个人类都变得更加富足相反，赛博叫魂让参与和不幸卷入其中的每个人都变得更加的贫乏了。然而遗憾的，这似乎和《三体》里所描述的黑暗森林法则一样，是一个不得不面对和接受的可悲现状，避无可避。

纠其根源也许是 yet another 关于优越感的议题？无论什么时代，能够无拘无束的创作，总归是一件些许奢侈之事 …

所以主张建立巴别塔的特蕾西娅死了，穷极一生致力于追寻人魔共存之道的壶中仙也死了，mean while 杀害魔族最多的芙莉莲却好好的活着。
由此可见，巴别塔是注定要失败的，能有小宇宙、不、能守住一方天书世界就不错了 —— 要么巴别塔在工程上彻底失败，要么最后搞不好变成了心灵终结仪啊、无限月读啊或者别的什么的奇怪的东西。
当然以目前的状况来看，能否抵御这些或来自外部或来自内部的侵蚀，在源石枯竭后保存住来亚什基的遗产，都也还要打一个大大的问号呢。

test

The function is_square(n) typically checks if a given number [ n ] is a perfect square.

TBD

Problem E. Tenzing and Triangle

只要能写出暴力 dp 就成功了 90% 啦！

不妨先把所有点都加起来，考虑最优能通过覆盖节省多少。我们发现一个有用的性质是，三角形覆盖的区域，是不需要重叠的，因此似乎可以简单的 1D/1D 动态规划。

这里我们用树状数组，可以维护出三角形覆盖区域的代价。

#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(2e5) + 9;
int n, k, A; vector<PII> P[N]; LL f[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif


	RD(n,k,A); LL z = 0;
	REP(i ,n) {
	    int x, y, c; RD(x, y, c);
	    z += c; P[k-x].PB({y, c});
	}

	fenwick_tree<int> T(k+1);

	REP(i, k+1) {
        for (auto p: P[i]) T.add(p.fi, p.se);
        checkMax(f[i], (LL)T.sum(0, i+1) - A*i);
        REP(j, i) checkMax(f[i], f[j] + T.sum(j+1, i+1) - A*(i-j-1));
	}

	cout << z - f[k] << endl;
}

进一步的我们再把这个转移分离分离放到线段树里求 rmq 就好了。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e5) + 9;
const int NN = 4*N;
int n, k, A; vector<PII> P[N]; int f[N];

struct SegTree {
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
#define rt 1,0,k

    int T[NN], D[NN];

    void add(int x, int d) {
        D[x] += d;
        T[x] += d;
    }
    void rls(int x) {
        //return;
        if (D[x]) {
            add(lx, D[x]);
            add(rx, D[x]);
            D[x] = 0;
        }
    }
    void upd(int x) {
        T[x] = max(T[lx], T[rx]);
    }
    void Build(int x, int l, int r) {
        if (l == r) {
            T[x] = A*l;
        } else {
            Build(lc);
            Build(rc);
            upd(x);
        }
    }

    int Add(int x, int l, int r, const int p, const int d) {
        if (l == r) {
            T[x] += d;
        } else {
            rls(x);
            if (p < mr) Add(lc, p, d);
            else Add(rc, p, d);
            upd(x);
        }
    }

    void Add(int x, int l, int r, const int a, const int b, const int d) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            add(x, d);
        } else {
            rls(x);
            Add(lc, a, b, d);
            Add(rc, a, b, d);
            upd(x);
        }
    }

    int Query(int x, int l, int r, const int a, const int b) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) {
            return T[x];
        } else {
            rls(x);
            return max(Query(lc, a, b), Query(rc, a, b));
        }
    }
} T;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif


	RD(n,k,A); int z = 0; REP(i, n) {
	    int x, y, c; RD(x, y, c); z += c;
	    P[k-x].PB({y, c});
	}

	T.Build(rt);

	REP(i, k+1) {
	    if (i) T.Add(rt, i, f[i-1]);
        for (auto p: P[i]) T.Add(rt, 0, p.fi, p.se);
        checkMax(f[i], T.Query(rt, 0, i) - A*i);
	}

	cout << z - f[k] << endl;
}