UOJ #299

题意

小 R 和小 B 玩了 $n$ 局游戏，第一局小 R 获胜的概率是 $p_1$，对于第 $i(1<i\le n)$ 局，若第 $i-1$ 局小 R 获胜，则小 R 获胜的概率为 $p_i$，否则为 $q_i$

现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 $m$ 次增加或删除已知条件后都输出答案

$n,m\le 2\times 10^5$

后面的游戏结果会影响前面的概率 = =

Codeforces 487E

题意

给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作

1. C a w，将第 $a$ 个点的权值改为 $w$

2. A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值

简单路径即不经过一个点超过一次的路径

$n,m,q\le 10^5$

LOJ #2269

题意

你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

• Change x y，表示把第$x$个点的权值改成$y$

• Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$

$n,q\le30000,m\le128$

SPOJ QTREE

题意

你有一棵$n$个点的树，边有权，有两种操作

• CHANGE x y，表示修改第$x$条边的边权为$y$

• QUERY x y，表示询问点$x$到$y$路径上的边权最大值

LOJ #2585

题意

在数轴上有$n$家商店，第$i$个商店有坐标$x_i$，种类$t_i\in[1..k]$，出现时间$[a_i,b_i]$

有$q$组询问$l_i,y_i$，表示询问在时间$y_i$，离坐标$l_i$最远的商店类型到$l_i$的距离

类型$t$的商店到一个点的距离定义为所有存在的$t$类商店到这个点的距离的最大值

$1\le n,q\le 3*10^5,1\le k\le n$

$1\le x_i,a_i,b_i\le 10^9$

$1\le l_i,y_i\le 10^8$

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$

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}$。