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\) 。

 

 

 …

[校内训练20161216] T2 版本管理git

[校内训练20161216] T2 版本管理git

时间限制:2000MS      内存限制:1048576KB

难度:\(7.0\)

  • 题目描述

在工程的开发中,我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的:刚开始只有一个版本 \(0\),表示最初始的情况,也就是空的项目;接下来一个用户可以对某一个版本 \(p\) 的项目进行修改,得到一个新的版本 \(i\)。这样,一个工程就产生了许多不同的版本,而管理员可以选择一些优秀的,将其合并到主版本中。

\(F\) 公司有一个项目 \(U\),这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改,其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。

作为项目的总负责人,你希望对这些版本进行评价。对一个字符串 \(S\),称串 \(S\) 是串 \(T\) 的超前缀,当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串,如若 \(T = abcd\),则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\),当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀,且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀(定义空串的 \(kitty\) 长度为 \(0\))。你需要做的就是对每一个版本求出其的 \(kitty\) 长度(设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\))。

在实际运营中,有两种情况,我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中, 你可以等候开发者进行所有修改后,再进行计算;但在 \(k = 1\) 的情况中,开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度,你需要实时计算出每个版本的 \(kitty\) 长度。

  • 输入格式

第一行包含三个整数 \(n,m,k\)。

接下来 \(n\) 行,其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\),其中:

如果 \(k = 0\) ,则 \(p_i = p^{′}_{i}\),\(c_i = c^{′}_{i}\);

如果 \(k = 1\),则 \(p_i = p^{′}_{i} \oplus kitty(i …