[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 – 关于存图

想当年，我只会用邻接矩阵，MLE的感人肺腑啊！

看最短路算法时，很多遍历边的方法我都看不懂。于是专门刷了一下存图……在此做个回顾总结。

部分来源于NOCOW。在此感谢。

邻接矩阵

作为图的一种储存方式，实际上就是一个二维数组。即为记为map[i][j]，map[i][j]为节点i到节点j之间的边的权值，若不存在边，则为-1或其他。

这种储存方式的优势是书写方便，但缺点是非稠密图空间效率不高。相比之下，稍微麻烦点的前向星,邻接表等结构更加快速。

邻接表

邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。

第i个单链表中的结点表示依赖于顶点vi的边。单链表中每一个结点称为表结点，应包括三个域邻接点域、链域和数据域。邻接点域，用以存放与vi相邻接的顶点序号；链域用以指向与vi邻接的下一个结点,数据域存储和边或弧有关的的信息。

但是，为什么一定要链表呢？

有vector为什么不用呢？

vector<pair<int, int> > MAP[MAX];
//存边
cin >> M;
for(int i = 1; i <= M; i++)
{
    int s, e, v;
    cin >> s >> e >> v;
    MAP[s].push_back(make_pair(e, v));
}

//遍历x的边集,MAP[x][i].first为终点，MAP[x][i].second为边权
for(int i = 0; i < MAP[x].size(); i++){
    //do YOLO
}

vector<pair<int, int> > MAP[MAX];

//存边

cin >> M;

for(int i = 1; i <= M; i++)

{

int s, e, v;

cin >> s >> e >> v;

MAP[s].push_back(make_pair(e, v));

}

//遍历x的边集,MAP[x][i].first为终点，MAP[x][i].second为边权

for(int i = 0; i < MAP[x].size(); i++){

//do YOLO

}

前向星

前向星构造方法如下：

读入每条边的信息

将边存放在数组中

把数组中的边按照起点顺序排序

struct R{
  int first,last;
}record[MAXN];
struct Edge{
  int s,t,w;
  bool operator <(const Edge &b)const
  {
      return this->s<b.s;
  }
}edge[MAXE];

for(i=1;i<=n;++i){
    record[i].last=0;
    //  每个顶点在数组中的起始位置初始化为-1，表示出度为0
    record[i].first=-1;
}
for(i=1;i<=m;++i){
    scanf("%d%d%d",&a,&b,&c);
    edge[i].s=a;
    edge[i].t=b;
    edge[i].w=c;
    record[a].last++;//记录某个节点出发的边有多少条
}
sort(edge+1,edge+m+1);//m条边排序
//下面求每个顶点在数组中的起始位置和终止位置
int index=1;
while(index<=m){
    record[edge[index].s].first=index;//以一个点为出发点的第一条边
    record[edge[index].s].last+=record[edge[index].s].first-1;
    //以一个点为出发点的最后一条边
    index=record[ edge[index].s].last+1;
}

struct R{

int first,last;

}record[MAXN];

struct Edge{

int s,t,w;

bool operator <(const Edge &b)const

{

return this->s<b.s;

}

}edge[MAXE];

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

record[i].last=0;

// 每个顶点在数组中的起始位置初始化为-1，表示出度为0

record[i].first=-1;

}

for(i=1;i<=m;++i){

scanf("%d%d%d",&a,&b,&c);

edge[i].s=a;

edge[i].t=b;

edge[i].w=c;

record[a].last++;//记录某个节点出发的边有多少条

}

sort(edge+1,edge+m+1);//m条边排序

//下面求每个顶点在数组中的起始位置和终止位置

int index=1;

while(index<=m){

record[edge[index].s].first=index;//以一个点为出发点的第一条边

record[edge[index].s].last+=record[edge[index].s].first-1;

//以一个点为出发点的最后一条边

index=record[ edge[index].s].last+1;

}

链式前向星

嗯，排序，快排，nlogn。

你看看人家存边只要O(n)……（如果你会计数排序的话……也行

那么……链式前向星。

struct edge{
	int e;int v;int next;
};
int first[MAXN],head;
edge V[MAXN];

cin>>m;
while(head++<m){
	cin>>b>>e>>l;
	V[head].e=e;V[head].v=l;
	if(first[b]!=-1){
		V[head].next=first[b];
	}else{
		V[head].next=head;
	}
	first[b]=head;
}

