[Dr.Lib]Note:Algorithm – SSSP

最短路是图论中的基础，单源最短路SSSP是基础的基础（2333自己发明的名言……

关于图论算法之前只说了存图……唔今天先复习一下SSSP的几个算法。

Dijkstra

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define PB(x) push_back(x)
#define PS(x) push(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long LL;

const int MAXN=10000;
const int INF=2147483647;
const int NINF=-1<<31;
const int ERR=-1;
bool getint(int &x){
    x=0;int n=1;
    char c=getchar();
    while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}
    while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;
    return true;
}
void priint(int k){if(k==0)putchar('0');if(k<0){putchar('-');k=-k;}
    int t=0;char ch[30];
    while(k>0)ch[++t]=k%10,k/= 10;
    while(t)putchar(ch[t--]+'0');  
    putchar(32);  
}
//以上是渣优化……

typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > Q;
struct P{int t;int v;
	P():t(0),v(0){}
	P(int st,int sv){t=st;v=sv;}
};
vector<P> M[MAXN];
int D[MAXN];
int n,m;int s,t;
int main(){
	getint(n);getint(m);
	while(m--){
		int s,t,v;
		getint(s);getint(t);getint(v);
		M[s].PB(P(t,v));
	}
	for(int i=0;i<n;i++){D[i]=INF>>1;}
	getint(s);
	Q.PS(MP(0,s));D[s]=0;
	while(!Q.empty()){
		PII pp = Q.top(); Q.pop();int ps=pp.second;
        if(pp.first != D[ps]) {continue;}
        for(int i = 0; i < M[ps].size(); i++)
        {
            int pt = M[ps][i].t;
            int pv = M[ps][i].v;
            if(D[pt] > D[ps] + pv)
            {
                D[pt] = D[ps] + pv;
                Q.PS(MP(D[pt], pt));
            }
        }
	}
	for(int i=0;i<n;i++)
    {
		priint(D[i]);
    }
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define PB(x) push_back(x)

#define PS(x) push(x)

#define MP(x,y) make_pair(x,y)

using namespace std;

typedef long long LL;

const int MAXN=10000;

const int INF=2147483647;

const int NINF=-1<<31;

const int ERR=-1;

bool getint(int &x){

x=0;int n=1;

char c=getchar();

while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}

while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;

return true;

}

void priint(int k){if(k==0)putchar('0');if(k<0){putchar('-');k=-k;}

int t=0;char ch[30];

while(k>0)ch[++t]=k%10,k/= 10;

while(t)putchar(ch[t--]+'0');

putchar(32);

}

//以上是渣优化……

typedef pair<int,int> PII;

priority_queue<PII,vector<PII>,greater<PII> > Q;

struct P{int t;int v;

P():t(0),v(0){}

P(int st,int sv){t=st;v=sv;}

};

vector<P> M[MAXN];

int D[MAXN];

int n,m;int s,t;

