妙妙题

CF369E Valera and Queries

传送门

题意简述

给定条线段，共有次询问，每次询问给定一组点集，询问至少覆盖其中一个点的线段条数。

思路

正难则反。

对于每次询问的点集，我们考虑以其为分割点，转化为一条条线段。例如：这个点集可以转化为这样的线段。

转化完成后按左端点从大到小排序，用树状数组统计答案即可。

P6564 [POI2007] 堆积木KLO

传送门

题意简述

有一串数列，定义一串数列的价值为满足的元素数量，你可以删除其中任意多个元素，使在它后面的元素向前平移。求价值的最大值。

，

思路

我们设表示在这个位置经过修改价值的最大值，那么可以得出这样的转移方程：

最后一个条件转化后即为。

因此，我们将整个序列以排序，用树状数组维护的最大值，以为关键词查询即可。

P2757 [国家集训队] 等差子序列

传送门
双倍经验

题意简述

给定一个排列，判断一个序列中是否有长度大于等于的等差子序列。

思路

首先我们可以将条件转换为：是否有一个长度为的等差子序列。那么我们继续转换：那么就是有一个数，存在一个数，满足和分居它两侧即可。

我们考虑从左到右扫描序列，记录下每一个之前扫描过数的位置，那么只要没有关于当前这个数对称，即存在一个长度为的等差数列。用线段树维护哈希值即可。

CF19D Points

传送门

这种题都不会做，我是不是该退役了

题意简述

有次在一个笛卡尔坐标系上的操作，有三种种类：

1. 加入一个点
2. 删除一个点
3. 查询在点严格右上角的，横坐标最近的，如有多个取纵坐标最近的点的坐标。

保证所有操作合法，即：不会有重复的点，不会删除不存在的点。

，

思路

一开始想成树套树了，死活做不出来……

首先很显然，坐标需要离散化然后就不会了。

我们注意到，查询的点的第一要求是横坐标最近，那么在查询的时候，我们只需要找到最靠左的横坐标，使得它有点在查询的点的右上方即可。我们建一颗线段树，维护横坐标在这个区间内的点的纵坐标的最大值（最开始都是）。对于每个横坐标，我们开一个 set 来维护纵坐标，在插入和删除的时候同步修改线段树上的最大值，在查询的时候线段树上二分即可，差不多像这样：

il int query(int p, int x, int y) {
  if (t[p].l == t[p].r) return (t[p].ma > y) ? t[p].l : -1;
  int res = -1;
  if (x <= mid && t[ls].ma > y) res = query(ls, x, y);
  if (~res) return res;
  if (t[rs].ma > y) res = query(rs, x, y);
  return res;
}

时间复杂度为

ABC219F Cleaning Robot

传送门

题意简述

懒得化简了，直接复制了洛谷翻译。

一个清扫机器人被放置在无限扩展的二维网格的方格上。

给定了一个由四种类型的字符 L、R、U、D 组成的字符串程序。
机器人根据给定的程序，依次读取每个字符，并针对每个字符采取以下行动：

1. 将机器人的当前位置设为方格
2. 根据读取的字符执行以下移动：

• 当读取 L 时：向左移动到方格。
• 当读取 R 时：向右移动到方格。
• 当读取 U 时：向上移动到方格。
• 当读取 D 时：向下移动到方格。

给定一个由 L、R、U、D 组成的字符串和整数。机器人执行的程序是将字符串重复连接次。

一旦机器人访问过的方格（包括机器人的初始位置）就会被清扫。
请输出在机器人执行程序结束后，被清扫的方格的数量。

，

思路

一看到这题的数据范围，我们可以立马发现：暴力是没有前途的废话。

我们发现，每次循环过一次，机器人横坐标的改变量和纵坐标的改变量是一定的，我们不放从这里入手。我们只考虑一次循环，思考：什么时候一个点的贡献（其实就是出现次数）不是？

答案不太好想：我们把循环的左下角看作起点（如果不是左下角，那就旋转它！），将每个点视作在一条斜率为的线上。那么一个点的贡献不是，当前仅当它后面有与它在同一条线上，并且之间的距离容不下次移动的点(应为之后的移动一定会被后面的点覆盖)。我们其实只需要模拟一次循环，便可找到所有点在哪根线上。假设两个点的横坐标分别为，，那么前一个点的贡献即为。我们用 std::set 存储经过的位置，用 std::map 存储每条线段上有哪些点，时间复杂度为。

注意处理和负数的情况。

CF940F Machine Learning

传送门

题意简述

给定一个数组，支持两种操作：

1. 修改一个位置的值
2. 查询这段区间内元素出现次数的。

思路

看到对一些区间进行与出现次数相关的查询以及数据范围，我们不难想到带修莫队的做法。那怎么查找出现次数的值呢？呃，其实直接从开始枚举就行了，因为这个的和是平方级别的，那么答案一定是在级别的。

视，同阶，时间复杂度为。

P4211 [LNOI2014] LCA

传送门

题意简述

（我就直接复制题面了）

给出一个个节点的有根树（编号为到，根节点为）。

一个点的深度定义为这个节点到根的距离。

设表示点的深度，表示与的最近公共祖先。

有次询问，每次询问给出，求，对取模。

思路

