SPOJ QTREE

题意

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

• CHANGE x y，表示修改第\(x\)条边的边权为\(y\)

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

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\)