for(int ed=first[ps];;ed=V[ed].next){
	//do YOLO
	if(ed==V[ed].next)break;
}

struct edge{

int e;int v;int next;

};

int first[MAXN],head;

edge V[MAXN];

cin>>m;

while(head++<m){

cin>>b>>e>>l;

V[head].e=e;V[head].v=l;

if(first[b]!=-1){

V[head].next=first[b];

}else{

V[head].next=head;

}

first[b]=head;

}

for(int ed=first[ps];;ed=V[ed].next){

//do YOLO

if(ed==V[ed].next)break;

}

还有吗……

十字链表和邻接多重表……在OI中还真没怎么见过

[Dr.Lib]Note:Data Structures – C++ STL

本着不重新发明轮子的原则，我很少手码快排和其他数据结构……基本都是拖STL出来用……

STL中还是有不少实用的数据结构的……set,bitset,priority_queue,queue,vector,map……

bitset

Via http://www.cplusplus.com/reference/bitset/bitset/

Member functions

(constructor)

Construct bitset (public member function )

applicable operators

Bitset operators (function )

Bit access

operator[]

Access bit (public member function )

count

Count bits set (public member function )

size

Return size (public member function )

test

Return bit value (public member function )

any

Test if any bit is set (public member function )

none

Test if no bit is set (public member function )

all

Test if all bits are set (public member function )

Bit operations

set

Set bits (public member function )

reset

Reset bits (public member function )

flip

Flip bits (public member function )

Bitset operations

to_string

Convert to string (public member function )

to_ulong

Convert to unsigned long integer (public member function )

to_ullong

Convert to unsigned long long (public member function )

在一些模拟中……bitset还是不错的……不过用处也不是很大……

priority_queue

Member functions

(constructor)

Construct priority queue (public member function )

empty

Test whether container is empty (public member function )

size

Return size (public member function )

top

Access top element (public member function )

push

Insert element (public member function )

emplace

Construct and insert element (public member function )

pop

Remove top element (public member function )

swap

Swap contents (public member function )

优先队列的用处就比较多了，据说优先队列优化dij秒爆SPFA[来源请求]……

只要定义了 operator< ，就可以用优先队列来做成大顶堆。小顶堆……要么改operator<，要么

priority_queue<T, vector<T>, greater<T> >

queue

Member functions

(constructor)

Construct queue (public member function )

empty

Test whether container is empty (public member function )

size

Return size (public member function )

front

Access next element (public member function )

back

Access last element (public member function )

push

Insert element (public member function )

emplace

Construct and insert element (public member function )

pop

Remove next element (public member function )

swap

Swap contents (public member function )

有优先队列优化的dij，就有队列优化的Bellman-Ford……

vector

Member functions

(constructor)

Construct vector (public member function )

(destructor)

Vector destructor (public member function )

operator=

Assign content (public member function )

Iterators:

begin

Return iterator to beginning (public member function )

end

Return iterator to end (public member function )

rbegin

Return reverse iterator to reverse beginning (public member function )

rend

Return reverse iterator to reverse end (public member function )

cbegin

Return const_iterator to beginning (public member function )

cend

Return const_iterator to end (public member function )

crbegin

Return const_reverse_iterator to reverse beginning (public member function )

crend

Return const_reverse_iterator to reverse end (public member function )

Capacity:

size

Return size (public member function )

max_size

Return maximum size (public member function )

resize

Change size (public member function )

capacity

Return size of allocated storage capacity (public member function )

empty

Test whether vector is empty (public member function )

reserve

Request a change in capacity (public member function )

shrink_to_fit

Shrink to fit (public member function )

Element access:

operator[]

Access element (public member function )

at

Access element (public member function )

front

Access first element (public member function )

back

Access last element (public member function )

data

Access data (public member function )

Modifiers:

assign

Assign vector content (public member function )

push_back

Add element at the end (public member function )

pop_back

Delete last element (public member function )

insert

Insert elements (public member function )

erase

Erase elements (public member function )

swap

Swap content (public member function )

clear

Clear content (public member function )

emplace

Construct and insert element (public member function )

emplace_back

Construct and insert element at the end (public member function )

