[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;

}

Tag Archives: data structures

[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线段树

朋友们

TAG CLOUD