数据结构

树状数组

普通树状数组

单点加操作

cpp
1
2
3
4
5
6
7
8
int n,arr[500005];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int d){
	while(x<=n){
		arr[x]+=d;
		x+=lowbit(x);
	}
}

前缀和操作

cpp
1
2
3
4
5
6
7
8
inline int sum(int x){
	int res=0;
	while(x){
		res+=arr[x];
		x-=lowbit(x);
	}
	return res;
}

差分树状数组

将树状数组维护差分数组，就可以达到区间加和单点查询操作

多维树状数组

使用for来循环，其他的和普通树状数组类似

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n,m,arr[102][102];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y,int d){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=m;j+=lowbit(j)) arr[i][j]+=d;
	}
}
inline int sum(int x,int y){
	int res=0;
	for(int i=x;i;i-=lowbit(i)){
		for(int j=y;j;j-=lowbit(j)) res+=arr[i][j];
	}
	return res;
}

区间查询/修改树状数组

需要维护两个数组：$d$ 和 $di$
为了简便，add和sum操作都需要第一个参数传递要操作的数组

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[100005],d[100005],di[100005];
int n;
inline int lowbit(int x){return -x&x;}
inline void add(int *arr,int x,int d){
	 while(x<=n){
	 	arr[x]+=d;
	 	x+=lowbit(x);
	 }
}
inline int sum(int *arr,int x){
	int res=0;
	while(x){
		res+=arr[x];
		x-=lowbit(x);
	}
	return res;
}

$a[]$ 为初始数据
$d[]$ 为差分数组，即$d[i]=a[i]-a[i-1]$
$di[i]=i*d[i]$ 我们有公式

$$\sum_{i=1}^{n} a_i =(n+1)\times \sum_{i=1}^{n} d[i]-\sum_{i=1}^{n} di[i]$$

初始化

cpp
1
2
3
4
5
6
for(int i=1;i<=n;i++){
	a[i]=read();
	int tmp=a[i]-a[i-1];
	add(d,i,tmp);
	add(di,i,tmp*i);
}

add操作

cpp
1
2
3
//在区间[l,r]中都加上v
add(d,l,v);add(d,r+1,-v);
add(di,l,l*v);add(di,r+1,-(r+1)*v);

区间查询直接套上面的公式即可

并查集

普通并查集

