UOJ #164

题意

给出一个长度为$n$的数列$a$，需要维护以下操作

1. 对于$i\in[l,r]$，$a_i=a_i+x$

2. 对于$i\in[l,r]$，$a_i=max(a_i-x,0)$

3. 对于$i\in[l,r]$，$a_i=x$

4. 询问$a_y$

5. 询问$a_y$的历史最大值

$n,m\le 5*10^5,0\le a_i,x\le10^9$

BZOJ 3064

题意

你有一个长度为$n$的数列，$m$个操作。

1. 查询区间最大值

2. 查询所有历史版本（包括现在）的区间最大值的最大值

3. 区间加

4. 区间覆盖

$n,m\le 10^5$

LOJ #2430

题意

一排$n$个水果$a_1..a_n$，分别是苹果$(j)$和橘子$(p)$，求最长的区间满足从左向右和从右向左取水果，任意时刻都有橘子数$\ge$苹果数，输出最长的区间长度

$n\le 10^6$

HDU 5306

题意

你有一个长为 $n$ 的序列 $a$，有 $m$ 次操作

• 给出 $l,r,x$，对于 $i\in[l,r]$，令 $a_i=min(a_i,x)$

• 给出 $l,r$，询问 $[l,r]$ 中的最大值

• 给出 $l,r$，询问 $\sum_{i=l}^ra_i$

多组数据，$\sum n\le 10^6,\sum m\le 10^6$

BZOJ 4373

题意

你有一个长度为$n$的数列$a$，需要支持如下操作：

1. 单点修改

2. 给出$l,r,k$，询问区间$[l..r]$中的数从小到大排序后是否为公差为$k$等差数列

强制在线

第一篇算法相关

第一次自己想sam

Codeforces 1063F

题意

给出一个长度为$n$的字符串$s$。

如果一个字符串序列$t_1,\dotsc,t_k$，$\forall1<i\le k$，$t_i$是$t_{i-1}$的一个子串，且长度严格小，那么称这个字符串序列是一个journey。

一个journey的长度是其中字符串的数量

求最长的journey，满足存在字符串序列$u_1,\dotsc,u_{k+1}$(可以为空)，使$s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}$。