分类 树套树 下的文章

BZOJ 3196: Tyvj 1730 二逼平衡树

Solution可以用线段树套权值线段树无脑做,然而我被卡空间了,不想改了,下面的代码无法 AC,会 MLE。Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cmath> #include <queue> using namespace std; const int N = 51000; int n, m; int arr[N]; struct inNode { - 阅读剩余部分 -

BZOJ 3110: [Zjoi2013]K大数查询

Solution线段树套线段树,外层是权值线段树,内层区间线段树。这样某个区间加一个值就变成了外层线段树单点修改,内层线段树区间加 1。询问的话,在外层线段树上二分就可以了,具体看我代码吧..需要注意开 long long,有负数需要离散化。用指针写树套树,动态开点实现起来更优雅,还不需要提前开数组...#include <cstdio> #include <algorithm> #include <vector> #include <iostream> #define long long long using namespa- 阅读剩余部分 -

BZOJ 1901: Zju2112 Dynamic Rankings

Description给定一个含有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继续回答上面的问题。Input第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令每行的格式是下面两种格式中的一种。 Q i j k 或者 C- 阅读剩余部分 -