cpp
1
2
3
4
5
6
7
8
int fa[10004];
inline int find(int x){
	while(x!=fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}

//初始化
for(int i=1;i<=n;i++) fa[i]=i;

带权并查集

[NOI2002] 银河英雄传说

题目描述

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 $30000$ 列，每列依次编号为 $1, 2,\ldots ,30000$。之后，他把自己的战舰也依次编号为 $1, 2, \ldots , 30000$，让第 $i$ 号战舰处于第 $i$ 列。

合并指令为 M i j，含义为第 $i$ 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 $j$ 号战舰所在的战舰队列的尾部。

询问指令：C i j。该指令意思是，询问第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

带权并查集需要在并查集合并和路径压缩时维护权值信息。下面是维护元素到根节点距离的实例（实际上还要顺便维护并查集连通块大小）

带权并查集就需要使用递归式了

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int fa[30001];
int w[30001];
int size[30001];
int find(int x){
	if(fa[x]==x) return x;
	int k=fa[x];//备份 
	fa[x]=find(fa[x]);//路径压缩 
	w[x]+=w[k];//更新，自己原来的父节点不一定是根节点，原来的值可能是假的，需要更新 
	size[x]=size[fa[x]];//更新 
	return fa[x];
}

//将a合并到b 
inline void unionn(int a,int b){
	a=find(a);
	b=find(b);
	fa[a]=b;
	w[a]+=size[b];//这里揭示了为什么还要维护并查集连通块大小 
	size[a]+=size[b];
	size[b]=size[a];
}

种类并查集

种类并查集可以非常好地处理元素之间的关系。

使用种类并查集的前提是，关系中的不等号具有传递性，比如满足类似"a!=b,b!=c则必有a!=c"的关系。更形象的话就是“非黑即白”

如果不具有传递性，可以考虑将并查集的处理离线下来操作，详见P1955

并查集快速跳过

在一个数列上，让每个点都指向另一个点（可以是自身也可以是后面的点），遍历到这个点之后就直接跳到指向的点，就可以达到快速跳过的目的。使用路径压缩会提高效率。其中的实现就是使用并查集

单调队列

这里以单调递增队列为例

push操作

cpp
1
2
3
4
5
6
7
8
struct Entry{
	int val,pos;
};
deque<Entry> q;
void push(Entry x){
	while(!q.empty()&&q.back().val>x.val) q.pop_back();
	q.push_back(x);
}

将元素放入双端队列前要维持单调队列的单调性 i为当前遍历到的位置，k为队列长度

cpp
1
while(!q.empty()&&q.front().pos<=i-k) q.pop_front();

取队头元素时要判断是否过期

st表

取log

cpp
1
2
int a[maxn],lg[maxn],st[maxn][20]; 
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;

预处理

cpp
1
2
3
4
5
6
for(int i=1;i<=n;i++) st[i][0]=a[i];
for(int i=1;i<=lg[n];i++){//枚举长度 
	for(int j=1;j<=n-(1<<i)+1;j++){//枚举起点
		st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	}
}

查询

cpp
1
2
3
//求[l,r]之间的最大值
int k=lg[r-l+1];
int ans=max(st[l][k],st[r-(1<<k)+1][k]); 

FHQ Treap

维护值域

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ch[_][2],val[_],dat[_],size[_],tot;
inline void update(int x){size[x]=1+size[ch[x][0]]+size[ch[x][1]];} 
inline int create(int v){return size[++tot]=1,val[tot]=v,dat[tot]=rand(),tot;}
//fhq treap满足小根堆 
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(dat[x]<dat[y]) return ch[x][1]=merge(ch[x][1],y),update(x),x;
	else return ch[y][0]=merge(x,ch[y][0]),update(y),y;
}
void split(int now,int k,int &x,int &y){
	if(!now) return x=y=0,void();
	if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
	else y=now,split(ch[now][0],k,x,ch[now][0]);
	update(now);
}
int query(int now,int k){
	while(true){
		if(k<=size[ch[now][0]]) now=ch[now][0];
		else if(k==size[ch[now][0]]+1) return now;
		else k-=size[ch[now][0]]+1,now=ch[now][1];
	}
}

插入
split(root,x,l,r),root=merge(merge(l,create(x)),r);

删除
split(root,x,l,tmp),split(l,x-1,l,r),r=merge(ch[r][0],ch[r][1]),root=merge(merge(l,r),tmp);

rank
split(root,x-1,l,r),cout<<size[l]+1<<endl,root=merge(l,r);

kth
cout<<val[query(root,x)]<<endl;

前驱
split(root,x-1,l,r),cout<<val[query(l,size[l])]<<endl,root=merge(l,r);

后继
split(root,x,l,r),cout<<val[query(r,1)]<<endl,root=merge(l,r);

维护序列

事实上，在维护值域的时候，实际上就是在维护一个排好序的序列

在维护序列时，只需要改动一下split操作即可

[CZOI Online #2] 滚动

我们规定将序列向左滚动表示：第二个数变为第一个数，第三个数变为第二个数...第一个数变为最后一个数。

现给定一个长度为 $n$ 的序列。我们有 $m$ 个操作，每次操作给定一个数 $x$，表示查询序列中位置 $x$ 上的数，然后再将区间 $[x,n]$ 向左滚动。

你需要回答每次的查询。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define int long long
#define _ 2000006
using namespace std;

int n,m;
int ch[_][2],dat[_],size[_],tot;
long long val[_];
inline void update(int x){size[x]=1+size[ch[x][0]]+size[ch[x][1]];}
inline int create(long long v){return size[++tot]=1,val[tot]=v,dat[tot]=rand(),tot;}
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(dat[x]<dat[y]) return ch[x][1]=merge(ch[x][1],y),update(x),x;
	else return ch[y][0]=merge(x,ch[y][0]),update(y),y; 
}
void split(int now,int k,int &x,int &y){
	if(!now) return x=y=0,void();
	int u=size[ch[now][0]]+1;//注意这里！！！！！！！！！！！！！！
	if(u<=k) x=now,split(ch[now][1],k-u,ch[now][1],y);
	else y=now,split(ch[now][0],k,x,ch[now][0]);
	update(now);
}
int query(int now,int k){
	while(true){
		if(k<=size[ch[now][0]]) now=ch[now][0];
		else if(k==size[ch[now][0]]+1) return now;
		else k-=size[ch[now][0]]+1,now=ch[now][1];
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	int root=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		root=merge(root,create(x));
	}
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		long long ans=val[query(root,x)];
		cout<<ans<<'\n';
		int p1=0,p2=0,p3=0,p4=0;
		split(root,x-1,p1,p2);
		split(p2,1,p3,p4);
		root=merge(merge(p1,p4),create(ans));
	}
	return 0;
}

