Fat Old Eight's Blog

题目描述 给⼀棵树，现在有两种操作： 标记某⼀个节点； 找到路径 $a$ 至 $b$ 中在第 $y$ 次操作到当前操作之间没有被标记的第 $k$ 个节点。 保证每个节点只会被标记一次。 完整题面 思路 首先用可持久化线段树维护树剖，对于修改操作直接修改即可，对于查询，直接在树剖上跳，如果未标记节点小于 $k$ 输出 -1，否则输出答案。 实现 这道题个人认为最大的... Read More

数论全家桶？ 题意描述 完整版 简单版： 给定 $g,n(g,n\le10^9)$，求 $g^{\sum_{d\mid n}{C_{n}^{d}}} \mod{999911659} $。 做法 首先根据欧拉定理推出： $$ g^{\sum_{d\mid n}{C_{n}^{d}}} \equiv g^{\sum_{d\mid n}{C_{n}^{d}}\mod{999911658}} (\bmod{99... Read More

前因 今天端午放假，明天返校，一般来说，今天怎么说都会出勤，但是考虑到以往清明、五一出勤的经验，今天肯定很多人，所以不如不去。于是在洛谷犇犇上面发了一句： 不出意外明天會直播寫UVA12421，主要明天可能會沒事干 然后，不出意外地，出意外了，主要是舟太好玩了，然后有两把都寄在第六... Read More

题意 题目链接 给定两颗结点数为 $n$ 的树 $T1$ 和 $T2$，定义 $dis(T,x,y)$ 表示在树 $T$ 上 $x$ 到 $y$ 的路径上所有边的权值和。 现在求 $\forall x \in [1,n] , \min\limits_{1\le y\le n,x\neq y}dis(T1,x,y)+dis(T2,x,y)$。 一道相当好的题。 此题 $O(n\log^2{n... Read More

其实谈不上学习笔记。 在谈平衡树之前，我们需要知道一种二叉树： 二叉查找树（BST） 性质 二叉查找树满足一种性质，即对于该树上的任意一个节点： 该节点的权值不小于它左子树上所有节点的权值。 该节点的权值不大于它右子树上所有节点的权值。 显然一颗 BST 的中序遍历就是一个权值非严格单调递增的节点序列。 在一颗 BST 上面，可以实现 插入、删除、查找排名、查找第 ... Read More

写在前面 因为本人太菜，所以大部分东西都只有结论，没有证明。 以及如果真的想学习网络流的话，建议去看OI Wiki。 概述 一个网络 $G=(V,E)$ 是一张有向图，图中每一条边都有一个给定的权值 $c(x,y)$，称为边的容量，特别地，若 $(x,y)\notin E$，则 $c(x,y)=0$。图中还有两个特殊点，$S\in V$ 和 $T\in V(S\ne ... Read More

题意描述 链接 实现插入、删除、查找排名、查找第 $k$ 大、查找前驱、后继。 很明显的平衡树，但是这里我介绍一种非常规做法——分块。 虽然是 $n\sqrt{n}$ 做法，但是依据数据范围还是可以过的。 做法 首先我们需要处理一个难点：插入。因为一般的分块都是根据数组来实现，所以仅仅是插入就需要 $O(n)$ 的时间复杂度，并且会给维护带来一定的麻烦，这是所不能允许的。 所以需要上另外一种数据... Read More

很早就想写的东西，最近才有时间写。主要是不想改错 树状数组 支持维护前缀和或者是前缀最大值之类的东西，支持单点修改。 基本只有维护前缀才会想到这个，其余的情况用线段树替代。 Code int c[N],n; int ask(int x) { int ans=0; for(;x;x-=lowbit(x))ans+=c[x]; return ans; } void add(int x,in... Read More

喏 你知道的太多了 Read More