主席树目录下的文章
[UOJ 218] 火车管理
题意简述
有n个栈，编号为1到n。有m个操作，如下三种：
1 l r : 计算第l到第r个栈的栈顶元素之和。
2 l : 第l个栈弹出栈顶元素，如果不存在则不执行。
3 l r x : 第l到第r个栈都把x压栈。
强制在线。
1 \le n, m \le 5 \times 10 ^ 5, 1 \le x \le 10 ^ 3
算法讨论
一开始一直在……
[BZOJ 2874] 训练士兵
题意简述
有一个n \times m的矩阵A，初始值均为0。
要求先进行k次修改操作，再回答q个询问。
修改操作选定一个子矩阵加上一个数。询问操作要求回答一个子矩形的和。
答案保证不超过2 ^ {64}。询问强制在线。
1 \le n, m \le 10 ^ 8, 1 \le t \le 40000, 1 \le q \le 100000
算法……
[BZOJ 1901] Dynamic Rankings
题目描述
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。
你需要编一个这样的程序，从……
[BZOJ 3524] Couriers
题目描述
给定一个长度为n的序列a。
有m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。
输入格式
第一行两个数n，m。n,m≤500000。
第二行n个数，a[i]。1≤a[i]≤n。
接下来m行，每行两个数l,r，表示询问[l,r……
[BZOJ 1415] 聪聪和可可
[BZOJ 1822] 冷冻波
[BZOJ 3931] 网络吞吐量
且看当下
矩阵优化递推