（原题数据比较毒瘤（虽然是自己出的），必须要开long long才能过）

P3391 【模板】文艺平衡树

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#define maxn 100005
using namespace std;

int id,val[maxn],dat[maxn],size[maxn],ch[maxn][2],root,tag[maxn];
inline int create(int x){
	id++;
	val[id]=x;
	dat[id]=rand();
	size[id]=1;
	return id;
}
inline void pushup(int k){
	size[k]=size[ch[k][0]]+1+size[ch[k][1]];
}
inline void pushdown(int k){
	if(tag[k]){
		tag[ch[k][0]]^=1;
		tag[ch[k][1]]^=1;
		swap(ch[k][0],ch[k][1]);
		tag[k]=0;
	}
}
void split(int now,int k,int &x,int &y){
	if(!now) x=y=0;
	else{
		pushdown(now);
		int u=size[ch[now][0]]+1;
		if(u<=k){
			x=now;
			split(ch[now][1],k-u,ch[now][1],y);
			pushup(x);
		}else{
			y=now;
			split(ch[now][0],k,x,ch[now][0]);
			pushup(y);
		}
	}
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	pushdown(x);
	pushdown(y);
	if(dat[x]<=dat[y]){
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void reverse(int l,int r){
	int p1=0,p2=0,p3=0,p4=0;
	split(root,l-1,p1,p2);
	split(p2,(r-l+1),p3,p4);
	tag[p3]^=1;
	p2=merge(p3,p4);
	root=merge(p1,p2);
}
void print(int k){
	pushdown(k);
	if(ch[k][0]) print(ch[k][0]);
	cout<<val[k]<<" ";
	if(ch[k][1]) print(ch[k][1]);
}

int main(){
	int n,m;
	cin>>n>>m;
	int l,r;
	for(int i=1;i<=n;i++){
		//int k;
		//cin>>k;
		split(root,i-1,l,r);
		root=merge(merge(l,create(i)),r);
	}
	while(m--){
		cin>>l>>r;
		reverse(l,r);
	}
	print(root);
	return 0;
}

可以直接把要翻转的区间分割出来打上懒标记 值得注意的是，merge和split操作时都需要把懒标记pushdown

主席树

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int in[_],din[_];
int root[_],size;
struct Node{int l,r,val;}tree[_<<5];//开32倍大小
inline int clone(int node){return tree[++size]=tree[node],size;}
int build(int l,int r){
	int node=++size;
	if(l==r) return node;
	int mid=(l+r)>>1;
	tree[node].l=build(l,mid);
	tree[node].r=build(mid+1,r);
	return node;
} 

int update(int pre,int l,int r,int x){
	int node=clone(pre);
	tree[node].val++;
	if(l==r) return node;
	int mid=(l+r)>>1;
	if(x<=mid) tree[node].l=update(tree[node].l,l,mid,x);
	else tree[node].r=update(tree[node].r,mid+1,r,x);
	return node;
}

int query(int u,int v,int l,int r,int k){
	if(l==r) return din[l];
	int mid=(l+r)>>1;
	int num=tree[tree[v].l].val-tree[tree[u].l].val;
	if(num>=k) return query(tree[u].l,tree[v].l,l,mid,k);
	else return query(tree[u].r,tree[v].r,mid+1,r,k-num);
}

int main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++) in[i]=din[i]=read();
	root[0]=build(1,n);
	
	sort(din+1,din+1+n);
	int len=unique(din+1,din+n+1)-din-1;
	for(int i=1;i<=n;i++){
		int x=lower_bound(din+1,din+len+1,in[i])-din;
		root[i]=update(root[i-1],1,n,x);
	}
	while(m--){
		int l=read(),r=read(),k=read();
		cout<<query(root[l-1],root[r],1,n,k)<<endl;
	}
	return 0;
}