Allocator:

get_allocator

Get allocator (public member function )

vector是个好东西，妈妈再也不用担心我的内存！

数组开大了爆内存，开小了爆下标……WTF……

还用的着担心邻接表MLE？vector没有压力。

map

Member functions

(constructor)

Construct multimap (public member function )

(destructor)

Multimap destructor (public member function )

operator=

Copy container content (public member function )

Iterators:

begin

Return iterator to beginning (public member function )

end

Return iterator to end (public member function )

rbegin

Return reverse iterator to reverse beginning (public member function )

rend

Return reverse iterator to reverse end (public member function )

cbegin

Return const_iterator to beginning (public member function )

cend

Return const_iterator to end (public member function )

crbegin

Return const_reverse_iterator to reverse beginning (public member function )

crend

Return const_reverse_iterator to reverse end (public member function )

Capacity:

empty

Test whether container is empty (public member function )

size

Return container size (public member function )

max_size

Return maximum size (public member function )

Modifiers:

insert

Insert element (public member function )

erase

Erase elements (public member function )

swap

Swap content (public member function )

clear

Clear content (public member function )

emplace

Construct and insert element (public member function )

emplace_hint

Construct and insert element with hint (public member function )

Observers:

key_comp

Return key comparison object (public member function )

value_comp

Return value comparison object (public member function )

Operations:

find

Get iterator to element (public member function )

count

Count elements with a specific key (public member function )

lower_bound

Return iterator to lower bound (public member function )

upper_bound

Return iterator to upper bound (public member function )

equal_range

Get range of equal elements (public member function )

Allocator:

get_allocator

Get allocator (public member function )

map用在一些需要存储键值对的地方……在一些需要维护数据的地方用这个偷懒一下也不错……

别忘了multimap。

[Dr.Lib]Note:Data Structures – 数据结构那些事

树状数组

[Dr.Lib]Note:Algorithms – 树状数组
树状数组是个简单高效的数据结构，实质上是省掉一半空间后的线段树加上中序遍历{Via ZKW《统计的力量》}

一般情况下，他可以做到单点更新，区间求和。

http://wikioi.com/problem/1080/

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <cstring>
using namespace std;
int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,m=0;
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void upd(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    cin>>n;
    while(i<=n){cin>>tmp;upd(i,tmp);++i;}
    cin>>m;
    while(m--){
    	cin>>tmp;
		if(tmp==2){cin>>p>>q;cout<<(sum(q)-sum(p-1))<<endl;}
        else{cin>>p>>q;upd(p,q);}
    }
    return 0;
}

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include <cstring>

using namespace std;

int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,m=0;

inline int lowbit(int x){

return x&(-x);

}

int sum(int x){

int sum=0;

while(x>0){

sum+=c[x];

x-=lowbit(x);

}

return sum;

}