int main(){

getint(n);getint(m);

while(m--){

int s,t,v;

getint(s);getint(t);getint(v);

M[s].PB(P(t,v));

}

for(int i=0;i<n;i++){D[i]=INF>>1;}

getint(s);

Q.PS(MP(0,s));D[s]=0;

while(!Q.empty()){

PII pp = Q.top(); Q.pop();int ps=pp.second;

if(pp.first != D[ps]) {continue;}

for(int i = 0; i < M[ps].size(); i++)

{

int pt = M[ps][i].t;

int pv = M[ps][i].v;

if(D[pt] > D[ps] + pv)

{

D[pt] = D[ps] + pv;

Q.PS(MP(D[pt], pt));

}

for(int i=0;i<n;i++)

{

priint(D[i]);

}

return 0;

}

SPFA

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define PB(x) push_back(x)
#define PS(x) push(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long LL;
const int MAXN=10000;
const int INF=2147483647;
const int NINF=-1<<30;
const int ERR=-1;
bool getint(int &x){
    x=0;int n=1;
    char c=getchar();
    while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}
    while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;
    return true;
}
void priint(int k){if(k==0)putchar('0');if(k<0){putchar('-');k=-k;}
    int t=0;char ch[30];
    while(k>0)ch[++t]=k%10,k/= 10;
    while(t)putchar(ch[t--]+'0');  
    putchar(32);  
}

queue<int> Q;
struct P{int t;int v;
	P():t(0),v(0){}
	P(int st,int sv){t=st;v=sv;}
};
vector<P> M[MAXN];
int D[MAXN];bool inQ[MAXN];int T[MAXN];
int n,m;int s,t;
bool NL;

int main(){
	getint(n);getint(m);
	while(m--){
		int s,t,v;
		getint(s);getint(t);getint(v);
		M[s].PB(P(t,v));
	}
	for(int i=0;i<n;i++){D[i]=INF>>1;}
	getint(s);
	D[s]=0;
	Q.PS(s);inQ[s]=1;
	while(!(Q.empty()||NL)){
		int ps=Q.front();Q.pop();
		inQ[ps]=0;
		for(int i=0;i<M[ps].size();++i){
			int pt=M[ps][i].t;int pv=M[ps][i].v;
			if(D[pt]>D[ps]+pv){
				D[pt]=D[ps]+pv;
				Q.PS(pt);inQ[pt]=1;
				if(++T[pt]>n){NL=1;}
			}
		}
	}
	if(NL){printf("Native Loop");return 0;}
	for(int i=0;i<n;i++){
		priint(D[i]);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define PB(x) push_back(x)

#define PS(x) push(x)

#define MP(x,y) make_pair(x,y)

using namespace std;

typedef long long LL;

const int MAXN=10000;

const int INF=2147483647;

const int NINF=-1<<30;

const int ERR=-1;

bool getint(int &x){

x=0;int n=1;

char c=getchar();

while(((c-'0')>=10)||((c-'0')<0)){n=1;if(c=='-')n=-1;c=getchar();if((int)c==-1)return false;}

while(((c-'0')<10)&&((c-'0')>=0)){x=x*10+(c-'0');c=getchar();}x*=n;

return true;

}

void priint(int k){if(k==0)putchar('0');if(k<0){putchar('-');k=-k;}

int t=0;char ch[30];

while(k>0)ch[++t]=k%10,k/= 10;

while(t)putchar(ch[t--]+'0');

putchar(32);

}

queue<int> Q;

struct P{int t;int v;

P():t(0),v(0){}

P(int st,int sv){t=st;v=sv;}

};

vector<P> M[MAXN];

int D[MAXN];bool inQ[MAXN];int T[MAXN];

int n,m;int s,t;

bool NL;

int main(){

getint(n);getint(m);

while(m--){

int s,t,v;

getint(s);getint(t);getint(v);

M[s].PB(P(t,v));

}

for(int i=0;i<n;i++){D[i]=INF>>1;}

getint(s);

D[s]=0;

Q.PS(s);inQ[s]=1;

while(!(Q.empty()||NL)){

int ps=Q.front();Q.pop();

inQ[ps]=0;

for(int i=0;i<M[ps].size();++i){

int pt=M[ps][i].t;int pv=M[ps][i].v;

if(D[pt]>D[ps]+pv){

D[pt]=D[ps]+pv;

Q.PS(pt);inQ[pt]=1;

if(++T[pt]>n){NL=1;}

}

if(NL){printf("Native Loop");return 0;}

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

priint(D[i]);

}

return 0;

}

SPFA不仅是SSSP的一个算法，而更多的是一种思想。

国家集训队2009论文集SPFA算法的优化及应用

[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: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]NOIP2013提高组酱油报告

370/600。
还不错的成绩。
但。。。怨念的是。。D1T2的10分。。
D1
T1
显然是快速幂。。
T2
显然当上下两序列同序（对应数字排名相同时和最小。
由于要求同序所以说序列一的顺序是无关紧要的，按序列一排序后我们只需再把序列二排序即可。由于交换一次至多消除一个逆序对，答案就是按序列一排序后的逆序对数。
至今不知哪写傻了，10分。
T3
当时写了一个裸并查集。。60。。
和YY聊了聊才发现应该先跑一个最大生成树的。。
D2
T1&T2都是喜闻乐见的题型。
n^2可以做，nlogn可以做，线性也可以做。。
我们那考场一位大神两题写了五个线段树（T1真的很像线段树操作喂。。
T1推了15分钟差分，5分钟码代码，10分钟对拍。
T2第一眼看过去是DP，看了下数据范围不大对了。
思考了五分钟，发现可以用数据结构优化。
先码了一个裸DP，试了一下貌似还可以，于是又推了一会题目，没看出什么东西来。
然后看了看第三题，我估计只会爆搜了，于是发呆5分钟开始重新码T2。
稳妥起见先码了一个离散化，把h搞到1~n（还有一个原因是h=0的话zkw线段树会囧。。。这是我后来才发现的。）
写了俩zkw分别记录当前处理到的这一棵是目标序列中奇数位和偶数位的情况。然后两种情况分别算一次。
然后写树的时候开闭区间没注意。。调了20分钟。。七弄八弄就交卷了囧。D2倒是A了两题……

发自 WordPress for Android

Tag Archives: OI

[Dr.Lib]Note:Algorithm – SSSP

Dijkstra

SPFA

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

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

性质

旋转

保持性质(Maintain)

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

函数式编程

主席树

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

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

临时建立节点的主席树

[Dream YOLO]NOIP2013提高组酱油报告

朋友们

TAG CLOUD