BZOJ 2125

题意

给定 $n$个 点仙人掌（每条边只在不超过1个简单环中的无向连通图），$q$ 次询问两点间最短路

边带权

$n,q\le 10000$

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$

LOJ #2127

题意

你有一个数字 $0$，每秒你会以 $p_i$ 的概率选择 $i$，$i\in[0,2^n-1]$，和自己的数进行按位或，问期望多少秒后数字变成 $2^n-1$

$n\le20,\sum p_i=1$

BZOJ 2639

题意

给出一个$n$行$m$列的矩阵，有$q$次询问，每次指定一个子矩阵，询问每种数字在这个子矩阵中出现次数的平方和

$n,m\le200,q\le10^5$

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$

Codeforces 662C

题意

给出一个$n$行$m$列的$01$矩阵，可以任意次取反一行或一列，最小化矩阵中$1$的总数

$n\le20,m\le10^5$

BZOJ 1921

题意

给一棵 $n$ 个点的树和长度为 $m$ 的特征串，树的每个节点有一个字符。

求随机两个点形成有向路径上构成的串在特征串里出现次数的期望

仅含小写字母，$n,m\le 5*10^4$

• 多项式乘法
• 多项式求逆
• 多项式除法/取模
• 多项式牛顿迭代法
• 多项式开根
• 多项式 $\ln$
• 多项式 $\exp$
• 多项式 $k$ 次幂
• 多项式多点求值和快速插值

封装的代码可以看挑战多项式

写的时候要注意各种清空问题.

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$