A. 博弈
首先考虑什么样的数列可以使先手必胜，可以发现若该数列最大值只出现一次，那么先手选择那个最大值即可获胜，若最大值出现两次，先选择到最大值的人失败。以此类推，若最大值出现奇数次，那么先手必胜，否则谁先选择到最大值谁必败。
所以我们考虑将序列按值分层，层与层之间按值降序排列，然后从大到小考虑每层，若该层的个数为偶数，那么先选择到这一层的人失败，发现先选择到这一层与在后面的层中无法选择等价，即与在不考虑该层的情况下胜负情况相同，所以可以消去。若遇到大小为奇数的层，那么先手从这一层开始选择，显然无论后手如何操作均必胜。
所以我们可以得出先手获胜的充要条件，即存在数字在序列中出现次数为奇数次，由于偶数次可以消去，发现其与异或运算的性质相似，故可以考虑统计路径异或和。
接下来我们的就面临着两个子问题，如何统计异或和合如何增加正确率。
发现如果直接将边权异或起来的话是很容易构造数据使其得出错误结果的，例如一条链，其边权依次为 \(1, 2, 3, 0\)。所以我们需要对边权进行哈希，当然还有一种更简便的方法，建立一个 map，将每种边权映射至一个在较大值域范围内均匀生成的整数。值得一提的是，大多数基于异或的哈希（例如 xor_shift）在本题中正确性均会错误。
接下来便是如何统计异或和，如果使用点分治的话显然是无法通过 \(5 \times 10^5\) 的数据的，我们可以再次利用异或的消去性，发现对于路径 \(u \rightarrow v\) 的异或和等于 \(u\) 到根的路径异或和与 \(v\) 到根的路径异或和，所以使用一个桶统计每种到根的路径异或和出现次数即可。
B. 跳跃
首先考虑一个 \(\mathcal{O}(n^2k)\) 的 \(\tt{DP}\)，设 \(f_{i, j}\) 代表跳跃 \(i\) 次后到达点 \(j\) 的最大价值，转移是显然的，需要注意题目要求任何时刻权值非负。
注意，下文所述的方法在
HZOI的测试数据中已经无法通过，对应的 \(\tt{Hack}\) 数据为 \(\tt{ex1.in}\)，还有剩余两组 \(\tt{Hack}\) 数据分别卡掉了前缀和错误做法（见牛客讨论区）和不注意任何时刻权值非负的做法（都是我造的）。
我们发扬人类智慧，可以发现在最后的大多数跳跃都会是在这个序列的最大子段和的两个端点间反复横跳，我们其实要做的事最大化从起点到任意一个和最大的区间的端点的权值，所以我们可以将所有端点预处理出来，当走到端点的时候更新答案。由于第一次走到端点可能不是最优情况，所以我们判断在第 \(100\) 次走到端点后直接退出寻找即可。
C. 大陆
原题 SCOI2005 王室联邦。
构造方法较为简单：维护一个栈，从根节点向下进行 \(\tt{DFS}\)，若有一个节点其子树在递归完成后使得栈中元素增加了超过 \(B\) 个，那么把增加的部分取出作为一个省，省会为当前节点，否则存在栈中向上递归，最后把栈中的剩余部分划入最后一个省即可（不新增省）。
考虑其正确性，显然每个省的城市数量一定满足大于等于 \(B\) 的条件，可能会冲突的条件为每个省最多 \(3B\) 个城市，我们发现每次递归结束后栈中元素一定小于 \(B\) 个，在根节点递归后，栈中元素最多剩余 \(B\) 个（\(B - 1\) 个来源为子树，\(1\) 个为根节点），总量最多 \(2B\) 个，满足要求。
D. 排列
由于存在移位拼接操作，所以考虑使用 \(\tt{FHQ-Treap}\) 维护序列。
首先考虑一个弱化的问题：是否存在全局二元上升子序列，发现在每次合并子树是结合左子树最小值，当前节点权值和右子树最大值即可判断。
下面考虑类似的情况，类比上面的问题，我们可以维护一个 \(pmax\) 和一个 \(pmin\) 分别代表子树内的二元上升子序列的较大值的最小值和子树内二元上升子序列的较小值的最大值，合并时维护 \(\tt{tag}\) 即可。
如果一个节点 \(\tt{tag}\) 为 \(\tt{true}\)，那么可能有如下来源：
- 从左子树继承
- 从右子树继承
- 左子树 \(pmin\) 小于根节点 \(value\)
- 左子树 \(pmin\) 小于右子树 \(max\)
- 右子树 \(pmax\) 大于根节点 \(value\)
- 右子树 \(pmax\) 大于左子树 \(min\)
- 左子树 \(min\) 小于根节点 \(value\) 且根节点 \(value\) 小于右子树 \(max\)
上述条件满足任意一条即可，条数繁多的原因主要是要考虑到根节点 \(value\) 的贡献，例如最后一条。
下面重点讨论如何维护 \(pmax\) 和 \(pmin\)，下文中以 \(pmax\) 为例。发现在合并子树后，当前节点的 \(pmax\) 来源有下：
- 从左子树继承
- 从右子树继承
- 左子树贡献较小值，右子树或根节点贡献较大值。
前两条的维护是平凡的，下面着重讨论如何维护第三个来源，注意到若当前子树 \(\tt{tag}\) 为 \(\tt{true}\)，那么根节点的 \(\tt{tag}\) 也为 \(\tt{true}\)，所以我们只需要在 \(\tt{tag}\) 为 \(\tt{false}\) 时维护 \(pmax\) 和 \(pmin\)。
考虑利用上 \(\tt{tag}\) 为 \(\tt{false}\) 的条件，即当前子树内不存在三元上升子序列，那么可以得出左子树内小于右子树和根节点中的较小值的所有元素一定单调递减，否则会产生三元上升子序列，与上述不符。
所以我们可以在左子树中递归寻找小于右子树和根节点中的较小值的最大元素，由于其单调递减，所以在递归过程中只要节点左子树内最小值小于给定阈值即右子树和根节点中的较小值的最大元素那么就可以向左子树递归否则检查当前节点和右子树，这一过程和给定排名查询值类似。
Code
A
//A
#include<bits/stdc++.h>
typedef long long valueType;
typedef unsigned long long hashType;
typedef std::vector<hashType> HashVector;
typedef std::map<hashType, valueType> HashTable;
typedef std::pair<valueType, hashType> Edge;
typedef std::vector<Edge> EdgeVector;
typedef std::vector<EdgeVector> EdgeMatrix;
typedef std::vector<bool> bitset;
typedef std::vector<valueType> ValueVector;
constexpr valueType MAX = std::numeric_limits<valueType>::max();
const hashType mask = std::chrono::system_clock::now().time_since_epoch().count() ^ 0xc0ffeec0ffee ^
(std::chrono::system_clock::now().time_since_epoch().count() >> 10);
valueType N, ans;
HashTable table;
EdgeMatrix G;
typedef std::mt19937_64 Engine;
void dfs(valueType x, valueType from, hashType const &depth);
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
Engine engine(mask);
for (int testcase = 0; testcase < T; ++testcase) {
table.clear();
G.clear();
N = 0;
ans = 0;
std::cin >> N;
G.resize(N + 1);
std::map<hashType, hashType> edgeTable;
for (int i = 1; i < N; ++i) {
valueType a, b;
hashType w;
std::cin >> a >> b >> w;
if (!edgeTable.count(w))
edgeTable[w] = engine();
w = edgeTable[w];
G[a].emplace_back(b, w);
G[b].emplace_back(a, w);
}
dfs(1, -1, 0);
for (auto const &iter: table)
ans += iter.second * (iter.second - 1) / 2;
ans = N * (N - 1) / 2 - ans;
std::cout << ans << std::endl;
}
std::cout << std::flush;
return 0;
}
void dfs(valueType x, valueType from, hashType const &depth) {
++table[depth];
for (auto const &iter: G[x]) {
if (iter.first == from)
continue;
dfs(iter.first, x, depth ^ iter.second);
}
}
B
//B
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
constexpr valueType MAX = std::numeric_limits<valueType>::max() >> 2, MIN = std::numeric_limits<valueType>::min() >> 2;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N, K;
std::cin >> N >> K;
ValueVector A(N + 1, 0);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i];
ValueVector S(N + 1, 0);
std::partial_sum(A.begin(), A.end(), S.begin());
valueType minPrefix = 0, leftBound = 0, rightBound = 0;
for (valueType i = 1; i <= N; ++i) {
if (S[i] - S[minPrefix] > S[rightBound] - S[leftBound - 1]) {
leftBound = minPrefix + 1;
rightBound = i;
}
if (S[i] < S[minPrefix])
minPrefix = i;
}
valueType maxSum = S[rightBound] - S[leftBound - 1];
ValueMatrix F(2, ValueVector(N + 1, MIN));
F[0][1] = 0;
valueType ans = 0;
for (valueType times = 1; times <= std::min(K, (valueType) 1000); ++times) {
valueType const now = times & 1, pre = now ^ 1;
std::fill(F[now].begin(), F[now].end(), MIN);
if (now == 0) {
for (valueType i = 1; i <= N; ++i) {
for (valueType j = i; j <= N; ++j)
if (F[pre][j] + S[j] - S[i - 1] >= 0)
F[now][i] = std::max(F[now][i], F[pre][j] + S[j] - S[i - 1]);
if (i == leftBound)
ans = std::max(ans, F[now][i] + maxSum * (K - times));
ans = std::max(ans, F[now][i]);
}
} else {
for (valueType i = 1; i <= N; ++i) {
for (valueType j = 1; j <= i; ++j)
if (F[pre][j] + S[i] - S[j - 1] >= 0)
F[now][i] = std::max(F[now][i], F[pre][j] + S[i] - S[j - 1]);
if (i == rightBound)
ans = std::max(ans, F[now][i] + maxSum * (K - times));
ans = std::max(ans, F[now][i]);
}
}
}
std::cout << ans << std::endl;
}
std::cout << std::flush;
return 0;
}
C
//C - sol
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
valueType N, B, K;
ValueVector belong, capacity;
std::stack<valueType> stack;
ValueMatrix G;
void dfs(valueType x, valueType from) {
auto const start = (valueType) stack.size();
for (auto const &iter: G[x]) {
if (iter == from)
continue;
dfs(iter, x);
if (stack.size() >= start + B) {
++K;
capacity[K] = x;
while (stack.size() > start) {
belong[stack.top()] = K;
stack.pop();
}
}
}
stack.push(x);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> N >> B;
belong.resize(N + 1);
capacity.resize(N + 1);
G.resize(N + 1);
for (valueType i = 1; i < N; ++i) {
valueType a, b;
std::cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1, -1);
if (K == 0)
capacity[++K] = 1;
while (!stack.empty()) {
belong[stack.top()] = K;
stack.pop();
}
std::cout << K << std::endl;
for (valueType i = 1; i <= N; ++i)
std::cout << belong[i] << " ";
std::cout << std::endl;
for (valueType i = 1; i <= K; ++i)
std::cout << capacity[i] << " ";
std::cout << std::endl;
return 0;
}
D
#include<bits/stdc++.h>
const unsigned int seed = std::chrono::steady_clock::now().time_since_epoch().count() ^ 0xc0ffee;
std::mt19937 engine(seed);
typedef std::vector<int> ValueVector;
class FHQ {
protected:
struct Node {
typedef Node self;
typedef unsigned int randType;
typedef int keyType;
typedef int valueType;
typedef std::shared_ptr<self> pointer;
static constexpr const valueType MIN = std::numeric_limits<valueType>::min();
static constexpr const valueType MAX = std::numeric_limits<valueType>::max();
pointer leftSon;
pointer rightSon;
randType priority;
self::keyType key, lazy;
self::valueType value;
self::valueType min, max, min2, max2;
bool tag;
Node() : leftSon(nullptr), rightSon(nullptr), priority(::engine()), key(0), lazy(0), value(0), min(MAX),
max(MIN), min2(MAX), max2(MIN), tag(false) {};
Node(keyType _key_, valueType _value_) : leftSon(nullptr), rightSon(nullptr), priority(::engine()), key(_key_),
lazy(0), value(_value_), min(_value_), max(_value_), min2(MAX),
max2(MIN), tag(false) {};
void update() {
if (!this->leftSon && !this->rightSon) {
this->min = this->max = this->value;
this->min2 = MAX;
this->max2 = MIN;
this->tag = false;
} else if (!this->leftSon) {
this->min = std::min(this->value, this->rightSon->min);
this->max = std::max(this->value, this->rightSon->max);
this->min2 = this->rightSon->min2;
this->max2 = this->rightSon->max2;
this->tag = this->rightSon->tag || this->value < this->rightSon->max2;
if (!this->tag) {
if (this->rightSon->max > this->value) {
this->max2 = std::max(this->max2, this->value);
this->min2 = std::min(this->min2, queryRightMin(this->rightSon, this->value));
}
}
} else if (!this->rightSon) {
this->min = std::min(this->value, this->leftSon->min);
this->max = std::max(this->value, this->leftSon->max);
this->min2 = this->leftSon->min2;
this->max2 = this->leftSon->max2;
this->tag = this->leftSon->tag || this->value > this->leftSon->min2;
if (!this->tag) {
if (this->leftSon->min < this->value) {
this->min2 = std::min(this->min2, this->value);
this->max2 = std::max(this->max2, queryLeftMax(this->leftSon, this->value));
}
}
} else {
this->min = std::min({this->value, this->leftSon->min, this->rightSon->min});
this->max = std::max({this->value, this->leftSon->max, this->rightSon->max});
this->min2 = std::min(this->leftSon->min2, this->rightSon->min2);
this->max2 = std::max(this->leftSon->max2, this->rightSon->max2);
this->tag = this->leftSon->tag || this->rightSon->tag ||
this->leftSon->min2 < std::max(this->value, this->rightSon->max) ||
this->rightSon->max2 > std::min(this->value, this->leftSon->min);
if (this->leftSon->min < this->value && this->value < this->rightSon->max)
this->tag = true;
if (this->tag)
return;
if (this->leftSon->min < this->value)
this->min2 = std::min(this->min2, this->value);
if (this->rightSon->max > this->value)
this->max2 = std::max(this->max2, this->value);
if (this->leftSon->min < std::max(this->rightSon->max, this->value))
this->max2 = std::max(this->max2,
queryLeftMax(this->leftSon, std::max(this->rightSon->max, this->value)));
if (this->rightSon->max > std::min(this->leftSon->min, this->value))
this->min2 = std::min(this->min2,
queryRightMin(this->rightSon, std::min(this->leftSon->min, this->value)));
}
}
void push() {
if (this->lazy != 0) {
if (this->leftSon != nullptr) {
this->leftSon->lazy += this->lazy;
this->leftSon->key += this->lazy;
}
if (this->rightSon != nullptr) {
this->rightSon->lazy += this->lazy;
this->rightSon->key += this->lazy;
}
this->lazy = 0;
}
}
};
typedef Node::pointer pointer;
public:
typedef Node::valueType valueType;
typedef Node::keyType keyType;
private:
static pointer allocate(keyType k, valueType v) {
return std::make_shared<Node>(k, v);
}
public:
pointer root;
FHQ() : root(nullptr) {};
static std::pair<pointer, pointer> split(const pointer ¤t, keyType key) {
if (current == nullptr)
return std::make_pair(nullptr, nullptr);
current->push();
if (current->key <= key) {
auto const temp = split(current->rightSon, key);
current->rightSon = temp.first;
current->update();
return std::make_pair(current, temp.second);
} else {
auto const temp = split(current->leftSon, key);
current->leftSon = temp.second;
current->update();
return std::make_pair(temp.first, current);
}
}
static pointer merge(pointer left, pointer right) {
if (left == nullptr && right == nullptr) return nullptr;
if (right == nullptr) return left;
if (left == nullptr) return right;
left->push();
right->push();
if (left->priority < right->priority) {
left->rightSon = merge(left->rightSon, right);
left->update();
return left;
} else {
right->leftSon = merge(left, right->leftSon);
right->update();
return right;
}
}
static valueType queryLeftMax(pointer current, valueType limit) {
current->push();
while (true) {
if (current->leftSon && current->leftSon->min < limit)
current = current->leftSon;
else if (current->value < limit)
return current->value;
else
current = current->rightSon;
current->push();
}
}
static valueType queryRightMin(pointer current, valueType limit) {
current->push();
while (true) {
if (current->rightSon && current->rightSon->max > limit)
current = current->rightSon;
else if (current->value > limit)
return current->value;
else
current = current->leftSon;
current->push();
}
}
void swap(keyType left, keyType mid, keyType right) { // swap [left,mid] and (mid, right]
auto const L = split(this->root, left - 1);
auto const first = split(L.second, mid);
auto const second = split(first.second, right);
if (first.first != nullptr) {
first.first->key += right - mid;
first.first->lazy += right - mid;
}
if (second.first != nullptr) {
second.first->key -= mid - left + 1;
second.first->lazy -= mid - left + 1;
}
this->root = merge(merge(L.first, second.first), merge(first.first, second.second));
}
bool empty() const {
return this->root == nullptr;
}
bool ans() const {
return !empty() && this->root->tag;
}
void build(ValueVector const &A) {
root = build(0, A.size() - 1, A);
dfs(root);
}
pointer build(valueType l, valueType r, ValueVector const &A) {
if (l > r)
return nullptr;
if (l == r)
return allocate(l, A[l]);
valueType const mid = (l + r) >> 1;
pointer const left = build(l, mid - 1, A);
pointer const right = build(mid + 1, r, A);
pointer const current = allocate(mid, A[mid]);
current->leftSon = left;
current->rightSon = right;
return current;
}
void dfs(pointer const ¤t) {
if (current == nullptr)
return;
dfs(current->leftSon);
dfs(current->rightSon);
current->update();
}
void print() const {
print(this->root);
}
void print(pointer const ¤t) const {
std::cerr << "Node : (" << current->key << ", " << current->value << ")" << std::endl;
std::cerr << "min : " << current->min << std::endl;
std::cerr << "max : " << current->max << std::endl;
std::cerr << "min2 : " << current->min2 << std::endl;
std::cerr << "max2 : " << current->max2 << std::endl;
std::cerr << "tag : " << current->tag << std::endl;
std::cerr << "leftSon : " << std::endl;
if (current->leftSon != nullptr)
std::cerr << "(" << current->leftSon->key << ", " << current->leftSon->value << ")" << std::endl;
else
std::cerr << "nullptr" << std::endl;
std::cerr << "rightSon : " << std::endl;
if (current->rightSon != nullptr)
std::cerr << "(" << current->rightSon->key << ", " << current->rightSon->value << ")" << std::endl;
else
std::cerr << "nullptr" << std::endl;
std::cerr << std::endl;
if (current->leftSon != nullptr)
print(current->leftSon);
if (current->rightSon != nullptr)
print(current->rightSon);
}
} tree;
typedef int valueType;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cerr << "seed : " << seed << std::endl;
valueType N;
std::cin >> N;
ValueVector P(N + 2);
P[0] = N + 1;
P[N + 1] = 0;
for (valueType i = 1; i <= N; ++i)
std::cin >> P[i];
tree.build(P);
valueType Q;
std::cin >> Q;
for (valueType query = 0; query < Q; ++query) {
valueType l, r, k;
std::cin >> l >> r >> k;
tree.swap(l, r - k, r);
std::cout << (tree.ans() ? "YES\n" : "NO\n");
}
std::cout << std::flush;
return 0;
}