莫队

普通莫队

以询问区间内有多少个不同的数为例

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n,in[1000010],bl[1000010],blo,ans[1000010];
struct Query{int l,r,id;} q[1000010];

//按左端点所在的块的位置排序。相同再按照右端点的位置排序 
inline bool cmp1(Query a,Query b){return bl[a.l]==bl[b.l]? a.r<b.r:bl[a.l]<bl[b.l];}
inline bool cmp2(Query a,Query b){return a.id<b.id;}

int l=1,r,now,cnt[1000010];
//加入 
inline void add(int x){
	if(cnt[in[x]]==0) ++now;
	++cnt[in[x]];
}
//删除 
inline void del(int x){
	--cnt[in[x]];
	if(cnt[in[x]]==0) --now;
}

int main(){
	cin>>n;
	blo=sqrt(n);
	for(int i=1;i<=n;i++) cin>>in[i];
	for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;
	
	int m;cin>>m;
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	
	sort(q+1,q+m+1,cmp1);
	for(int i=1;i<=m;i++){
		//注意删除操作是先删除，再移动指针
		//添加操作是先移动指针再添加 
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) add(r--);
		ans[q[i].id]=now;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}

带修莫队

• 可修改莫队只用于单点修改，区间修改的题目就算了吧...

• 时间上的优化：将块的大小从sqrt(n)改为n的二分之三次方，即 blo=pow(n,0.666);
  复杂度大约为O(n的五分之三次方)

修改和询问单独分开

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int numq,numc;
struct Query{int l,r,pre,id,ans;} q[maxn];
struct Change{int pos,val;} c[maxn];

//排序部分，右端点比较对象改变，新增了一个比较的关键字
inline bool cmp1(Query a,Query b){
	if(bl[a.l]!=bl[b.l]) return bl[a.l]<bl[b.l];
	if(bl[a.r]!=bl[b.r]) return bl[a.r]<bl[b.r];
	return a.pre<b.pre;
}

//读入部分
for(int i=1;i<=m;i++){
	char opt;
	cin>>opt;
	if(opt=='Q'){
		numq++;
		q[numq].l=read();q[numq].r=read();
		q[numq].pre=numc;
		q[numq].id=numq;
	}
	if(opt=='R'){
		numc++;
		c[numc].pos=read();c[numc].val=read();
	}
}

新增 now 变量，表示当前处理了几个修改操作
移动指针后需要顺手处理一下操作

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int i=1;i<=numq;i++){
	while(l<q[i].l) del(l++);
	while(l>q[i].l) add(--l);
	while(r<q[i].r) add(++r);
	while(r>q[i].r) del(r--);
	//带修莫队 
	while(now<q[i].pre) work(++now,i);
	while(now>q[i].pre) work(now--,i);
	q[i].ans=ans;
}

//不去真正执行这个操作，把数据修改。而是考虑操作对答案的贡献
inline void work(int x,int i){
	if(c[x].pos>=q[i].l&&c[x].pos<=q[i].r){//只有修改在查询区间内才会对ans产生影响 
		cnt[in[c[x].pos]]--;
		if(cnt[in[c[x].pos]]==0) ans--;
		cnt[c[x].val]++;
		if(cnt[c[x].val]==1) ans++;
	}
	//下次再修改就相当于撤销了本次修改 
	swap(c[x].val,in[c[x].pos]);
}

分块

块长度 blo=sqrt(n)

每个元素属于第几个块 bl=(i-1)/blo+1

并且有一个性质，第 $i$ 个块的右边界为 $i*blo$

一般分块的做法为

cpp
1
2
3
4
for(int i=l;i<=min(bl[l]*blo,r);i++) ...//对左侧的非整块进行暴力操作
if(bl[l]!=bl[r])
	for(int i=(bl[r]-1)*blo+1;i<=r;i++) ...//对右侧的非整块进行暴力操作
