[Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated]-D. Kuroni and the Celebration（交互题+树的性质） This is an interactive problem. After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess ...

[AtCoder Beginner Contest 151] E - Max-Min Sums（预处理组合数学，贡献） Problem Statement For a finite set of integers XX, let f(X)=maxX−minXf(X)=maxX−minX. Given are NN integers A1,...,ANA1,...,AN. We will choose KK of them and let SS be the set of the integers chosen. If we distinguish elements with diffe...

牛客练习赛58 F-XOR TREE（结论+树链剖分+线段树） 链接：https://ac.nowcoder.com/acm/contest/4090/F来源：牛客网 XOR TREE 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 ​ 给出一颗n{n}n个结点n−1{n-1}n−1条边的带权树，第i{i}i个结点的权值为aia_{i}ai 。 ​ 定义点u{u}u到点v{v}v的路径的长度为点u{u}u到点v{v}v的最短路径上的所有结点的权值的异或和。 ​ 单...

牛客练习赛58 F-XOR TREE（结论+树链剖分+线段树） 链接：https://ac.nowcoder.com/acm/contest/4090/F 来源：牛客网 XOR TREE 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 ​ 给出一颗n{n}n个结点n−1{n-1}n−1条边的带权树，第i{i}i个结点的权值为aia_{i}ai 。 ​ 定义点u{u}u到点v{v}v的路径的长度为点u{u}u到点v{v}v的最短路径上的所有结点的权值的异或和。 ​ 单独一个...

AtCoder Beginner Contest 152 - F - Tree and Constraints （容斥定理+树上路径的性质） We have a tree with NN vertices numbered 11 to NN. The ii-th edge in this tree connects Vertex aiai and Vertex bibi. Consider painting each of these edges white or black. There are 2N−12N−1 such ways to paint the edges. Among th...

[Codeforces Round #622 (Div. 2)] - C2. Skyscrapers (hard version) （单调栈） C2. Skyscrapers (hard version) time limit per test 3 seconds memory limit per test 512 megabytes input standard input output standard output This is a harder version of the problem. In this version n≤500000n≤500000 Th...

2018牛客国庆集训派对Day1 D-Love Live! （01字典数+树上启发式合并/静态链分治） 链接：https://ac.nowcoder.com/acm/contest/201/D 来源：牛客网 Love Live! 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1048576K，其他语言2097152K 64bit IO Format: %lld 题目描述 因为招生办的招生政策变化，Otonokizaka Academy的ACM-ICPC team面临废队危机。Honoka Kosaka,Kotori Minami,Umi Sonoda等人决定成为偶像...

[Codeforces Round #620 (Div. 2)] E. 1-Trees and Queries time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea f...

AtCoder Beginner Contest 155 - D - Pairs ，-E - Payment 题解 D - Pairs We have NN integers A1,A2,...,ANA1,A2,...,AN. There are N(N−1)2N(N−1)2 ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the KK-th numb...

AtCoder Beginner Contest 155 - D - Pairs ，-E - Payment 题解 D - Pairs We have NN integers A1,A2,...,ANA1,A2,...,AN. There are N(N−1)2N(N−1)2 ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the KK-th n...

[Educational Codeforces Round 82 (Rated for Div. 2)] D. Fill The Bag （二进制拆分，贪心） D. Fill The Bag time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You have a bag of size nn. Also you have mm boxes. The size of ii-th box is aiai, wh...

C++ 开3次方根方法 \(y=\sqrt[3]{x}=x^{\frac{1}{3}}\) 又因为y与x同符号（同正负），所以应该这样写： double poww(double x, double y) { if (x < 0) { return -pow(-x, y); } else { return pow(x, y); } }

树状数组 进阶篇：区间修改，区间查询 单点更新，区间查询 我们知道，树状数组最基本的功能是 单点更新，区间查询 代码如下： int lowbit(int x) { return x & (-x); } void add(int x, int val) { while (x <= n) { tree[x] += val; x += lowbit(x); } } int ask(int x) { int res = 0; while (x) { res += tree[x]; ...

树状数组 进阶篇：区间修改，区间查询 单点更新，区间查询 我们知道，树状数组最基本的功能是 单点更新，区间查询 代码如下： int lowbit(int x) { return x & (-x); } void add(int x, int val) { while (x <= n) { tree[x] += val; x += lowbit(x); } } int ask(int x) { int res = 0; while (x) { res += tree[x]...