题意
给出一个长度为\(n\)的数列\(a\)，需要维护以下操作
对于\(i\in[l,r]\)，\(a_i=a_i+x\)
对于\(i\in[l,r]\)，\(a_i=max(a_i-x,0)\)
对于\(i\in[l,r]\)，\(a_i=x\)
询问\(a_y\)
询问\(a_y\)的历史最大值
\(n,m\le 5*10^5,0\le a_i,x\le10^9\)
给出一个长度为\(n\)的数列\(a\)，需要维护以下操作
对于\(i\in[l,r]\)，\(a_i=a_i+x\)
对于\(i\in[l,r]\)，\(a_i=max(a_i-x,0)\)
对于\(i\in[l,r]\)，\(a_i=x\)
询问\(a_y\)
询问\(a_y\)的历史最大值
\(n,m\le 5*10^5,0\le a_i,x\le10^9\)
给一棵 \(n\) 个点的树和长度为 \(m\) 的特征串，树的每个节点有一个字符。
求随机两个点形成有向路径上构成的串在特征串里出现次数的期望
仅含小写字母，\(n,m\le 5*10^4\)
一排\(n\)个水果\(a_1..a_n\)，分别是苹果\((j)\)和橘子\((p)\)，求最长的区间满足从左向右和从右向左取水果，任意时刻都有橘子数\(\ge\)苹果数，输出最长的区间长度
\(n\le 10^6\)
你有一个长为 \(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\)
你有一个长度为\(n\)的数列\(a\)，需要支持如下操作：
单点修改
给出\(l,r,k\)，询问区间\([l..r]\)中的数从小到大排序后是否为公差为\(k\)等差数列
强制在线
第一篇算法相关
第一次自己想sam
给出一个长度为\(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}\)。