主席树目录下的文章
[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……