差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:树套树 [2020/07/11 21:20]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:树套树 [2020/07/30 14:23] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 树套树 1 ======
+====== 树套树 ======
 ===== 树状数组套树状数组 =====
@@ 行 35: / 行 35: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 #define lowbit(x) (x)&(-x)
 const int MAXN=2050;
@@ 行 156: / 行 109: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=(5e4+5)*4,MAXM=40;
 struct Node{
@@ 行 307: / 行 213: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=(5e4+5)*4,MAXS=MAXN*20,Inf=0x7fffffff;
 template <typename T>
@@ 行 566: / 行 425: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=5e4+5,MAXS=MAXN*20,Inf=0x7fffffff;
 template <typename T>
@@ 行 829: / 行 641: @@
 </hidden>
-=== 动态开点权值线段树套名次树版本 ===
+=== 权值线段树套名次树版本 ===
 转换一下思路，考虑外层维护权值，内层维护位置。那么 $\text{rank}$ 操作查询 $0\sim v-1$ 区间的满足条件的点的个数。
@@ 行 839: / 行 651: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=5e4+5,MAXS=MAXN*40,Inf=0x7fffffff;
 template <typename T>
@@ 行 1126: / 行 891: @@
 </hidden>
-=== 树状数组套权值线段树版本 ===
+===== 树状数组套权值线段树 =====
-树状数组的每个节点的权值线段树维护区间 $[x-\text{lowbit}(x)+1,x]$ 的权值分布，需要动态开点。
+==== 简介 ====
-求 $\text{rank}$ 类似主席树求法。
+功能类似线段树/树状数组套名次树。
+其实权值线段树和名次树在功能上有许多相同点，权值线段树码量相对较少，但空间复杂度多一个 $O(\log v)$。
+==== 模板题 ====
+[[https://www.luogu.com.cn/problem/P3759|洛谷p3759]]
+该题等价于维护一个数组，支持一下操作：
+  - 修改某个点的点权
+  - 询问满足位置在 $[l_1,r_1]$ 且权值在 $[l_2,r_2]$ 范围内的点个数和点权和。
+树状数组的每个节点的权值线段树维护区间 $[x-\text{lowbit}(x)+1,x]$ 的权值分布，每个权值记录点个数和点权和。
 空间复杂度 $O(n\log n\log v)$，单次操作时间复杂度 $O(\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5,MAXM=400,mod=1e9+7;
+struct Node{
+	int ch[2],sz,sum;
+}node[MAXN*MAXM];
+struct Ans{
+	int sz,sum;
+	Ans operator + (const Ans &b){
+		Ans c;
+		c.sz=sz+b.sz;
+		c.sum=sum+b.sum;
+		if(c.sum>=mod)c.sum-=mod;
+		return c;
+	}
+	Ans operator - (const Ans &b){
+		Ans c;
+		c.sz=sz-b.sz;
+		c.sum=sum-b.sum;
+		if(c.sum<0)c.sum+=mod;
+		return c;
+	}
+	void operator += (const Ans &b){
+		sz+=b.sz;
+		sum+=b.sum;
+		if(sum>=mod)sum-=mod;
+	}
+	void operator -= (const Ans &b){
+		sz-=b.sz;
+		sum-=b.sum;
+		if(sum<0)sum+=mod;
+	}
+	Ans(int sz=0,int sum=0):sz(sz),sum(sum){}
+};
+#define lowbit(x) (x)&(-x)
+int n,root[MAXN],tot;
+int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
+void add(int pos,int v){
+	while(pos<=n){
+		c[pos]+=v;
+		if(c[pos]>=mod)
+		c[pos]-=mod;
+		d[pos]++;
+		pos+=lowbit(pos);
+	}
+}
+Ans sum(int pos){
+	int s1=0,s2=0;
+	while(pos){
+		s2+=c[pos];
+		if(s2>=mod)
+		s2-=mod;
+		s1+=d[pos];
+		pos-=lowbit(pos);
+	}
+	return Ans(s1,s2);
+}
+void update_1D(int &k,int lef,int rig,int pos,int v1,int v2){
+	if(!k)k=++tot;
+	node[k].sz+=v2,node[k].sum=(node[k].sum+v1)%mod;
+	if(lef==rig)
+	return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update_1D(node[k].ch[0],lef,mid,pos,v1,v2);
+	else
+	update_1D(node[k].ch[1],mid+1,rig,pos,v1,v2);
+}
+void update_2D(int k,int pos,int v1,int v2){
+	while(k<=n){
+		update_1D(root[k],1,n,pos,v1,v2);
+		k+=lowbit(k);
+	}
+}
+Ans query_1D(int k,int lef,int rig,int L,int R){
+	if(!k)
+	return Ans(0,0);
+	if(L<=lef&&rig<=R)
+	return Ans(node[k].sz,node[k].sum);
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return query_1D(node[k].ch[0],lef,mid,L,R);
+	else if(mid<L)
+	return query_1D(node[k].ch[1],mid+1,rig,L,R);
+	return query_1D(node[k].ch[0],lef,mid,L,R)+query_1D(node[k].ch[1],mid+1,rig,L,R);
+}
+Ans query_2D(int L,int R,int ql,int qr){
+	if(ql>qr)
+	return Ans(0,0);
+	int pos1=L-1,pos2=R;
+	Ans re=Ans(0,0);
+	while(pos1){
+		re-=query_1D(root[pos1],1,n,ql,qr);
+		pos1-=lowbit(pos1);
+	}
+	while(pos2){
+		re+=query_1D(root[pos2],1,n,ql,qr);
+		pos2-=lowbit(pos2);
+	}
+	return re;
+}
+int main()
+{
+	n=read_int();
+	int q=read_int(),lef,rig;
+	LL ans=0;Ans temp;
+	_rep(i,1,n)
+	a[i]=read_int(),b[i]=read_int();
+	for(int i=n;i;i--){
+		add(a[i],b[i]);
+		temp=sum(a[i]-1);
+		ans=(ans+temp.sum+1LL*b[i]*temp.sz)%mod;
+		update_2D(i,a[i],b[i],1);
+	}
+	while(q--){
+		lef=read_int();
+		rig=read_int();
+		if(lef==rig){
+			enter(ans);
+			continue;
+		}
+		if(lef>rig)
+		swap(lef,rig);
+		temp=query_2D(lef+1,rig-1,a[lef]+1,n)-query_2D(lef+1,rig-1,1,a[lef]-1);
+		ans=(ans+temp.sum+1LL*b[lef]*temp.sz)%mod;
+		temp=query_2D(lef+1,rig-1,1,a[rig]-1)-query_2D(lef+1,rig-1,a[rig]+1,n);
+		ans=(ans+temp.sum+1LL*b[rig]*temp.sz)%mod;
+		if(a[lef]<a[rig])
+		ans=(ans+b[lef]+b[rig])%mod;
+		else
+		ans=(ans-b[lef]-b[rig])%mod;
+		enter((ans+mod)%mod);
+		update_2D(lef,a[lef],-b[lef],-1);update_2D(rig,a[rig],-b[rig],-1);
+		swap(a[lef],a[rig]);swap(b[lef],b[rig]);
+		update_2D(lef,a[lef],b[lef],1);update_2D(rig,a[rig],b[rig],1);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具