[Dr.Lib]Note:Data Structures – Size Balanced Tree – II

。。也没什么好说的了，《Size Balanced Tree》（CQF WC 2006）说的很清楚了……

今晚（昨晚？手敲的代码……不知道如何……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define L(x) T[(x)].ls
#define Ln(x) T[T[(x)].ls]
#define R(x) T[(x)].rs
#define Rn(x) T[T[(x)].ls]
#define W(x) T[(x)].w
#define S(x) T[(x)].size
using namespace std;

const int MAXN=100000;
const int INF=2147483647;
int root=0;

struct Node{
	int ls,rs,size,w;
	Node():ls(0),rs(0),size(0),w(0){}
};
Node T[MAXN];
int sz,n;

void RR(int &s){
	int x = s;
	int k=L(s);
	L(s)=R(k);
	R(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void LR(int &s){
	int x = s;
	int k=R(s);
	R(s)=L(k);
	L(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void Maintain(int &s,bool op){
	if (s == 0)return;
	if(!op){
		if( S(R(s)) < S(L(L(s))) )RR(s);
		else if( S(R(s)) < S(R(L(s))) ){
			LR(L(s));RR(s);
		}
		else  return;
	}else{
		if( S(L(s)) < S(R(R(s))) )LR(s);
		else if( S(L(s)) < S(L(R(s))) ){
			RR(R(s));LR(s);
		}
		else  return;
	}
	Maintain(L(s),false);
	Maintain(R(s),true);
	Maintain(s,false);
	Maintain(s,true);
}
void Insert(int &s,int val){
	if(s==0){
		s=++sz;S(s)++;W(s)=val;return;
	}
	S(s)++;
	if(W(s)>val)Insert(L(s),val);
	else Insert(R(s),val);
	Maintain(s,(val>=W(s)));
}
int Delete(int &s,int v){
	S(s)--;
	if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){
		int ans=W(s);
		if(!(L(s)*R(s))){
			s=L(s)+R(s);
		}else{
			W(s)=Delete(L(s),W(s)+1);
		}
		return ans;
	}else{
		if(W(s)>v) return Delete(L(s),v); 
		else       return Delete(R(s),v);
	}
}
int Search(int &s,int v){
	if(!s)return INF;
	if(v==W(s))return s;
	else if(W(s)>v) return Search(L(s),v);
	else            return Search(R(s),v);
}
int Select(int &s,int k){
	if(k>S(root)) return INF;
	int Lt=S(L(s));
	if(k==Lt) return W(s);
	else if(Lt>k) return Select(L(s),k);
	else          return Select(R(s),k-Lt-1);
}
int Rank(int &s,int x){
	if(!s)return INF;
	int Lt=S(L(s));
	if(x==W(s))return Lt;
	else if(W(s)>x)return Rank(L(s),x);
	else           return Rank(R(s),x)+Lt+1;
}
int main(){
	int c;
	int x;
	while(cin>>c>>x){
		switch(c){
			case 0:Insert(root,x);break;
			case 1:Delete(root,x);break;
			case 2:cout<<Search(root,x)<<endl;break;
			case 3:cout<<Select(root,x)<<endl;break;
			case 4:cout<<Rank(root,x)<<endl;break;
			default:cout<<endl;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define L(x) T[(x)].ls

#define Ln(x) T[T[(x)].ls]

#define R(x) T[(x)].rs

#define Rn(x) T[T[(x)].ls]

#define W(x) T[(x)].w

#define S(x) T[(x)].size

using namespace std;

const int MAXN=100000;

const int INF=2147483647;

int root=0;

struct Node{

int ls,rs,size,w;

Node():ls(0),rs(0),size(0),w(0){}

};

Node T[MAXN];

int sz,n;

void RR(int &s){

int x = s;

int k=L(s);

L(s)=R(k);

R(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void LR(int &s){

int x = s;

int k=R(s);

R(s)=L(k);

L(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void Maintain(int &s,bool op){

if (s == 0)return;

if(!op){

if( S(R(s)) < S(L(L(s))) )RR(s);

else if( S(R(s)) < S(R(L(s))) ){

LR(L(s));RR(s);

}

else return;

}else{

if( S(L(s)) < S(R(R(s))) )LR(s);

else if( S(L(s)) < S(L(R(s))) ){

RR(R(s));LR(s);

}

else return;

}

Maintain(L(s),false);

Maintain(R(s),true);

Maintain(s,false);

Maintain(s,true);

}

void Insert(int &s,int val){

if(s==0){

s=++sz;S(s)++;W(s)=val;return;

}

S(s)++;

if(W(s)>val)Insert(L(s),val);

else Insert(R(s),val);

Maintain(s,(val>=W(s)));

}

int Delete(int &s,int v){

S(s)--;

if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){

int ans=W(s);

if(!(L(s)*R(s))){

s=L(s)+R(s);

}else{

W(s)=Delete(L(s),W(s)+1);

}

return ans;

}else{

if(W(s)>v) return Delete(L(s),v);

else return Delete(R(s),v);

}

int Search(int &s,int v){

if(!s)return INF;

if(v==W(s))return s;

else if(W(s)>v) return Search(L(s),v);

else return Search(R(s),v);

}

int Select(int &s,int k){

if(k>S(root)) return INF;

int Lt=S(L(s));

if(k==Lt) return W(s);

else if(Lt>k) return Select(L(s),k);

else return Select(R(s),k-Lt-1);

}

int Rank(int &s,int x){

if(!s)return INF;

int Lt=S(L(s));

if(x==W(s))return Lt;

else if(W(s)>x)return Rank(L(s),x);

else return Rank(R(s),x)+Lt+1;

}

int main(){

int c;

int x;

while(cin>>c>>x){

switch(c){

case 0:Insert(root,x);break;

case 1:Delete(root,x);break;

case 2:cout<<Search(root,x)<<endl;break;

case 3:cout<<Select(root,x)<<endl;break;

case 4:cout<<Rank(root,x)<<endl;break;

default:cout<<endl;

}

return 0;

}

[Dr.Lib]Note:Math – Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

\( [P] = \begin{cases} 1 & \text{if } P \text{ is true;} \\ 0 & \text{otherwise.} \end{cases} \)

where P is a statement that can be true or false. This notation was introduced by Kenneth E. Iverson in his programming language APL,while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.

The Iverson bracket converts a Boolean value to an integer value through the natural map \( \textbf{false}\mapsto 0; \textbf{true}\mapsto1 \), which allows counting to be represented as summation. For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

\( \phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad\text{for }n\in\mathbb N^+. \)

More generally the notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically. For example

\( \sum_{1\le i \le 10} i^2 = \sum_{i} i^2[1 \le i \le 10]. \)

In the first sum, the index \( i \) is limited to be in the range 1 to 10. The second sum is allowed to range over all integers, but where i is strictly less than 1 or strictly greater than 10, the summand is 0, contributing nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n\varphi(n) \)

which is valid for n > 1 but which is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which \(\phi(n) \) is defined), a correction term involving the Iverson bracket may be added:

\( \sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n(\varphi(n)+[n=1]) \)

-By Wikipedia https://en.wikipedia.org/wiki/Iverson_bracket

Via Ivy – End http://www.ivy-end.com/archives/1064

闲来无事，逛逛Mathematics。看到一道关于数列的题目，不妨拿来研究一下。原题地址

题目是这么说的，计算\[\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}.\]各位可以自己动笔计算一下。

下面我们主要讨论一下给出的两种种解法。

法一：

令\(S_{n}=\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2}\)。

则\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n} \right )^{2}+\cdots + \left ( \frac{1}{n-1}+\frac{1}{n} \right )^{2}+\left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]整理得\[S_{n}-S_{n-1}=\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \left [ \left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]\\ + \cdots + \left [ \left ( \frac{1}{n-1} \right )^{2}+2\cdot\left ( \frac{1}{n-1} \right )\cdot\left ( \frac{1}{n} \right )+\left ( \frac{1}{n} \right )^{2} \right ]+\left [ \left ( \frac{1}{n} \right )^{2} \right ]\\-\left [\left ( 1+\frac{1}{2}+\cdots + \frac{1}{n-1} \right )^{2}+\cdots + \left ( \frac{1}{n-2}+\frac{1}{n-1} \right )^{2}+\left ( \frac{1}{n-1} \right )^{2} \right ].\]化简得\[S_{n}-S_{n-1}=n\cdot\left ( \frac{1}{n} \right )^{2}+2\cdot\frac{1}{n}\cdot\left [ 1+2\cdot\frac{1}{2}+3\cdot\frac{1}{3}+\cdots +\left ( n-1 \right )\cdot\frac{1}{n-1} \right ].\]即\[S_{n}-S_{n-1}=\frac{1}{n}+\frac{2\left ( n-1 \right )}{n}=2-\frac{1}{n}.\]运用累加法求和即可得到\[S_{n}=2n-H_{n}.\]其中\(H_{n}=1+\frac{1}{2}+\frac{1}{2}+\cdots +\frac{1}{n}.\)

法二：

这种方法比第一种方法高明很多，它需要用到一个引理——Iverson Bracket。简单的介绍一下这个引理，它的符号是中括号，当且仅当中括号里的表达式成立时，其值为\(1\)，否则为\(0\)。例如\(\left [ 1 < 2 \right ]=1\)，而\(\left [ 1 > 2 \right ]=0\)。

下面我们就用Iverson Bracket来求解这个问题\[S_{n}=\sum_{k}\left ( \sum_{i}\frac{1}{i}\cdot\left [ k \leq i \right ] \right )^{2}=\sum_{k}\sum_{i,j}\frac{1}{ij}\cdot\left [ k \leq i, k \leq j \right ]=\sum_{i,j}\frac{1}{ij}\sum_{k}\left [ k \leq \min\left ( i,j \right ) \right ].\]即\[S_{n}=\sum_{i,j}\frac{1}{ij}\cdot\min\left ( i,j \right )=\sum_{i,j}\frac{1}{\max\left ( i,j \right )}=\sum_{m}\frac{1}{m}\sum_{i,j}\left [ \max\left ( i,j \right )=m \right ].\]即\[S_{n}=\sum_{m}\frac{1}{m}\cdot\left ( 2m-1 \right )=2n-\sum_{m}\frac{1}{m}=2-H_{n}.\]

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

。。按惯例笔记贴都是摘抄、转载的……TAT看了半天貌似还是不会写的样子……滚回去复习主席树了

Via NOCOW http://www.nocow.cn/index.php/Size_Balanced_Tree

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。

性质

Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树，它也因此得名。它总是满足：
对于SBT的每一个结点 t：

性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

如图（圈代表结点，三角代表SBT，下同）：

s[R] ≥ s[A]，s[B]
s[L] ≥ s[C]，s[D]

旋转

SBT的旋转（Rotations）与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

k ← right[t]
right[t] ← left[k]
left[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← right[t]

right[t] ← left[k]

left[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

k ← left[t]
left[t] ← right[k]
right[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← left[t]

left[t] ← right[k]

right[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

保持性质(Maintain)

当我们插入或删除一个结点后，SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程；Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。

第一种情况：s[left[left[t]]>s[right[t]]如图3，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
第二种情况：s[right[left[t]]>s[right[t]]在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
3. 在第1步和第2步过后，整棵树就变得非常不可预料了。万幸的是，在图7中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
4. 在第3步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
第三种情况：s[right[right[t]]>s[left[t]]
与情况1对称。
第四种情况：s[left[right[t]]>s[left[t]]
与情况2对称。

通过前面的分析，很容易写出一个普通的Maintain。

 If s[left[left[t]]>s[right[t]] then    //case1
      Right-Rotate(t)
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[left[right[t]]>s[right[t]] then   //case2
      Left-Rotate(left[t])
      Right-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[right[right[t]]>s[left[t]] then   //case1'
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(t)
      Exit
 If s[right[left[t]]>s[left[t]] then    //case2'
      Right-Rotate(right[t])
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Maintain(right[t])

Maintain(t)

Exit

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

Exit

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Maintain(left[t])

Maintain(t)

Exit

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。

 If flag=false then
       If s[left[left[t]]>s[right[t]] then      //case1
           Right-Rotate(t)
       Else
           If s[left[right[t]]>s[right[t]] then   //case2
                Left-Rotate(left[t])
                Right-Rotate(t)
      Else                                   //needn’t repair
           Exit
 Else
       If s[right[right[t]]>s[left[t]] then      //case1'
           Left-Rotate(t)
      Else
           If s[right[left[t]]>s[left[t]] then     //case2'
                Right-Rotate(right[t])
                Left-Rotate(t)
      Else                                    //needn’t repair
           Exit
 Maintain(left[t],false)                     //repair the left subtree
 Maintain(right[t],true)                     //repair the right subtree
 Maintain(t,false)                           //repair the whole tree
 Maintain(t,true)                            //repair the whole tree

If flag=false then

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Else

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Else //needn’t repair

Exit

Else

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Else

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Else //needn’t repair

Exit

Maintain(left[t],false) //repair the left subtree

Maintain(right[t],true) //repair the right subtree

Maintain(t,false) //repair the whole tree

Maintain(t,true) //repair the whole tree

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？

……且听下回分解

[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

偶然间翻PDF时看到了FHQ神犇的WC论文……看了一遍没记住什么……除了函数式编程其他也……就那样吧……顺手把CLJ的论文也看了一遍……//可持久化做法很多，函数式是种比较科学的实现……暴力复制、wzk树什么的就不说了……

然后函数式编程早就接触过但从来没有研究过TAT显然函数式线段树最成功的应用(之一?）就是主席树了……

函数式编程

修改元素是数据结构的一个基本操作，平常的实践中我们比较常见的就是直接改储存的值，而函数式编程中，我们从不去修改值，而是再定义一个。

对应在线段树操作中，我们每次修改值，都不会去修改任何节点，而是返回一棵新的树。

函数式Treap假想图函数式线段树

图片来自范浩强_wc2012谈谈各种数据结构

因为保证所有节点都不会被修改，所以我们可以重用未受影响的节点。显然，函数式线段树中，插入操作的时间、空间复杂度都是O(log n)，其他操作与正常线段树无异。

主席树

主席树是一种利用函数式线段树维护数列的数据结构，一般用来解决区间第K大数问题。设数列长度为NN，数据范围为n，已离散化。

不支持修改的主席树（前缀和主席树）

……不支持修改的主席树在我的笔记中记为前缀和主席树…自己取的名字。。。

前缀和主席树由N棵线段树组成，第i棵Ti是对于[1,i]建一棵以序列里的值为下标，储存区间里出现该值的次数的线段树，也可以看作是Ti-1插入a[i]后的线段树。

注意到所有的树是同构(?)的，Ts-1和Tt可以直接相减得到T[s,t]，在树上进行二分就可以得到区间K大值。

当然，所有的线段树都指函数式线段树。

代码：Via http://www.cnblogs.com/Rlemon/archive/2013/05/23/3094635.html 我自己码的实现惨不忍睹…这是和我的风格最接近的一个…以下是按我的笔记格式码的…

#define w(i) T[(i)].w
#define ls(i) T[(i)].ls
#define rs(i) T[(i)].rs
using namespace std;
const int MAXNN;
struct node{
    int ls,rs,w;
    node(){ls=rs=w=0;}
}T[MAXNN*20];
int a[MAXNN],root[MAXNN],sz,m;

void ins(int &i,int l,int r,int x){
    T[++sz]=T[i]; i=sz;
    w(i)++;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) ins(ls(i),l,m,x);
    else ins(rs(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k){
    if (l==r) return l;
    int t=w(ls(j))-w(ls(i));
    int m=(l+r)>>1;
    if (t>=k) return query(ls(i),ls(j),l,m,k);
    else return query(rs(i),rs(j),m+1,r,k-t);
}
int main(){
        //DO YOLO
        root[0]=0;
        sz=0;
        for (int i=1;i<=N;i++){
            root[i]=root[i-1];
            ins(root[i],1,n,a[i]);
        }
        //支持操作：
            //QUERY(s,t,k):query(root[s-1],root[T],1,n,k);

    return 0;
}

#define w(i) T[(i)].w

#define ls(i) T[(i)].ls

#define rs(i) T[(i)].rs

using namespace std;

const int MAXNN;

struct node{

int ls,rs,w;

node(){ls=rs=w=0;}

}T[MAXNN*20];

int a[MAXNN],root[MAXNN],sz,m;

void ins(int &i,int l,int r,int x){

T[++sz]=T[i]; i=sz;

w(i)++;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) ins(ls(i),l,m,x);

else ins(rs(i),m+1,r,x);

}

int query(int i,int j,int l,int r,int k){

if (l==r) return l;

int t=w(ls(j))-w(ls(i));

int m=(l+r)>>1;

if (t>=k) return query(ls(i),ls(j),l,m,k);

else return query(rs(i),rs(j),m+1,r,k-t);

}

int main(){

//DO YOLO

root[0]=0;

sz=0;

for (int i=1;i<=N;i++){

root[i]=root[i-1];

ins(root[i],1,n,a[i]);

}

//支持操作：

//QUERY(s,t,k):query(root[s-1],root[T],1,n,k);

return 0;

}

支持修改的主席树（树状主席树）

还记得当年学数据结构时如何维护带修改区间[s,t]的区间和吗？

树状数组，简单高效。既然我们维护的是一个线段树的前缀和，何不用树状数组维护呢？

脑补一棵树状数组，每个节点是一棵线段树。修改时，我们仅需修改log n棵线段树即可。

//貌似只有我叫它树状主席树……正解是树状数组套主席树。

代码

#define ls(i) T[i].ls
#define rs(i) T[i].rs
#define w(i) T[i].w

using namespace std;
const int MAXNN;
struct node{
    int ls,rs,w;
    node(){ls=rs=w=0;}
}T[MAXNN*20];
vector<int> Ql,Qr;
int n,m,sz,NN;

int a[MAXNN],root[MAXNN],rooto[MAXNN];
inline int lowbit(int x){
    return x&-x;
}
void build(int &i,int l,int r,int x){
    T[++sz]=T[i]; i=sz;
    w(i)++;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) build(ls(i),l,m,x);
    else build(rs(i),m+1,r,x);
}
void ins(int &i,int l,int r,int x,int v){
    if (i==0){ T[++sz]=T[i]; i=sz; }
    w(i)+=v;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) ins(ls(i),l,m,x,v);
    else ins(rs(i),m+1,r,x,v);
}
void BITins(int pos,int x,int v){
    for (int i=pos;i<=NN;i+=lowbit(i)){
        ins(root[i],1,n,x,v);
    }
}
int  STquery(vector<int> Q1,vector<int> Q2,int l,int r,int k){
    if (l==r) return l;
    int c=0;
    int m=(l+r)>>1;
	//查询[l,m]
    for (int i=0;i<Q1.size();i++) c-=w(ls(Q1[i]));
    for (int i=0;i<Q2.size();i++) c+=w(ls(Q2[i]));
	//线段树上二分
    for (int i=0;i<Q1.size();i++) Q1[i]=(c>=k?ls(Q1[i]):rs(Q1[i]));
    for (int i=0;i<Q2.size();i++) Q2[i]=(c>=k?ls(Q2[i]):rs(Q2[i]));

    if (c>=k) return STquery(Q1,Q2,l,m,k);
    else return STquery(Q1,Q2,m+1,r,k-c);
}
int query(int l,int r,int k){
    Ql.clear();Qr.clear();
	//原始数组
    Ql.push_back(rooto[l-1]);
    Qr.push_back(rooto[r]);
	//操作数，用树状数组维护
    for (int i=l-1;i>0;i-=lowbit(i)) Ql.push_back(root[i]);
    for (int i=r;i>0;i-=lowbit(i)) Qr.push_back(root[i]);
    return STquery(Ql,Qr,1,n,k);
}
int main(){
    //DO YOLO
    sz=0;
    memset(rooto,0,sizeof(rooto));
    memset(root,0,sizeof(root));
    for (int i=1;i<=n;i++){
        rooto[i]=rooto[i-1];
        build(rooto[i],1,n,a[i]);
    }
    //支持操作：
	//UPDATE(x,v):[
	//    BITins(x,a[x],-1);
	//    BITins(x,v,1);
	//    a[x]=v;
	//]
	//QUERY(s,t,k):[
	//    query(s,t,k);
	//]
}

#define ls(i) T[i].ls

#define rs(i) T[i].rs

#define w(i) T[i].w

using namespace std;

const int MAXNN;

struct node{

int ls,rs,w;

node(){ls=rs=w=0;}

}T[MAXNN*20];

vector<int> Ql,Qr;

int n,m,sz,NN;

int a[MAXNN],root[MAXNN],rooto[MAXNN];

inline int lowbit(int x){

return x&-x;

}

void build(int &i,int l,int r,int x){

T[++sz]=T[i]; i=sz;

w(i)++;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) build(ls(i),l,m,x);

else build(rs(i),m+1,r,x);

}

void ins(int &i,int l,int r,int x,int v){

if (i==0){ T[++sz]=T[i]; i=sz; }

w(i)+=v;

if (l==r) return;

int m=(l+r)>>1;

if (x<=m) ins(ls(i),l,m,x,v);

else ins(rs(i),m+1,r,x,v);

}

void BITins(int pos,int x,int v){

for (int i=pos;i<=NN;i+=lowbit(i)){

ins(root[i],1,n,x,v);

}

int STquery(vector<int> Q1,vector<int> Q2,int l,int r,int k){

if (l==r) return l;

int c=0;

int m=(l+r)>>1;

//查询[l,m]

for (int i=0;i<Q1.size();i++) c-=w(ls(Q1[i]));

for (int i=0;i<Q2.size();i++) c+=w(ls(Q2[i]));

//线段树上二分

for (int i=0;i<Q1.size();i++) Q1[i]=(c>=k?ls(Q1[i]):rs(Q1[i]));

for (int i=0;i<Q2.size();i++) Q2[i]=(c>=k?ls(Q2[i]):rs(Q2[i]));

if (c>=k) return STquery(Q1,Q2,l,m,k);

else return STquery(Q1,Q2,m+1,r,k-c);

}

int query(int l,int r,int k){

Ql.clear();Qr.clear();

//原始数组

Ql.push_back(rooto[l-1]);

Qr.push_back(rooto[r]);

//操作数，用树状数组维护

for (int i=l-1;i>0;i-=lowbit(i)) Ql.push_back(root[i]);

for (int i=r;i>0;i-=lowbit(i)) Qr.push_back(root[i]);

return STquery(Ql,Qr,1,n,k);

}

int main(){

//DO YOLO

sz=0;

memset(rooto,0,sizeof(rooto));

memset(root,0,sizeof(root));

for (int i=1;i<=n;i++){

rooto[i]=rooto[i-1];

build(rooto[i],1,n,a[i]);

}

//支持操作：

//UPDATE(x,v):[

// BITins(x,a[x],-1);

// BITins(x,v,1);

// a[x]=v;

//]

//QUERY(s,t,k):[

// query(s,t,k);

//]

}

临时建立节点的主席树

//待补完
参见clj的wc论文

[Dream YOLO]保平语录 (Ver.3 Expanded)

Aside

林保平是三明二中（三明市第二中学）的一名数学老师，也是我目前的数学老师。林保平老师经验丰富，功力深厚，语录层出不穷……

Via http://user.qzone.qq.com/519630380/blog/1376798868

完整版的保平语录~！你，值得拥有哦，欢迎分享和转载及提供遗漏的保平语录~

前言

高中后两年有幸成为保平老师的学生，再次整理本人两年所记全部保平语录，及引用池童鞋的高一版本。为避免重复，稍有删减。

正文

1.（指着某个令人发晕的多项式）你看这个式子非常优美，是不是？（好想说不是）

2.我们死活要证明这个点是存在的！（死了都要证）

3.（说明纯粹性和完备性）清一色，没有XX在这儿，都是15班的同学！（这就是纯粹性) 只此一家，别无分店！（完备性）

4.这是一种感情的自然流露哇~！（挥动教鞭作自然流露状）

5.来，余熙萌同学你来回答一下（佘萌熙：……）

6.在那遥远的地方..（我们的视线已经随着他教鞭所指飞出了教室）..还有一个交点！！（这想象力）

7.不要求你们换元！心中有元就好办！（我心有元~）

8.u是谁？u是谁？！括号里的都是u，心中的u就是它！（好动人）

9.这道题减轻了同学们的负担，只求了一次导！（原来还有二次求导，三次求导..）

10.这是最严格的证明！无懈可击的，滴水不漏！（脑海中都有画面了）

11.（讲三次函数x^3轨迹）你一辆车在上面开，肯定先往左拐，然后过了原点他就是向右拐的！（飞一般的想象力）

12下面使我们最熟悉的二次函数x^2的曲线，我就不求导了，要求的话也很简单，2x！（忍不住就求了个导）

13.多项式函数是最最可爱的函数！（可爱在哪儿了…）

14.黑板不能转哦，不然很想转过来给你们看一下的。（这就是数学的力量）

15.那时候我17岁，我觉得国家就要变革了！！（瞬间回到了三十年前青涩的时代）

16.《几何》原本的印刷量仅次于《圣经》，真可以说是不朽的著作了！（真不朽..）

17.（讲推理）步步可逆，慎之！（谨记..）

18.综合运用综合法和分析法那不就是两头凑嘛？（凑出个未来）

19.其实伽利略不用做什么自由落体试验了，用我数学就证出来了！（数学威武..）

20.解推理题的十六字方针：发展条件，转化结论，寻找联系，实现沟通！（提纲掣领的十六字）

21.要证a(x1-x2)=0，设a=0……推出x1-x2≠0，那只能a=0了！只好逼良为娼了！ (好个逼良为娼..)

22.如果你认为某个数a可以被n^2整除却不能被n整除，那你就厉害了，你可能患了很严重的病，但你成为了数学界的一颗新星！（难道有某种联系？）

23.（讲多米诺骨牌）把那么一大堆东西推倒掉，有一种成就感,ho~ （爽快的成就感）

24.假设某个人要爬很高的楼梯，那就是千里之梯，始于足下！（语文老师一直强调的化用）

25.你不能从形式上证明它就要从内心接受它，不然你们会出现很多悲剧的… （看来已经出现了许许多多悲剧）

26.个人的经历，与世无争–整数；我借你一块橡皮，你要还我–负数；一个苹果分成四半–分数（好比方）

27.复数还是一个牙医发现的哟~ （潜台词：各行各业的同学们欢迎开创数学新天地啊！）

28.（讲复数和虚数单位i）就是可爱，灰常可爱！（保平的独特视角）

29.（提问）你来！你敢不敢讲！（讲了要被批斗吗..？）

30.石有豪同学你来回答一下！石有豪：这个函数嘛……（犹豫中）保平（急切地）：讲的太好了！！（真是心有灵犀一点通，外人一头雾水中）

31. 数系的扩充反映了数学客观规律的“真”，复数在科学中的应用体现了数学功利的“善”，实数与虚数的对立统一体现了数学和谐的“美”！（真善美也在此现身了..）

32.f(x)在这一点发生了从量变到质变的戏剧性的深刻变化！（进化了吗..？）

33.对于球匣模型的种类数就记成求子心切（球指心切的谐音，球数就是指数) （从此再也没忘记过）

34.假设我今天等车，等了π分钟.. （已经超神了）

35.走13个台阶，一次能跨一个或者两个台阶。你一天换一种花样，一年都走不完！（花式走台阶大赛？）

36.0.5的下一个数是什么？你肯定说不出来，你要是说出来你就是世界上最伟大的人了！（咦？是0.6吗？）

37.（讲挑废品题）你可能是一个运气很不好的人。应该是极差！一直取一直取到的的都是废品.. （神衰）

38. 看你们大多数人的眼神就知道你们听的懂。（保平读心术）

39.（若干人排队抽奖）第一个人没中，第三个人窃喜：哎呀，好事儿！（神态毕肖）

40. 两件事情互斥，我把它叫做不共戴天；两件事情独立，我把它叫做井水不犯河水。（浮想：“某某，你记着，从今以后我跟你互斥了！”）

41.把n改写成P( i ) 显然是一脉相承的！（云里雾里，..承哪儿了？？）

42.（讲射击比赛）容易失常也容易超常，说不定在乱棍之中就把他打赢了！（不是射击比赛吗？）

43.（讲正态分布曲线）不胖也不瘦，非常优美！（PS:手感好~）

44.函数的三种变化我把它叫做拉风琴，滑冰和跳皮筋！（原来函数也进入了全民健身时代）

45.据我观察，15 16班还没有3σ（读sigma）以外的人…结论：大家都是3σ以内的人，要同舟共济啊！（这扯得回来…）

46.（讲正态分布曲线的变化）先拉长再压扁，祸不单行！两个方向都促使它变胖，一拉一压，胖的要命！（搓圆圆捏扁扁的正态曲线已经无地自容了..）

47. 你想要实现你的理想，仅仅做一次实验是几乎不可能的。你要二次革命，三次革命…（怎么突然变成革命了…)

48. 说不定某一天你就在随机事件和必然事件的碰撞中结束了你的一生。（过公路是必然事件，飞来一辆车好比是随机事件。你就…）

49. 其实你的一生就是无数个随机事件和必然事件的组合。说不定在某一次随机事件中你就过早地结束了你的生命。（悲剧人生啊！）

50. 什么是无悔的人生？用现在的话来讲叫hold（一边板书hold）。把握必然事件，转化随机事件为对你有利的必然事件就行了。 (同学们，你们要hold住啊！)

51. （评论同学当场解题）哦？我这也给你捏把汗了ho~！（十分体贴哪）

52. （讲逆矩阵）就是左乘等于他，右乘也等于他，就是这样了！（潜台词：你们咋就听不懂呢？）

53. 你们就做在书上啰？要是写作业纸上过不了几天你们就拿去折飞机了…（潜台词：你们这些长不大的小盆友啊~）

54.特征值和特征向量总是成双成对的，对吧！（诶？还真是）

55. （讲向量）严格来说是要写箭头的，因为手写很难写加粗的黑体字，ho～（其实明明可以写）

56. 你做梦都想不到它们是垂直的！（答：我做梦当然想不到了。。）

57. （极坐标新课：讲到国外某一个奇葩的城市街道分布）有什么红白喜事，或者什么随机事件发生了，只要知道在哪一条街，距离皇宫多远就可以了（发生了某件可怕的随机事件。。）

58. 此t非彼t也！（彼读第二声，说完发现有谐音，不对劲）

59. 你不敢加它？我就敢加它！（看来这真的需要很大的勇气）

60. （讲化简多项式）把这个代进来，先过瘾一下再说。（原来化简也能过把瘾~）

61. 这道题证明他是不要证明的。（感情让我们直接写易得？）

62. 这种题在联赛中是二试的大题。考查一个人的头脑，做出来的才能成为党和国家领导人。（诶？突然把数学竞赛和官员选拔建立起某种联系）

63. 我很怕计算，ho～（我们也很怕的说）

64. 用反证法往往可以出奇制胜，呈现柳暗花明又一村的局面！（潜台词：这是你们必备的新技能啊！）

65. 时空，时空，三维空间加一维时间，懂不懂？东方时空啊！…（《东方时空》莫名中枪）

66. 柯西≠式（柯西不等式的极简版，还见过写成C≠的版本，以及“△≠”（三角不等式））

67. 柯西不等式可以简记为“平方的和的乘积≥乘积的和的平方” （真的很好记！，就是绕口）

68. （指着一个让人头大的不等式）非常好玩的，你们看！（底下同学内牛满面…）

69. 跟你们比隔壁班同学这次是“用心躁也” （这水平教语文肯定够了吧~）

70. 我们先把下节课的内容先回顾一下！（神一般的回顾啊~）

71. （审视板书）有一句话我贪污掉了，没写！（好诚实的保平！）

72. 恰有一个解不就是这两个函数图像亲密接吻的时候嘛？（数学的浪漫啊~！）

73. 有的同学在今天上交的作业上写“老师，我升学无望了”。如果你觉得做这种题会让你生活的道路越走越窄，那你还是别做了…（该同学：其实我是开玩笑的，嘿嘿~（不是笔者啊！））

74. 简单点！用行话来说！（传说中的正品行话）

75.（讲定积分题）到底是哪个被积了啊！？（积第一声，内涵）

76. 先四等分再画，我把他叫做先斩后奏！（古词新意）

77. （讲正余弦定理）这些都是如雷贯耳的公式，天天用不用说了ho~ （大名鼎鼎的公式…）

78. 找到基底后，你就咬定基底不放松！（轻巧的化用呢）

79. 这里有个好的三角形哦！我画的还不错吧~ （画个坏的看看？）

80. 底下，一切尽在不言中。（此处省略XX字，难道这就是解题的某种高境界？）

81. 看你们底下一个个鸦雀无声我就知道你们理解有问题了（小样，早看穿你们了）

82. 法向量法堪称是传统与现代相结合的做法！（看不出来啊…）

83. 你怎么能非法建系呢？！（我还违章建系呢~）

84. 纯碱不是碱，截距不是距！（硬扭过来都行…）

85. 这种题！（蔑视状）高考古今中外都不会考的！（古今中外的高考…）

86. 要不要挖点？你自己想！肯定要挖的！（潜台词：你们很傻啊！）

87. 抛物线在动，直线也在动。哎呀，吓死人呢！（倒退作惊吓状，毕肖）

88. 这题直接用民间小结论处理！不算是走江湖。（大家喜闻乐见的民间小结论又出现了）

89. 那出题的挖空心思才想到这道题。（潜台词：他没什么技术含量的，不要怕！）

90. 倒一，倒三，哎呀，我数学不及格.. （底下面面相觑中）

91. XX，你怎么空掉作业还睡那么香呢！（潜台词：你这孩子，真让我心痛啊~）

92.你们班怎么就十几个人记住？隔壁班几乎都举手说记住了，看来他们都在撒谎…！（本来已经听得有点惭愧了，突然觉得保平好人啊！！）

93. 俗话说有限的古典，无限的几何… （俗语没听过，不过记住了古典概型与几何概型的差别，那俗语就是保平said的吧！）

94. 这道题，哎呀！（痛心疾首状）小学生都会做，你们到现在还不会！（底下沉浸在没文化的悲伤中…）

95. 这道题有没有勾引起你们的回忆吖？（兴致盎然状） {全班沉默了5秒}唉，真让我伤心啊… （勾引…）

96. 人家一开始就构造函数，你很郁闷：我怎么就想不到呢？那就要等到瓜熟蔕落水到渠成了！（语文真好…）

97. 这道题我看过很多解法，（停顿）我的肯定是最好的！（全班热烈鼓掌！太帅了）

98.（论走江湖）不是教你们使坏，是教你们跟他们公平竞争！（原来大家都在走江湖~）

99.你们可以跟我异口同声地讲出来！（齐唱:五十六个民族，…）

100.你们班班风纯朴！（良民大大的~）

101.合理争分体现了一个人的基本素质！（突然觉得很没素质…）

102.这个函数是越来越平还是越来越缓啊… （教我如何回答….）

103.大佐：老师，这题选A还是B？保平：对！（大佐当场阵亡！）

104. 这道大题，你在旁边写上：只配作小题！（该大题泪奔了…）
105.[以下是最后一节课的语录] 生活就是生活，生活没有那么多的充要条件。（举不出例子…）

106.有时候你发现，题太难，人在江湖，身不由己啊！（骑虎难下不觉已三年，一说泪双流…）

107.高考完提纲你们全部不客气地烧掉！把它烧掉！（手中教材作投火炉状）（好～不过烧了就没有这篇文章了…）

108.在我们班有的夹着尾巴做人的人到时候就露出来了（潜台词：到时候就看见你露出马脚了吧~）

109.对待生活，你与其抱怨，不如勇敢地抗争！（永远不要低估一颗冠军的心！）

110.有志者事不一定成，但以后你回忆时是不会留下遗憾的。（保儿柯察金曾经说过：人…）

111.你们可以利己，但是不能损人；可以不高贵，但不能无耻！（仰望保平中。。）

112.（还是在最后一节课）希望你们将来不仅要摆正自己，善待他人，而且要正视现实，坚守底线！（精神导师保平呕心沥血讲课的场景历历在目~）

113.祝同学们未来生活的道路越走越宽！（迈向明日~）

【Bonus】

114.ABCDE中的三个人分别去北京，巴黎，纽约旅行，A不能去北京。那么我们先把A关进厕所讨论BCDE的情况。。（A：我不要关进厕所…..）

【The End】十四五六青衫湿，保平老师知不知？

附：池童鞋在高一整理的保平语录。

【保哥said】:

1.古今中外从来都没有考过这么简单的五分题！考填空选择是不可能的！！！（此处情绪激动地挥手）

2.这个国际惯例是要写成区间的……懂不懂啊？国际惯例都是这样的。（从前怎么没听过有这玩意…）

3.f(x)大于零，那f的三角形是不是也要大于零啊！那f的苹果是不是也要大于零啊！是不是这样子啊！（是！f的梨子香蕉什么的都大于零！）

4.闹了半天……（语速要慢）

5.这个大于零，这个也大于零，那两个搞在一起不就大于零嘛！（潜台词：你们很傻啊！）

6.这道题，我们死活要证明……（“死活要证明”要读重音）

7.证明完了我们就可以理直气壮的……！（“理直气壮”要读的理直气壮）

8.默认状态下……（电脑课？）

9.最终的结局是什么玩意吖？（语速要慢，“什么玩意吖”要一个字一个字连续拖着读）

10.哪儿啊~？（三个字要缓慢的有连续性的读）

11.这个函数图像我一般都把它叫做腰斩，这个函数图像我叫它截肢！（应该补一句：我很有创意吧）

12.这道题听懂了没有啊？哎呦，你们怎么会这么差啊！我真的想不通有的人是怎么混进15班的队伍里的！有的同学真的是很差啊！（要做出真的搞不清楚的表情）

13.这道题错掉的同学完全就是脑袋混乱，定义不清楚！实在是差啊！（厌恶状）

14.这道题不会的同学月考是很成问题啊！（恨铁不成钢状）

15.这个定义域是不是xxx啊？哎呦！实在太差了！极差！（愤恨状）

16.正的负的？（负的！）把绝对值拗弯掉！正的负的？（正的！）正的直接脱！（连接要快）

17.我们偷偷代一个数进去……（要有偷偷的感觉，轻声读）

18.看图说话都不会！小学生都不如！怎么上高中的！！（小学生还不懂函数图像呢……）

19.敢不敢用端点代啊？还再说用端点代！用端点代改卷老师一看，实在差！连本三都没有！（语速十分快，并且最后一句语气要十分之重……）

20.你们这种题目都不会做啊？哎呦！本三都上不了！（我们的目标是大专……）

21.哎呦！我们看看，这道题实在是好做啊！整份卷子这道题最简单了！是不是这样子啊！（其实很想说不是……）

22.15个班只有我们班可能有讲……（老大，我们是16个班咧…某个倒霉的班级被忽略了）

23.f (x)大于零，f 的小明是不是也要大于零啊！……（省略f的小红、f 的小白、f的小绿…）

24.于是乎……（重读并且拖着念…）

25.换言之……

26.这样一来，我们就可以搞出来这个东西了！（搞出- -）

27.你们有些同学凭着良心说，是不是真的很差！（边做出摸良心的动作）

28.下面我们再来看一道题，这道题带我们进入了整节课的高潮了！（高潮- -…）

29.今天我们从后面开始体验经典。

30.哎呦，这个函数图像是不是非常可爱，非常漂亮啊~~~（数学境界到一定程度了……）

31.好的好的，那么……（“的”要用第一声读）

32.这道题给我们一个启示……（题目也可以有启示的！）

33.这个条件题目是不是已经告诉咱啦？（注意“咱”）

34.用-x代替x。（x请读成s，并且此处要拿本新坐标犹抱琵琶半遮面）

35.地球人都知道。

36.我们的目标……（很想说没有蛀牙(⊙-⊙)）

37.奇函数偶函数就像函数大海里的几朵浪花，奇函数是一朵，偶函数是一朵……（这个比喻完全超越语文老师水平！）

38.有平方做后盾！（补：可以直接脱！）

39.把 f 的3吃掉，吃掉它！（味道好不好…）

40.我们要上升到理论的高度。

41.我们画出这个函数，要画漂亮一点……

42.在我们十四班（我们是十五班…）揪出一个最小的，十五班再揪出一个最小的，抓到了！（哇塞…真厉害，这都能抓到- -）

43.考古学家挖出死尸一般都要看看它什么时候出生的……（没见过考古学家研究出生日期的- -!）

44.一层层脱！（咳咳，要纯洁）

45.哎呦，原来是它！

46.非常过瘾！（此处一只手抱着另一只手，握在胸前，目光要真挚无邪）

47.（44、45、46连起来看，要纯洁哦！嘿嘿……不解释）

48.书上根本不讲道理的！（保平哥就是真理）

49.数学概念的引进要看运算性质是否和谐，要遵循和谐美。（共建和谐社会）

50.一样样的。（小沈阳附身？）

51.我们进入下一个凡节。（环节……）

52.（保平哥在黑板上写：（-3）^3=8）：负3是负8的立方根。（我们：负2！）负2是8的立方根。（我们：负8！）哎，今天犯错误了…（要做出对不起的样子）。然后又说：8的立方根是负2（我们：负8…–!）……

被指不敬业了…啦啦啦…运动会前来享受一次保平哥的教诲吧！

53.同学们一看到这个就有一种冲动，合在一起没商量！（我们老冲动了…）

54.根式的运算要用心除。（用心去感受）

55.同学们别混了。（还是读书好！）

56.那我们就可以求f(1)、f(2)、f(3)（逐个加重的读，要深沉！）

57.很生动的体现出……（函数图像，就是这么生动！）

58.常言道…

59.这边，我们要找个桥。（做数学作业还要找桥…）

60.注意我是怎么措辞的。（多么具有美感的语言表达）

61.过去的事情忘记掉！（手上拿着粉笔擦激烈地在黑板上挥动，然后转身扔到讲台桌！尘烟四起…）

62.（幕布挡住了函数图像）保哥：有没有最大值？有没有最大值？有没有最大值啊！（一只手激动地把幕布掀起来…）

63.昭然若揭。（我愣了…因为字不会写）

64.如法炮制。（丰富的语言词汇）

65.过去的事一笔勾销！（上数学课顺便积累词汇量）

66.中心在哪？中心在哪？！中心在哪！（把我们吓得呦…）

67.手感很不好，是尖点！（咳咳，纯洁，不解释）

68.最大值在很遥远的地方，五万里高空~（真够远的…）

69.正数的任何次方都是正数，这是经典名言啊，同学们！（知道了，老师！）

70.很大很大很大，灰常灰常大，同学们展开想象的翅膀。（I believe I can fly……）

71.在本三线上挣扎的同学们，这是灰常低级的错误！（我们都是本三的娃）

72.负二乘上负五分明等于负十，是不是呀？（不是…）

73.这道题你们该不会是换元吧？换什么元！心中有元就可以了！（我们的心是如此庞大）

74.你们要记住这些民间小结论呀，很好用的！（民间小结论- -）

75.哎呦，看到一个0.06，灰常诱人啊~（第一次听说诱人的数字）

76.这里有个灰常受欢迎的东西~~~~（大家快来做啊！）

77.强行提出一个三分之二！（我们要霸道！）

78.两边同除a是合情合理又合法的。（我们是遵纪守法的好孩子）

79.无条件的脱！（脱你没商量）

80.全国只有海南、宁夏、福建三个最落后的省用这本教材。（老师好直接啊）

81.y要有东西割啊！哪怕把P眼割掉也可以！把P眼搞掉！（迄今为止，老师说的唯一一句貌似粗话的粗话）

82.函数有一个中心，两个基本点。（小平爷爷的话都可以套用函数了）

83.你能一次就找到零点，那是命大福大造化大。（真是幸运…）

84.不要乘开，更不要配方！你们初中都是乘开，配方！乘开很傻！配方更是傻上加傻！（感情我们一直都傻着）

85.没想别的方法，就是通分，你还在犹豫什么？（赶紧下手吧！）

86.你念了高中，连这种国民基本要掌握的常识都不知道，那真是不行了。（全民学函数）

87.（老师解释农民卖菜是否喷农药）：这还是跟你个人的操守有关。

88. 还是不要直接用张角定理，民间小结论用起来是有风险的懂吗？

【End】

终于完整了~ 天苍苍，野茫茫，老夫聊发少年狂~

!感谢池瑜馨、廖思忆、向维成、严晨、锦鹏等童鞋的大力支持，得以完成语录的大致搜集！

欢迎分享及转载，若发现有遗漏和错别字请与笔者联系，可以评论或留言哦！一定收录及更正。

谢谢! 海于13.8.18

[Dr.Lib]Note:Data Structures – Size Balanced Tree – II

[Dr.Lib]Note:Math – Iverson bracket

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

性质

旋转

保持性质(Maintain)

[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

函数式编程

主席树

不支持修改的主席树（前缀和主席树）

支持修改的主席树（树状主席树）

临时建立节点的主席树

[Dream YOLO]保平语录 (Ver.3 Expanded)

Aside

朋友们

TAG CLOUD