分类： 其他

[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间：2019.04 ~ 2019.09

参加成员：Modem_  Lagoon  _Qijia  mnihyc

备注：第二年就开始混水了啊（笑），只存了自己写的那部分：

  • 高维偏序

至此，\(k \le 3\) 的问题已经被我们解决了。

那 \(k = 4\) 呢？CDQ套CDQ？CDQ套树套树？树套树套树？

如果 \(k\) 更大，达到 \(k = 10\) 呢？十维树状数组？树套树套树套树套………？

很明显 \(O(n{\log ^{k – 1}}n)\) 的复杂度是承受不起的，需要从别的方面下手。

注意到在 \(k\) 变大的同时，\(n\) 也在变小，所以可以考虑复杂度以 \(n\) 为主的算法。

首先考虑的，当然是暴力啦）。

可以暴力枚举所有维度，并且按照这个维度（上的数）排序，这些就可以快速找出一个点控制了其它哪一些点。如果把这个信息用一个长度为 \(n\) 的二进制数表示，那么对于每个询问，只需要把它在所有维度下的二进制数取“与”运算（即能控制的点取交集），这样答案就是二进制位为 \(1\) 的数量了。

维护二进制串？当然是用 std::bitset<>  啦）。

这样复杂度就是 \(\displaystyle O\left( {\frac{{{n^2}k}}{{32}}} \right)\) ，足以通过本题了。

 

代码略。

 

这里其实还有一种在时空复杂度上的优化——分块）。

按照分块的那一套理论，把区间分成 \(\sqrt n \) 个，每块用一个 std::bitset<>  维护前缀，同时维护一个块最大值。查询的时候在块上二分，找到询问点所在的块，然后暴力加块内的点即可。时间复杂度即可缩小至 \(\displaystyle O\left( {\frac{{nk\sqrt n }}{{32}}} \right)\) 。

 

 …

[ARC092D] Two Sequences

[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度：\(4.0\)

  • Problem Statement

You are given two integer sequences, each of length \(N\): \(a_1, \cdots ,a_N\) and \(b_1, \cdots ,b_N\).

There are \(N^2\) ways to choose two integers \(i\) and \(j\) such that \(1 \leq i,j \leq N\). For each of these \(N^2\) pairs, we will compute \(a_i+b_j\) and write it on a sheet of paper. That is, we will write \(N^2\) integers in total.

Compute the XOR of these \(N^2\) integers.

给定两个长度为 \(n\) 的正整数数组 \(a,b\) ，求 \(\forall 1 \leq i,j \leq n\)，\(a_i+b_j\) 在二进制下的异或和 。

  • Input

\(n\) 和两数组 \(a,b\) 。

  • Output

答案。

  • Sample Input

  • Sample Output

  • Constraints

\(1 \leq …

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制：2000MS      内存限制：524288KB

难度：\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\)，有 \(m\) 次操作。格式如下：

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\)，表示序列长度和操作次数。

第二行 \(n\) 个正整数，第 \(i\) 个数为 \(a_i\)，表示序列初始值。

接下来 \(m\) 行每行四个正整数，表示操作，含义如题目所示。

  • 输出格式

对于每个询问，输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq …

YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

时间限制：5000MS      内存限制：524288KB

难度：\(7.0\)

  • 题目描述

一辆自动驾驶的士正在 \(Innopolis\) 的街道上行驶。该街道上有 \(n+1\) 个停车站点，它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起，它将照亮连接第 \(i\) 与第 \(i+1\)个站点的路段。否则这条路段将是黑暗的。

出于安全性的考虑，自动驾驶的士只能行驶在被照亮的路段上。换言之，的士能从站点 \(a\) 出发到达站点 \(b\) \((a<b)\) 的条件是：连接站点 \(a\) 与 \(a+1\)，\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 \(0\) 时刻时，街道上路灯的初始状态。之后 \(1,2,\cdots,q\) 时刻，每时刻会发生下列两种事件之一：

\(toggle i\)：切换第 \(i\) 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

\(query a b\)：自动驾驶的士部门的负责人想知道，从 \(0\) 时刻起到当前时刻，有多少个时刻满足：自动驾驶的士能够从站点 \(a\) 出发到达站点 \(b\) 。

请你帮助自动驾驶的士部门的负责人回答他们的问题。

  • 输入格式

第一行包含两个整数 \(n\) 和 \(q\) \((1 \leq n,q \leq 300000)\) —- 表示路灯的数量与时刻数。

第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\)， \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起； \(s_i\) 为 \(0\) 表示第 \(i\) 个路灯初始时熄灭。

接下来 \(q\) 行每行描述一个时刻的事件。第 \(i\) 行描述时刻 \(i\) 所发生的事件。