这道题要用到我一个不会的经典套路：两个点之间 lca 的深度，就是在其中一个点到根节点的路径上整体加，然后求另一个点到根节点的路径上权值和。但是如果暴力这样做的话，复杂度为，无法通过本题。如何优化？

我们注意到每次要求的是一段连续区间与某个点的 lca 深度之和，我们不难想到对这个区间差分（为什么我想不到），直接从到全加上，那么两次询问答案的差即为最终答案。

将询问离线下来后树剖 + 线段树即可，时间复杂度为。

[AGC040C] Neither AB nor BA

传送门

题意简述

给定一个正偶数，求出长度为的， 由 A，B，C，组成的，能够被以下方式完全删除的字符串个数，对取模。

删除方式：删除两个相邻的，不是 AB 或 BA 的字符。

思路

这道题要用到一个 Trick：奇偶染色（我瞎胡的名字）。具体的，我们对于一个假想的字符串，把它偶数位上的 A 换成 B，B 换成 A，那么删除条件就转换为了：不能是两个 A 或 两个 B 一起删除。我们设 A 的个数为，B 的个数为，在不考虑 C 的情况下，最后会剩下个字符。设 C 的个数为，那么能够被完全删除的充要条件为。注意到，带入解得。我们考虑容斥，计算或大于的字符串个数，因为同时只能满足一个条件，因此个数为。最终答案即为。

[AGC052B] Tree Edges XOR

传送门

题意简述

给你一棵有个节点的树，保证为奇数。每条边上有一个边权和一个目标边权，每次可以选择一条边，

将与这条边有公共点的所有边的边权都异或上这条边的边权，求能否把所有的变为。

，

思路

首先我们手玩一下，发现什么是不容易变的？就是一条路径的异或和，只要一个端点不是选定的那条边的一个端点，那么异或和就是不变的。那么我们用上一个经典（真的经典吗？）Trick：将边权转为点权。但这里不是简单的一一对应，而是将一个点的点权设为从根到这个点的路径和，那么一条路径的异或和就被转化为了两个端点的权值的异或。我们继续手玩，发现这样一个事实：对于一条边的操作，相当于交换两个点的点权。好，现在你兴冲冲的按照这个去写，判断两棵树的点权集合是否相等，尽管你感觉有些不对劲。一交，好，WA 了。哪里不对劲？在于根节点：它的权值应该保持为。

现在该这么处理？我们仔细思考一下为什么根节点是特殊的。答案是显然的（真的吗）：因为它没有向上的边。这并不好办，我们在它上面接个虚拟节点不就是了？那么现在的问题是：这个点到根节点的边权应该是多少？我们考虑一下这条边对每个点的点权的影响，其实就是都异或上一个边权。因为是奇数，那么点权的异或和就会异或上一个边权。那么，如果这条边的边权不是以建树点权的异或和和以建树点权的异或和的异或，那么肯定是无法达成目标的。但是这只是一个必要条件，所以求出这个边权之后还要判断两棵树的点权集合是否相等，时间复杂度为。

CF1641D Two Arrays

传送门

题意简述

给定个长为的序列，保证序列内部元素互补相同。每个序列有一个权值。求出最小的，使得和的个元素互不相同。若无解，输出。

，，

思路

做不出来，鉴定为：题做少了。

首先注意到总的数组个数很少，但值域很大，显然首先要离散化。然后我们发现可以使用 std::bitset 来记录每个数字在哪几个序列中出现过，时间复杂度为，但这样空间会爆（然后就不会了）。这道题需要用到平衡复杂度的 Trick。具体的，我们令，只有出现次数大于等于的数我们才在 std::bitset 里统计出现位置，小于的我们直接暴力统计，时间复杂度为，足以通过本题。

CF618F Double Knapsack

传送门

题意简述

给定两个长为的序列，，保证序列中每个元素的大小都在与之间。求能否找到两个序列的两个子集，使得它们的和相等，无解输出。

思路

妙妙构造题。

我们注意到值域等于，想想能利用这一点做什么。首先，我们大胆猜测一定有解（虽然确实一定有解）对两个序列做两个前缀和。我们假设，以此来进行接下来的分析。

对于，我们找到使得的第一个位置，那么一定有。一共有对，但只有个取值，那么一定会有重复的，那么在这两对位置之间的元素和相同，我们通过双指针找出每队即可，的情况同理，时间复杂度为。

P4587 [FJOI2016] 神秘数

传送门

题意简述

定义一个可重集的神秘数为不可以被集合内元素累加表示出来的最小的数。现在给你一个长度为的序列，多次询问，求出一段区间内的神秘数是多少。

，

思路

很有意思的一道题。

我们先不考虑在序列上的询问，想想给了你一个可重集，我们如何求出这个可重集的神秘数。我从小到大加入数字，假如当前可以表示的数的范围是，新加入的数是，假如，那么神秘数就是，否则能够表示的数的范围就是。我们想想如何把这个方法扩展到序列上。我们假设当前能够表示的最大值为，假如这个序列内小于等于的数之和大于，那么答案一定可以扩大到这些数的和，我们可以用主席树维护这个求和的过程。看上去时间复杂度很假，但我们发现这个更新过程是一个类似于斐波那契数列的扩展过程，所以时间复杂度大概是