for(int i=bl[l]+1;i<=bl[r]-1;i++) ...//对中间的整块进行操作

区间小于某个值

区间加，然后查找区间第k小

在块内进行二分查找，多加一个log的复杂度。对于非整块的数据，可以进行一个reset操作，即暴力对非整块进行加法操作，然后再重新对这个块的元素排序

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline void reset(int x){
	v[x].clear();
	for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++) v[x].push_back(in[i]);
	sort(v[x].begin(),v[x].end());
}

inline void add(int l,int r,int c){
	for(int i=l;i<=min(bl[l]*blo,r);i++) in[i]+=c;
	reset(bl[l]);
	if(bl[l]!=bl[r]){
		for(int i=(bl[r]-1)*blo+1;i<=r;i++) in[i]+=c;
		reset(bl[r]);
	}	
	for(int i=bl[l]+1;i<=bl[r]-1;i++) tag[i]+=c;
}

inline int query(int l,int r,int c){
	int ans=0;
	for(int i=l;i<=min(bl[l]*blo,r);i++) if(in[i]+tag[bl[i]]<c) ans++;
	if(bl[l]!=bl[r]){
		for(int i=(bl[r]-1)*blo+1;i<=r;i++) if(in[i]+tag[bl[i]]<c) ans++;
	}
	for(int i=bl[l]+1;i<=bl[r]-1;i++){
		int x=c-tag[i];
		ans+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
	}
	return ans;
}

插入

分块支持插入，使用vector维护。但会破坏块的大小，需要在若干次操作后对块进行重构。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
pair<int,int> query(int a){
	int x=1;
	while(a>v[x].size()) a-=v[x].size(),x++;
	return make_pair(x,a-1);
}
void rebuild(){
	int top=0;
	for(int i=1;i<=m;i++){
		for(auto j:v[i]){
			tmp[++top]=j;//创建临时数组，把所有的数据都复制下来 
		}
		v[i].clear();
	}
	blo=sqrt(top);
	for(int i=1;i<=top;i++){
		bl[i]=(i-1)/blo+1;
		v[bl[i]].push_back(tmp[i]);
	}
	m=bl[n];
}
void insert(int l,int r){
	pair<int,int> t=query(l); 
	v[t.first].insert(v[t.first].begin()+t.second,r);
	if(v[t.first].size()>20*blo) rebuild();
}

线段树优化建图

若干变量

cpp
1
2
3
4
5
6
7
8
9
10
11
12
//线段树
//tree out/in存放线段树节点编号所代表图中的点 
//线段树节点和图上的点一一对应
int treeOut[maxn<<2];//out是子节点向父节点连边
int treeIn[maxn<<2];//in是父节点向子树连边
int cnt;//用cnt分发图中的点的编号 
//如果图中有n个节点，则cnt从n+1开始分发编号
//前n个编号是给原图上的点保留的 

//线段树对图优化之后，图上最多有几个边不好计算所以直接采用邻接矩阵式 
typedef pair<int,int> pii; //第一个int是to，第二个int是w 
vector<pii> g[maxn*10];

建树

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void build(int k,int l,int r){
	if(l==r){
		treeOut[k]=l;
		treeIn[k]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(k),l,mid);
	build(rs(k),mid+1,r); 
	//构建图基本框架
	treeOut[k]=++cnt;
	treeIn[k]=++cnt; 
	g[treeOut[ls(k)]].push_back(pii(treeOut[k],0));
	g[treeOut[rs(k)]].push_back(pii(treeOut[k],0));
	g[treeIn[k]].push_back(pii(treeIn[ls(k)],0));
	g[treeIn[k]].push_back(pii(treeIn[rs(k)],0));	
}

建边

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//区间与点之间建边
//tp=true，区间向点建边
//tp=false，点向区间建边 
inline void connect(int k,int l,int r,int x,int y,int p,int w,bool type){
	if(l>=x&&r<=y){
		if(type) g[treeOut[k]].push_back(pii(p,w));
		else g[p].push_back(pii(treeIn[k],w));
		return; 
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		connect(ls(k),l,mid,x,y,p,w,type); 
	}
	if(y>mid){
		connect(rs(k),mid+1,r,x,y,p,w,type);
	}
}