\(toggle i\) \((1 \leq i \leq n)\)：该时刻切换了第 \(i\) 个路灯的状态。

\(query a b\) \((1 \leq a < b \leq n+1)\)：计算从 \(0\) 时刻起到该时刻，共有多少个时刻满足的士能从站点 \(a\) 出发到达站点 \(b\) 。

至少有一个时刻的事件是 \(query\) 。

  • 输出格式

对于每个 \(query\) 的事件，输出一行单个整数，表示该问题的答案。…

YZOJ P2967 收割

YZOJ P2967 收割

时间限制：4000MS      内存限制：524288KB

难度：\(7.0\)

  • 题目描述

兔有 \(n\) 个甘蔗，兔将它们种成一排。

每天早上，第 \(i\) 个甘蔗会长高 \(a_i\) 米，但如果达到 \(b_i\) 米，就不会继续长高，而是维持在 \(b_i\) 米。

兔收割了 \(m\) 次甘蔗，第 \(i\) 次收割在第 \(t_i\) 天的晚上，他收割了 \([l_i, r_i]\) 中的所有甘蔗。收割后，这些甘蔗的高度变为 \(0\) 米，但第二天还会继续按照原来的规则生长。

请你求出兔每天收割了多少甘蔗。

  • 输入格式

第一行 \(n, m\) ；

接下来 \(n\) 行，每一行 \(a_i, b_i\) ；

接下来 \(m\) 行，每一行 \(t_i, l_i, r_i\)，保证输入的 \(t_i\) 严格递增。

  • 输出格式

输出 \(m\) 行表示兔每次收割的甘蔗的高度之和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

存在 \(30\%\) 数据，保证所有甘蔗都不会长到 \(b_i\) 米；

存在 \(30\%\) 数据，保证每次收取的是所有萝卜；

存在 \(60\%\) 数据，\(n \leq 50000\)；

对于所有数据 \(n \leq 300000\) ，\(m \leq 100000\) ，\(t_i,a_i,b_i \leq 10^9\) 。

 

 

 …

YZOJ P2905 [PA2014]Druzyny

YZOJ P2905 [PA2014]Druzyny

时间限制：1000MS      内存限制：131072KB

难度：\(8.0\)

  • 题目描述

在之前的某次校内训练中，zzx 出了一道神奇的题目：给出 \(n\) 个人，要求将所有人分成若干个组，第 \(i\) 个人所在的组的人数必须在 \([l_i, r_i]\) 之间，判断是否存在可行解。

OI组的神犇们决定把这题改造一下：

dick32165401：改成只有编号连续的的一段才可以分一组。

runzhe2000：判定可行解可能会被爆搜水过，最大化分的组数就不那么容易水过了。

E.Space：不仅要最大化组数，还要求出最大化组数的方案数。

ct：数据范围就出100万好了。

于是这题就被这么造好了。

  • 输入格式

第一行 \(n\)，\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行，每行 \(l_i,r_i\)，\(1 \leq l_i \leq r_i \leq 1000000\) 。

  • 输出格式

若不存在合法的方案，仅输出一行 \(-1\) 。

否则输出一行两个整数，分别表示组数的最大值和组数取最大值的方案数模 \(10^9+7\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ…

YZOJ P3527 [FJOI2018D1T3]城市路径问题

YZOJ P3527 [FJOI2018D1T3]城市路径问题

时间限制：1000MS      内存限制：131072KB

难度：\(6.5\)

  • 题目描述

给出一张 \(n\) 个点的有向图 \(G(V, E)\) 。对于任意两个点 \(u, v\) （\(u\) 可以等于 \(v\) ），\(u\) 向 \(v\) 的连边数为：\(\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}\) 。

给定 \(k\) 和数组 \(out, in\) ，现在有 \(m\) 个询问，每次询问给出三个参数 \(u, v, d\)，你需要回答从节点 \(u\) 出发，经过不超过 \(d\) 条边到达节点 \(v\) 的路径有多少种。

答案对 \(10^9+7\) 取模。

  • 输入格式

第一行两个整数 \(n, k\) 。

接下来 \(n\) 行，第 \(i\) 行有 \(2k\) 个整数，前 \(k\) 个整数描述 \(out[i][]\)，后 \(k\) 个数描述 \(in[i][]\) 。

接下来一行一个整数 \(m\) 。

接下来 \(m\) 行，每行三个整数 \(u, v, d\)，描述一组询问。

  • 输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 \(10^9+7\) 后的余数。…

YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制：5000MS      内存限制：1048576KB

难度：\(7.0\)

  • 题目描述

