「UOJ 299」「CTSC2017」游戏
题意
小 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\)
后面的游戏结果会影响前面的概率 = =
小 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\)
后面的游戏结果会影响前面的概率 = =
给你一张 \(n\) 个点 \(m\) 条边的无向图，每个点有点权，\(q\) 次操作
C a w，将第 \(a\)
个点的权值改为 \(w\)
A a b，询问 \(a\)
到 \(b\)
所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
\(n,m,q\le 10^5\)
你有一棵\(n\)个点的树，点\(y\)有一个\([0,m)\)内的整数权值\(a_u\)
定义一棵树的权值是点权的异或和
有\(q\)次操作
Change x y，表示把第\(x\)个点的权值改成\(y\)
Query x，表示询问有多少个非空的联通子树的权值是\(x\)，模\(10007\)
\(n,q\le30000,m\le128\)
你有一棵\(n\)个点的树，边有权，有两种操作
CHANGE x y，表示修改第\(x\)条边的边权为\(y\)
QUERY x y，表示询问点\(x\)到\(y\)路径上的边权最大值
在数轴上有\(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\)
给出一个长度为\(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\)，有 \(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}\)。