void upd(int x,int v){

while(x<=n){

c[x]+=v;

x+=lowbit(x);

}

int main()

{

cin>>n;

while(i<=n){cin>>tmp;upd(i,tmp);++i;}

cin>>m;

while(m--){

cin>>tmp;

if(tmp==2){cin>>p>>q;cout<<(sum(q)-sum(p-1))<<endl;}

else{cin>>p>>q;upd(p,q);}

}

return 0;

}

小小的差分一下，就可以做到区间更新单点值

http://wikioi.com/problem/1081/

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <cstring>
using namespace std;
int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,r=0,m=0;
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void upd(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
	cin>>n;
    int pre=0;
    while(i<=n){cin>>tmp;upd(i,tmp-pre);++i;pre=tmp;}
    cin>>m;
    while(m--){
    	cin>>tmp;
		if(tmp==2){cin>>p;cout<<sum(p)<<endl;}
        else{cin>>p>>q>>r;upd(p,r);upd(q+1,-r);}
    }
    return 0;

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include <cstring>

using namespace std;

int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,r=0,m=0;

inline int lowbit(int x){

return x&(-x);

}

int sum(int x){

int sum=0;

while(x>0){

sum+=c[x];

x-=lowbit(x);

}

return sum;

}

void upd(int x,int v){

while(x<=n){

c[x]+=v;

x+=lowbit(x);

}

int main()

{

cin>>n;

int pre=0;

while(i<=n){cin>>tmp;upd(i,tmp-pre);++i;pre=tmp;}

cin>>m;

while(m--){

cin>>tmp;

if(tmp==2){cin>>p;cout<<sum(p)<<endl;}

else{cin>>p>>q>>r;upd(p,r);upd(q+1,-r);}

}

return 0;

问题是区间更新区间和呢？

只能上线段树了吗？

NO！

http://wikioi.com/problem/1082/

#include<iostream>
#include<algorithm>
#include<cstring>
#include <cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
#define MAXN 200020
int n,q;
int l,r,k,x;
long long c[MAXN],s[MAXN],t[MAXN];
inline int lowbit(int x){return x&(-x);}
long long ssum(int x){
    long long ans=0;
    while(x>0){
        ans+=s[x];
        x-=lowbit(x);
    }
    return ans;
}
long long tsum(int x){
    long long ans=0;
    while(x>0){
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void sadd(int xx,long long val){while(xx<=n)s[xx]+=val,xx+=lowbit(xx);}
void tadd(int xx,long long val){while(xx<=n)t[xx]+=val,xx+=lowbit(xx);}
int main(){
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    scanf("%d",&n);
    for (int i=a;i<=b;i++) scanf("%d",&x),c[i]=c[i-1]+x;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&x,&l,&r);
        if(x==1){
            scanf("%d",&k);
            sadd(l,k);sadd(r+1,-k);
            tadd(l,(l-1)*k);tadd(r+1,-r*k);
        }else{
           printf("%lld\n",((c[r]-c[l-1])+(1-l)*ssum(l)+r*ssum(r)-(tsum(r)-tsum(l))));
        }
    }
    return 0;
}

#include<iostream>

#include<algorithm>

#include<cstring>

#include <cstdio>

#include<cstdlib>

#include<vector>

using namespace std;

#define MAXN 200020

int n,q;

int l,r,k,x;

long long c[MAXN],s[MAXN],t[MAXN];

inline int lowbit(int x){return x&(-x);}

long long ssum(int x){

long long ans=0;

while(x>0){

ans+=s[x];

x-=lowbit(x);

}

return ans;

}

long long tsum(int x){

long long ans=0;

while(x>0){

ans+=t[x];

x-=lowbit(x);

}

return ans;

}

void sadd(int xx,long long val){while(xx<=n)s[xx]+=val,xx+=lowbit(xx);}

void tadd(int xx,long long val){while(xx<=n)t[xx]+=val,xx+=lowbit(xx);}

int main(){

memset(c,0,sizeof(c));

memset(s,0,sizeof(s));

memset(t,0,sizeof(t));

scanf("%d",&n);

for (int i=a;i<=b;i++) scanf("%d",&x),c[i]=c[i-1]+x;

scanf("%d",&q);

while(q--){

scanf("%d%d%d",&x,&l,&r);

if(x==1){

scanf("%d",&k);

sadd(l,k);sadd(r+1,-k);

tadd(l,(l-1)*k);tadd(r+1,-r*k);

}else{

printf("%lld\n",((c[r]-c[l-1])+(1-l)*ssum(l)+r*ssum(r)-(tsum(r)-tsum(l))));

}

return 0;

}

朴素线段树

[Dr.Lib]Note:Algorithms – 线段树

*计算几何在长期的发展中，
诞生了许多实用的数据结构。

*区间查询，穿刺查询都是计算几何解决的问题

*作为特例中的特例，线段树解决的问题是：

*一维空间上的几何统计

Via 《统计的力量》

线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b]，它的左子树表示的区间为[a,(a+b)/2]，右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N，即整个线段区间的长度。

http://wikioi.com/problem/1191

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int ls[800100];
int rs[800100];
int ts[800100];
void build(int l,int r,int p) {
	ls[p]=l;
	rs[p]=r;
	ts[p]=1;
	if(l<r) {
		build(l,((l+r)>>1),(p<<1));
		build(((l+r)>>1)+1,r,(p<<1)+1);
	}
	if(l!=r)
	ts[p]=ts[p<<1]+ts[(p<<1)+1];
}
void inst(int l,int r,int p){if(ts[p]){
	if(l<=ls[p]&&rs[p]<=r){ts[p]=0;return;}
	if(ls[p]==rs[p])return;
	if(!(l>rs[p<<1]||r<ls[p<<1])){inst(l,r,(p<<1));}
	if(!(l>rs[(p<<1)+1]||r<ls[(p<<1)+1])){inst(l,r,(p<<1)+1);}
	ts[p]=ts[p<<1]+ts[(p<<1)+1];
}}

int main() {
    int lp,rp;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&lp,&rp);
        inst(lp,rp,1);
        printf("%d\n",ts[1]);
    }
    return 0;
}

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int n,m;

int ls[800100];

int rs[800100];

int ts[800100];

void build(int l,int r,int p) {

ls[p]=l;

rs[p]=r;

ts[p]=1;

if(l<r) {

build(l,((l+r)>>1),(p<<1));

build(((l+r)>>1)+1,r,(p<<1)+1);

}

if(l!=r)

ts[p]=ts[p<<1]+ts[(p<<1)+1];

}

void inst(int l,int r,int p){if(ts[p]){

if(l<=ls[p]&&rs[p]<=r){ts[p]=0;return;}

if(ls[p]==rs[p])return;

if(!(l>rs[p<<1]||r<ls[p<<1])){inst(l,r,(p<<1));}

if(!(l>rs[(p<<1)+1]||r<ls[(p<<1)+1])){inst(l,r,(p<<1)+1);}

ts[p]=ts[p<<1]+ts[(p<<1)+1];

}}

int main() {

int lp,rp;

scanf("%d%d",&n,&m);

build(1,n,1);

for(int i=1;i<=m;i++)

{

scanf("%d%d",&lp,&rp);

inst(lp,rp,1);

printf("%d\n",ts[1]);

}

return 0;

}

ZKW线段树

参见《统计的力量》

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50005
bool U[4*N];
int T[4*N],M;
void update(int n,int V){
	n+=M;
	T[n]=V;U[n]=1;
	for(n>>=1;n;n>>=1){
	T[n]=T[n<<1]+T[(n<<1)+1];U[n]=1;}
}
int query(int ss,int tt){
	int ans=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;ss>>=1,tt>>=1) {
		if (~ss&1) ans=+T[ss^1];
		if ( tt&1) ans=+T[tt^1];
	}
	return ans;
}
int n,s,t,k;
int main (){
	cin>>n;
	for(M=1;M<=n+1;M*=2);
	while(n--){
		cin>>k>>s>>t;
		if(k)
		update(s,t);
		else
		cout<<query(s,t)<<endl;
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define N 50005

bool U[4*N];

int T[4*N],M;

void update(int n,int V){

n+=M;

T[n]=V;U[n]=1;

for(n>>=1;n;n>>=1){

T[n]=T[n<<1]+T[(n<<1)+1];U[n]=1;}

}

int query(int ss,int tt){

int ans=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;ss>>=1,tt>>=1) {

if (~ss&1) ans=+T[ss^1];

if ( tt&1) ans=+T[tt^1];

}

return ans;

}

int n,s,t,k;

int main (){

cin>>n;

for(M=1;M<=n+1;M*=2);

while(n--){

cin>>k>>s>>t;

if(k)

update(s,t);

else

cout<<query(s,t)<<endl;

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50005
bool U[4*N];
int T[4*N],S[4*N],M;
int count(int n){
	int h=1;
	while((n<<=1)<(M*2))h<<=1;
	return h;
}
int query(int ss,int tt){//查询[ss,tt]
	int ans=0,tlc=0,trc=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {
		if (~ss&1){ans+=T[ss^1];tlc+=count(ss^1);}//左端点是左孩子
		if ( tt&1){ans+=T[tt^1];trc+=count(tt^1);}//右端点是右孩子 
		ss>>=1;tt>>=1;
		ans+=tlc*S[ss]+trc*S[tt];
	}
	for (ss >>= 1;ss > 0; ss >>= 1) {  
        ans += S[ss]*(tlc+trc);  
    }
	return ans;
}
void inc(int ss,int tt,int vv){//[ss,tt]全部加上一个数
	int tlc=0,trc=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {
		if (~ss&1){S[ss^1]+=vv;T[ss^1]+=vv*count(ss^1);tlc+=count(ss^1);}//左端点是左孩子 
		if ( tt&1){S[tt^1]+=vv;T[tt^1]+=vv*count(tt^1);trc+=count(tt^1);}//右端点是右孩子
		ss>>=1;tt>>=1;
		T[ss]+=tlc*vv;T[tt]+=trc*vv;
	}
	for (ss >>= 1;ss > 0; ss >>= 1) {  
		T[ss] += vv*(tlc+trc);  
	}
}
void update(int n,int V){//置[n,n]为V [problem spec
	int per=query(n,n);
	inc(n,n,-per);
	inc(n,n,V);
}
int n,s,t,k;
int main (){
	cin>>n;
    for(M=1;M<=n+1;M*=2);
	while(1){
		cin>>k>>s>>t;
		if(k==2)
		{cin>>k;inc(s,t,k);}
		else if(k==1)
		update(s,t);
		else if(k==0)
		cout<<query(s,t)<<endl;
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define N 50005

bool U[4*N];

int T[4*N],S[4*N],M;

int count(int n){

int h=1;

while((n<<=1)<(M*2))h<<=1;

return h;

}

int query(int ss,int tt){//查询[ss,tt]

int ans=0,tlc=0,trc=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {

if (~ss&1){ans+=T[ss^1];tlc+=count(ss^1);}//左端点是左孩子

if ( tt&1){ans+=T[tt^1];trc+=count(tt^1);}//右端点是右孩子

ss>>=1;tt>>=1;

ans+=tlc*S[ss]+trc*S[tt];

}

for (ss >>= 1;ss > 0; ss >>= 1) {

ans += S[ss]*(tlc+trc);

}

return ans;

}

void inc(int ss,int tt,int vv){//[ss,tt]全部加上一个数

int tlc=0,trc=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {

if (~ss&1){S[ss^1]+=vv;T[ss^1]+=vv*count(ss^1);tlc+=count(ss^1);}//左端点是左孩子

if ( tt&1){S[tt^1]+=vv;T[tt^1]+=vv*count(tt^1);trc+=count(tt^1);}//右端点是右孩子

ss>>=1;tt>>=1;

T[ss]+=tlc*vv;T[tt]+=trc*vv;

}

for (ss >>= 1;ss > 0; ss >>= 1) {

T[ss] += vv*(tlc+trc);

}

void update(int n,int V){//置[n,n]为V [problem spec

int per=query(n,n);

inc(n,n,-per);

inc(n,n,V);

}

int n,s,t,k;

int main (){

cin>>n;

for(M=1;M<=n+1;M*=2);

while(1){

cin>>k>>s>>t;

if(k==2)

{cin>>k;inc(s,t,k);}

else if(k==1)

update(s,t);

else if(k==0)

cout<<query(s,t)<<endl;

}

return 0;

}

[Dr.Lib]Note:Math – 欧拉函数

正在纠结要不要码一篇欧拉函数……IvyEnd神犇的大作就已经出炉了……

Via http://www.ivy-end.com/archives/1021

欧拉函数\(\varphi \left ( N \right )\)表示小于或等于\(N\)的正整数中与\(N\)互质的数的个数。又称\(\varphi\)函数、欧拉商数。

下面介绍欧拉函数的几个性质：

\(\displaystyle\varphi\left ( 1 \right )=1\)。
\(\displaystyle\varphi \left( N\right )=N\cdot\prod_{p\mid N}\left ( \frac{p-1}{p} \right )\)。
\(\displaystyle\varphi \left ( p^{k} \right ) = p^{k}-p^{k-1}=\left(p-1 \right )\cdot p^{k-1}\)，其中\(p\)为质数。
\(\displaystyle\varphi \left(mn \right )=\varphi \left(m \right )\cdot \varphi \left(n \right )\)，其中\(\gcd \left ( m,n \right )=1\)。

我们根据这几个性质就可以求出欧拉函数。

基本思路是首先置\(\varphi \left ( N \right )=N\)，然后再枚举素数\(p\)，将\(p\)的整数倍的欧拉函数\(\varphi \left ( kp \right )\)进行操作\(\varphi \left ( kp \right )=\varphi \left ( kp \right )\cdot \frac{p-1}{p}\)即可。

#include <iostream>
using namespace std;
const int MAX = 1024;
int N;
int p[MAX], phi[MAX];

int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++)    // 初始化
    { p[i] = 1; phi[i] = i; }
    p[1] = 0;    // 1不是素数
    for(int i = 2; i <= N; i++)    // 筛素数
    {
        if(p[i])
        {
            for(int j = i * i; j <= N; j += i)
            { p[j] = 0; }
        }
    }
    for(int i = 2; i <= N; i++)    // 求欧拉函数
    {
        if(p[i])
        {
            for(int j = i; j <= N; j += i)    // 处理素因子p[i]
            {
                phi[j] = phi[j] / i * (i - 1);    // 先除后乘，防止中间过程超出范围
            }
        }
    }
    cout << "Primes: " << endl;
    for(int i = 1; i <= N; i++)
    { if(p[i]) { cout << i << " "; } }
    cout << endl;
    cout << "Euler Phi Function: " << endl;
    for(int i = 1; i <= N; i++)
    { cout << phi[i] << " "; }
    return 0;
}

#include <iostream>

using namespace std;

const int MAX = 1024;

int N;

int p[MAX], phi[MAX];

int main()

{

cin >> N;

for(int i = 1; i <= N; i++) // 初始化

{ p[i] = 1; phi[i] = i; }

p[1] = 0; // 1不是素数

for(int i = 2; i <= N; i++) // 筛素数

{

if(p[i])

{

for(int j = i * i; j <= N; j += i)

{ p[j] = 0; }

}

for(int i = 2; i <= N; i++) // 求欧拉函数

{

if(p[i])

{

for(int j = i; j <= N; j += i) // 处理素因子p[i]

{

phi[j] = phi[j] / i * (i - 1); // 先除后乘，防止中间过程超出范围

}

cout << "Primes: " << endl;

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

{ if(p[i]) { cout << i << " "; } }

cout << endl;

cout << "Euler Phi Function: " << endl;

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

{ cout << phi[i] << " "; }

return 0;

}

以及求单点的函数值

ull phi(ull x)
{
    ull ans = x;
    ull m = (ull)sqrt(x);
    for(ull i = 2; i <= m; i++)
    {
        if(x % i == 0)    // 求素因子
        {
            ans = ans / i * (i - 1);    // 运用通项求解欧拉函数
            while(x % i == 0)    // 每个素因子只计算一次
            { x /= i; }
        }
    }
    if(x > 1)    // 防质数
    { ans = ans / x * (x - 1); }
    return ans;
}

ull phi(ull x)

{

ull ans = x;

ull m = (ull)sqrt(x);

for(ull i = 2; i <= m; i++)

{

if(x % i == 0) // 求素因子

{

ans = ans / i * (i - 1); // 运用通项求解欧拉函数

while(x % i == 0) // 每个素因子只计算一次

{ x /= i; }

}

if(x > 1) // 防质数

{ ans = ans / x * (x - 1); }

return ans;

}

应用：

欧拉定理

\(a^{\varphi(n)}=1 \mod {n}\)

原根个数

\(\varphi \left ( \varphi \left ( N \right ) \right )\)

对于原根的定义，我们可以这样来叙述：

若存在一个实数\(a\)，使得\(a^{i}\mod{N},a\in\left \{ 1,2,3,\cdots ,N \right \}\)的结果各不相同，我们就成实数\(a\)为\(N\)的一个原根。

原根的个数等于\(\varphi \left ( \varphi \left ( N \right ) \right )\)。这样我们就可以很方便的求出原根的个数。（参考题目）

指数循环节

Via http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9

\( A^{x}=A^{x\%\varphi(C) + \varphi(C)} \mod{C} (x \ge \varphi(C))\)

Tag Archives: algorithm

[Dr.Lib]Note:Algorithm – SSSP

Dijkstra

SPFA

[Dr.Lib]Note:Data Structures – 关于存图

邻接矩阵

邻接表

前向星

链式前向星

还有吗……

[Dr.Lib]Note:Data Structures – C++ STL

bitset

Member functions

Bit access

Bit operations

Bitset operations

priority_queue

Member functions

queue

Member functions

vector

Member functions

map

Member functions

[Dr.Lib]Note:Data Structures – 数据结构那些事

树状数组

朴素线段树

ZKW线段树

[Dr.Lib]Note:Math – 欧拉函数

欧拉定理

原根个数

指数循环节

朋友们

TAG CLOUD