五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 \(n\) 个商店出现。第 \(i\) 个商店可 以使用四个整数 \(x_i , t_i , a_i , b_i\) 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 \(q\) 个询问，每个询问用二元组 （坐标，时间）表示。第 \(i\) 对二元组用两个整数 \(l_i , y_i\) 描述，分别表示选择的地点 \(l_i\) 和年份 \(y_i\) 。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离 居住点最远的商店类型到居住点的距离。类型 \(t\) 的商店到居住点的距离定义为：在指定的年份，类型 \(t\) 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 \(i\) 的商店在第 \(y\) 年在营业当且仅当 \(a_i \leq y \leq b_i\) 。注意，在某些年份中，可能在五福街上并非所有 \(k\) 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 \(-1\)。

你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 \(n,k\) 和 \(q\) ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量（\(1 \le n, q \le 3 \times 10^5 , 1 \le k \le n\)）

接下来 \(n\) 行，每行包含四个整数 \(x_i , t_i , a_i\) 和 \(b_i\) 用于描述一家商店，意义如题面所述 （\(1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i\)）。

接下来 \(q\) 行，每行包含两个整数 \(l_i\) 和 \(y_i\) ，表示一组（坐标，时间）查询 （\(1 \le l_i , y_i \leq 10^8 \)）。

  • 输出格式

输出一行，包含 \(q\) 个整数，依次表示对于 \(q\) 组（坐标，时间）询问求出的结果。…

YZOJ P3384 [校内训练20171201]括号替换问题

YZOJ P3384 [校内训练20171201]括号替换问题

时间限制：1000MS      内存限制：262144KB

难度：\(5.0\)

  • 问题描述

这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列，我们能得到一个正确的数学表达式，我们就认为这个括号序列是合法的。例如，序列 “(())()”, “()” 和 “(()(()))” 是合法的，但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”，“)” 和 “?” 组成的括号序列，你必须将 “?” 替换成括号，从而得到一个合法的括号序列。

对于给定仅由 “(”，“)” 和 “?” 组成的括号序列，你需要将 “?” 替换成括号，得到一个合法的括号序列，同时需要使得代价之和最小。

  • 数据输入

文件有多个测试实例（\(\leq 5\)）。每个实例的第一行有 \(1\) 个正整数 \(n\)，（\(1 \leq n \leq 100000\)），表示括号序列的长度为 \(n\)。第二行是一个长度为 \(n\) 的字符串，表示输入的括号序列，字符串仅由 “(”，“)” 和 “?” 组成。接下来 \(m\) 行，\(m\) 是字符串中 “?” 的个数，每一行包含两个整数 \(a_i\) 和 \(b_i\)（\(1 \leq a_i,b_i \leq 1000000\)），\(a_i\) 是将第 \(i\) 个 “?” 替换成左括号的代价，\(b_i\) 是将第 \(i\) 个 “?” 替换成右括号的代价。文件的最后一行有一个 \(0\) 表示结束。

  • 结果输出

将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数，表示最小代价和。如果不存在合法方案，输出 \(-1\)。如果存在合法方案，第二行输出替换后的括号序列。若有多种替换方案的代价之和最小，可以输出任意一种。…

YZOJ P3195 [NOI2017]游戏

YZOJ P3195 [NOI2017]游戏

时间限制：1000MS      内存限制：524288KB

难度： \(6.4\)

  • 题目描述

小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。

\(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\underline{\mathrm{xaabxcbc}}\) 表示小 L 计划进行 \(8\) 场游戏，其中第 \(1\) 场和第 \(5\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(a\)，不适合赛车 \(A\)，第 \(4\) 场和第 \(7\) 场的地图是 \(b\)，不适合赛车 \(B\)，第 \(6\) 场和第 \(8\) 场的地图是 \(c\)，不适合赛车 \(C\) 。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 \((i,h_i,j,h_j)\) 来描述，表示若在第 \(i\) 场使用型号为 \(h_i\) 的车子，则第 \(j\) 场游戏要使用型号为 \(h_j\) 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “\(-1\)”（不含双引号）。

  • 输入格式

输入第一行包含两个非负整数 \(n,d\) 。

输入第二行为一个字符串 \(S\) 。

\(n,d,S\) 的含义见题目描述，其中 \(S\) 包含 \(n\) 个字符，且其中恰好 \(d\) 个为小写字母 \(x\) 。

输入第三行为一个正整数 \(m\)，表示有 \(m\) 条用车规则。接下来 \(m\) 行，每行包含一个四元组 \(i,h_i,j,h_j\) ，其中 \(i,j\) 为整数，\(h_i,h_j\) 为字符 \(A\) 、\(B\) 或 \(C\)，含义见题目描述。

  • 输出格式

输出一行。

若无解，输出 “\(-1\)”（不含双引号）。

若有解，则包含一个长度为 \(n\) 的仅包含大写字母 \(A\)、\(B\)、\(C\) 的字符串，表示小 L 在这 \(n\) 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。…