BZOJ3110 - Click Here
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c。如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
Output
输出每个询问的结果
Solutions
树套树。权值线段树套区间线段树。
一开始，我想的是区间线段树套权值线段树，然后利用二分答案来求解。但是每次操作时间是$log_{}^{3}N$，很明显过不了。后来发现，可以将二分答案转换成二分查找(常用技巧QAQ)。
改成权值线段树套区间线段树，然后每次询问就可以用二分查找解决。这样，询问的时间就可以降为$log_{}^{2}N$。
2018.10.30 Updated:
上文也说了，每个询问都可以二分答案来求解。再加之每次加入元素的操作之间是相互独立的，因此可以直接整体二分。
CODE
CODE(树套树) - Click Here
CODE(整体二分) - Click Here