主席树学习笔记 Apare_xzc

主席树学习笔记

xzc 2019/4/11

  上次打武大网络赛，除了一道树上第K大的板子题，没搞出来，于是乎，我这周学了主席树，和gdl一起做了专题里的4道题目。

  今天晚上才AC了E题(终于跟上了gdl的进度)，这道题做了3天了，感觉有点儿收获，所以想记录下来

主席树专题vj链接(5道)

A.K-th Number poj-2104

分析：
求静态区间第K大(从小到大第K个)，主席树板子题

我的代码：

  我把前会长Y_Cl给的板子改成了自己的

  • 去掉了num[],直接用a[]存离散化后的值
  • 把指针的写法用数组模拟了，这样更节省空间 
/* Status：Accepted Time：1672ms Memory：22608kB Length：1541 Lang：G++ Submitted：2019-04-09 20:35:24 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a)) 
using namespace std;
const int maxn = 1e5+10;
int a[maxn],p[maxn],n,cnt;
struct Node{
	int Lchild,Rchild,sum;
}node[maxn*20];
int root[maxn*20];
int update(int left,int right,int v,int p)
{
	if(v<left||v>right) return p;
	int t = cnt++;
	node[t].Lchild = node[p].Lchild;
	node[t].Rchild = node[p].Rchild;
	node[t].sum = node[p].sum + 1;
	int mid = (left+right)>>1;
	if(left==right) return t;
	node[t].Lchild = update(left,mid,v,node[p].Lchild);
	node[t].Rchild = update(mid+1,right,v,node[p].Rchild);
	return t;
}
void build()
{
	cnt = 0;
	root[0] = cnt++;
	node[0].Lchild = node[0].Rchild = node[0].sum = 0;
	For(i,1,n) root[i] = update(1,n,a[i],root[i-1]);
}
int query(int left,int right,int k,int rx,int ry)
{
	if(left==right) return left;
	int tot = node[node[ry].Lchild].sum - node[node[rx].Lchild].sum;
	int mid = (left+right)>>1;
	if(k<=tot) return query(left,mid,k,node[rx].Lchild,node[ry].Lchild);
	else return query(mid+1,right,k-tot,node[rx].Rchild,node[ry].Rchild);
}
int main()
{
	int m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		For(i,1,n) scanf("%d",a+i), p[i] = a[i];
		sort(p+1,p+n+1);
		For(i,1,n) a[i] = lower_bound(p+1,p+n+1,a[i])-p;
		build();
		int l,r,k;
		while(m--)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",p[query(1,n,k,root[l-1],root[r])]);
		}
	}
	
	return 0;
}

指针写法：

/* Accepted 1688ms 22608kB 1399 G++ 2019-04-08 20:19:00 */
Select Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
using namespace std;
const int maxn = 1e5+10;
int a[maxn],p[maxn],n,cnt;
struct Node{
	Node * Lchild, * Rchild;
	int sum;
}node[maxn*20],*root[maxn*20];
Node * update(int left,int right,int v,Node * p)
{
	if(v<left||v>right) return p;
	Node * t = &node[cnt++];
	t->Lchild = p->Lchild;
	t->Rchild = p->Rchild;
	t->sum = p->sum + 1; 
	if(left==right) return t;
	int mid = (left+right)>>1;
	t -> Lchild = update(left,mid,v,p->Lchild);
	t -> Rchild = update(mid+1,right,v,p->Rchild);
	return t;	
}
void build()
{
	cnt = 0;
	root[0] = &node[cnt++];
	root[0]->Lchild = root[0]->Rchild = root[0];
	root[0]->sum = 0;
	For(i,1,n) root[i] = update(1,n,a[i],root[i-1]);
}
int query(int left,int right,int k,Node*x,Node*y)
{
	if(left==right) return left;
	int tot = y->Lchild->sum - x->Lchild->sum;
	int mid = (left+right)>>1;
	if(k<=tot) return query(left,mid,k,x->Lchild,y->Lchild);
	else return query(mid+1,right,k-tot,x->Rchild,y->Rchild);
}

int main()
{
	//freopen("in.txt","r",stdin);
	int m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		For(i,1,n) scanf("%d",a+i), p[i] = a[i];
		sort(p+1,p+1+n);
		For(i,1,n) a[i] = lower_bound(p+1,p+1+n,a[i])-p;
		build();
		int l,r,k;
		while(m--)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",p[query(1,n,k,root[l-1],root[r])]);
		}	
	} 
	
	return 0;	
}

B.Count on a tree spoj-COT

题意：
  询问树上第K小

分析：
  和区间第K大的思想一样，还是要离散化，区间的意义也相同。
  我们知道：一棵树上，两个结点u，v之间的距离可以用这个抽象的公式来求：
dis(u,v) = dis(u)+dis(v)-2*dis(lca(u,v))
  u,v这条路径上面包含的节点的个数可以这样计算：
num(u.v) = num(root_to_u) + num(root_to_v) - num(root_to_lca)-num(root_to_fa(lca))
  我们可以先dfs出一棵生成树，然后记录下来书上每个节点x的父节点fa[x]
  建立主席树的时候，每建一棵线段树，不是从数组a前一个点那棵树的基础上建，而是从fa[x]的基础上建树
  我求LCA的方法是dfs+RMQ

我的代码(指针写的)：

/* Status: Accepted Time: 1480ms Memory: 168960kB Length: 3254 Lang: C++ (gcc 6.3) Submitted: 2019-04-08 21:47:25 */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Mst(a,b) memset(a,(b),sizeof(a))
using namespace std;
const int maxn = 1e5+100;
int a[maxn],p[maxn],n,cnt;
struct Edge{
	int to,Next;
}edge[maxn<<1];
int head[maxn],totEdge;
int disToRoot[maxn];
int First[maxn];
int sequence[maxn<<1];
int deep[maxn<<1];
int father[maxn];
bool vis[maxn];
struct Node{
	Node * Lchild, * Rchild;
	int sum;
}node[maxn*40],*root[maxn*40];
Node * update(int left,int right,int v,Node * p);
void build();
int query(int left,int right,int k,Node*ru,Node*rv,Node*rlca,Node*rfalca);
void initG();
void addedge(int u,int v);
void dfs(int x,int fa);
void dfs(int x,int fa,int dep,int &cntOfSeq)
{
	father[x] = fa;
	vis[x] = true;
	root[x] = update(1,n,a[x],root[fa]);
	sequence[++cntOfSeq] = x;
	deep[cntOfSeq] = dep;
	First[x] = cntOfSeq;
	for(int i=head[x];i!=-1;i=edge[i].Next)
	{
		int to = edge[i].to;
		if(vis[to]) continue;
		vis[to] = true;
		disToRoot[to] = disToRoot[x]+1;
		dfs(to,x,dep+1,cntOfSeq);
		sequence[++cntOfSeq] = x;
		deep[cntOfSeq] = dep;
	}
}
int Min[maxn<<1][20];
int Log2[maxn<<1]={-1};
void getST(int n)
{
	For(i,1,n) Min[i][0] = i;
	for(int j=1;(1<<j)<=n;++j)
	{
		for(int i=1;i+(1<<j)-1<=n;++i)
		{
			int a = Min[i][j-1];
			int b = Min[i+(1<<(j-1))][j-1];
			Min[i][j] = deep[a]>deep[b]?b:a;
		}
	}
} 
int LCA(int x,int y)
{
	x = First[x];
	y = First[y];
	if(x>y) swap(x,y);
	int j = Log2[y-x+1];
	int a = Min[x][j];
	int b = Min[y-(1<<j)+1][j];
	return deep[a]>deep[b]?sequence[b]:sequence[a];
}
int main()
{
	//freopen("in.txt","r",stdin);
	For(i,1,maxn*2-15) Log2[i] = Log2[i>>1]+1;
	int m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		For(i,1,n) scanf("%d",a+i), p[i] = a[i];
		sort(p+1,p+1+n);
		For(i,1,n) a[i] = lower_bound(p+1,p+1+n,a[i])-p;
		int u,v;
		initG();
		For(i,2,n)
		{
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}	
		build(); //先建一棵空树
		Mst(vis,0); 
		int cntOfSequence = 0;
		dfs(1,0,1,cntOfSequence);
		int k,lca;
		getST(2*n-1); 
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&k);
			lca = LCA(u,v);
			printf("%d\n",p[query(1,n,k,root[u],root[v],root[lca],root[father[lca]])]);
		}	
	} 
	
	
	return 0;	
}

void initG()
{
	Mst(head,-1);
	totEdge = 0;
}
void addedge(int u,int v)
{
	edge[totEdge].to = v;
	edge[totEdge].Next = head[u];
	head[u] = totEdge++;
}
Node * update(int left,int right,int v,Node * p)
{
	if(v<left||v>right) return p;
	Node * t = &node[cnt++];
	t->Lchild = p->Lchild;
	t->Rchild = p->Rchild;
	t->sum = p->sum + 1; 
	if(left==right) return t;
	int mid = (left+right)>>1;
	t -> Lchild = update(left,mid,v,p->Lchild);
	t -> Rchild = update(mid+1,right,v,p->Rchild);
	return t;	
}
void build()
{
	cnt = 0;
	root[0] = &node[cnt++];
	root[0]->Lchild = root[0]->Rchild = root[0];
	root[0]->sum = 0;
}
int query(int left,int right,int k,Node*ru,Node*rv,Node *rlca,Node*rfalca)
{
	if(left==right) return left;
	int tot = ru->Lchild->sum + rv->Lchild->sum 
	     - rlca->Lchild->sum - rfalca->Lchild->sum;
	int mid = (left+right)>>1;
	if(k<=tot) 
		return query(left,mid,k,ru->Lchild,rv->Lchild,rlca->Lchild,rfalca->Lchild);
	else 
		return query(mid+1,right,k-tot,ru->Rchild,rv->Rchild,rlca->Rchild,rfalca->Rchild);
}

附：2019武大网络赛那道区间第K大(大！)

  • 区间第K大就是区间第cnt-k+1小
  • cnt = deep[u]+deep[v]-deep[lca(u,v)]-deep[fa[lca(u,v)]
  • (deep[u]为节点u在生成树中的深度)

我的代码：

/* Apr/08/2019 22:10UTC+8 CCNU_你们好强啊我们都是面包手 F - Climb GNU C++17 Accepted 1294 ms 59200 KB */
Apr/09/2019 06:22UTC+8	CCNU_你们好强啊我们都是面包手	F - Climb	GNU C++17	Accepted	1294 ms	59200 KB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Mst(a,b) memset(a,(b),sizeof(a))
using namespace std;
const int maxn = 1e5+20;
int a[maxn],p[maxn],n,cnt;//p离散化 
struct Edge{
	int to,Next;
}edge[maxn<<1];
int head[maxn],totEdge;//邻接表 
int First[maxn],sequence[maxn<<1],deep[maxn<<1];
int father[maxn];
bool vis[maxn]; //dfs 
int Min[maxn<<1][20];
int Log2[maxn<<1]={-1};
struct Node{
	Node * Lchild, * Rchild;
	int sum;
}node[maxn*20],*root[maxn*20];
Node * update(int,int,int,Node*); 
void build(); //建第一课空树(爷爷节点) 
void initG(); //初始化邻接表 
void addedge(int u,int v);
void dfs(int x,int fa,int deep,int&);
void getST(int n); 
int LCA(int x,int y);
int query(int,int,int,Node*,Node*,Node*,Node*);
int main()
{
	//freopen("in.txt","r",stdin);
	For(i,1,maxn*2-15) Log2[i] = Log2[i>>1]+1;
	int T,m;scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		For(i,1,n) scanf("%d",a+i), p[i] = a[i];
		sort(p+1,p+1+n);
		For(i,1,n) a[i] = lower_bound(p+1,p+1+n,a[i])-p;
		int u,v;
		initG();
		For(i,2,n)
		{
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}	
		build(); //先建一棵空树
		Mst(vis,0); 
		int cntOfSequence = 0;
		dfs(1,0,1,cntOfSequence); //dfs生成树的同时，在父节点基础上建立新的线段树 
		int k,lca;
		getST(2*n-1); //线性预处理(nlogn) 
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&k); 
			lca = LCA(u,v);
			int totNum = deep[First[u]]+deep[First[v]]-deep[First[lca]]-deep[First[father[lca]]];
			if(k>totNum) //询问的K大于这条路径上所有顶点的个数 
			{
				printf("-1\n");
				continue;
			}
			k = totNum - k+1;
			printf("%d\n",p[query(1,n,k,root[u],root[v],root[lca],root[father[lca]])]);
		}	
	} 
	
	return 0;	
}

void initG()
{
	Mst(head,-1);
	totEdge = 0;
}
void addedge(int u,int v)
{
	edge[totEdge].to = v;
	edge[totEdge].Next = head[u];
	head[u] = totEdge++;
}
void dfs(int x,int fa,int dep,int &cntOfSeq)
{
	father[x] = fa;
	vis[x] = true;
	root[x] = update(1,n,a[x],root[fa]);
	sequence[++cntOfSeq] = x;
	deep[cntOfSeq] = dep;
	First[x] = cntOfSeq;
	for(int i=head[x];i!=-1;i=edge[i].Next)
	{
		int to = edge[i].to;
		if(vis[to]) continue;
		vis[to] = true;
		dfs(to,x,dep+1,cntOfSeq);
		sequence[++cntOfSeq] = x;
		deep[cntOfSeq] = dep;
	}
}
void getST(int n)
{
	For(i,1,n) Min[i][0] = i;
	for(int j=1;(1<<j)<=n;++j)
	{
		for(int i=1;i+(1<<j)-1<=n;++i)
		{
			int a = Min[i][j-1];
			int b = Min[i+(1<<(j-1))][j-1];
			Min[i][j] = deep[a]>deep[b]?b:a;
		}
	}
} 
int LCA(int x,int y)
{
	x = First[x];
	y = First[y];
	if(x>y) swap(x,y);
	int j = Log2[y-x+1];
	int a = Min[x][j];
	int b = Min[y-(1<<j)+1][j];
	return deep[a]>deep[b]?sequence[b]:sequence[a];
}
Node * update(int left,int right,int v,Node * p)
{
	if(v<left||v>right) return p;
	Node * t = &node[cnt++];
	t->Lchild = p->Lchild;
	t->Rchild = p->Rchild;
	t->sum = p->sum + 1; 
	if(left==right) return t;
	int mid = (left+right)>>1;
	t -> Lchild = update(left,mid,v,p->Lchild);
	t -> Rchild = update(mid+1,right,v,p->Rchild);
	return t;	
}
void build()
{
	cnt = 0;
	root[0] = &node[cnt++];
	root[0]->Lchild = root[0]->Rchild = root[0];
	root[0]->sum = 0;
}
int query(int left,int right,int k,Node*ru,Node*rv,Node *rlca,Node*rfalca)
{
	if(left==right) return left;
	int tot = ru->Lchild->sum + rv->Lchild->sum 
	     - rlca->Lchild->sum - rfalca->Lchild->sum;
	int mid = (left+right)>>1;
	if(k<=tot) 
		return query(left,mid,k,ru->Lchild,rv->Lchild,rlca->Lchild,rfalca->Lchild);
	else 
		return query(mid+1,right,k-tot,ru->Rchild,rv->Rchild,rlca->Rchild,rfalca->Rchild);
}

D.Super Mario HDU-4417
题意：
  一个数列，求区间内元素值<=H的个数

两种做法：

  1. 主席树
  2. 离线+线段树

主席树的代码：

/* Status：Accepted Time：187ms Memory：23708kB Length：1690 Lang：G++ Submitted：2019-04-09 21:07:54 */
//主席树，数组模拟 
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back 
using namespace std;
const int maxn = 1e5+10; 
int a[maxn],p[maxn],n,cnt;
struct Node{
	int Lchild,Rchild,sum;
}node[maxn*20];
int root[maxn*20];
int update(int left,int right,int v,int p)
{
	if(v<left||v>right) return p;
	int t = cnt++;
	node[t].Lchild = node[p].Lchild;
	node[t].Rchild = node[p].Rchild;
	node[t].sum = node[p].sum+1;
	if(left==right) return t;
	int mid = (left+right)>>1;
	node[t].Lchild = update(left,mid,v,node[p].Lchild);
	node[t].Rchild = update(mid+1,right,v,node[p].Rchild);
	return t;
} 
void build()
{
	cnt = 0;
	root[0] = cnt++;
	node[0].Lchild = node[0].Rchild = node[0].sum = 0;
	For(i,1,n) root[i] = update(1,n,a[i],root[i-1]);
}
int query(int left,int right,int qx,int qy,int rx,int ry)
{
	if(left>qy || right<qx) return 0;
	if(qx<=left&&right<=qy) return node[ry].sum - node[rx].sum;
	int mid = (left+right)>>1;
	int ansL = query( left,  mid,qx,qy,node[rx].Lchild,node[ry].Lchild);
	int ansR = query(mid+1,right,qx,qy,node[rx].Rchild,node[ry].Rchild);
	return ansL + ansR;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int m,T;scanf("%d",&T);
	For(ca,1,T)
	{
		scanf("%d%d",&n,&m);
		For(i,1,n) scanf("%d",a+i), p[i] = a[i];
		sort(p+1,p+n+1);
		For(i,1,n) a[i] = lower_bound(p+1,p+n+1,a[i])-p;
		build();
		int l,r,H;
		printf("Case %d:\n",ca);
		while(m--)
		{
			scanf("%d%d%d",&l,&r,&H);
			H = upper_bound(p+1,p+n+1,H)-p-1;
			printf("%d\n",query(1,n,1,H,root[l],root[r+1]));
		}
	}

	return 0;
}

离线+线段树：

/* Status: Accepted Time：171ms Memory：6236kB Length：1892 Lang：G++ Submitted：2019-04-09 21:10:02 */
//贴的之前erd老师课堂上写的线段树+离线
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn = 1e5+100;
struct A{
	int x,id;
}a[maxn];
struct Node{
	int left,right,sum; //or id
	int mid(){return (left+right)>>1;}
}tree[maxn<<2]; 
struct Re{
	int L,R,h,id,ans;
	void input(int _id)
	{
		scanf("%d%d%d",&L,&R,&h);
		id = _id;
		++L,++R;
	}
}r[maxn];
void build(int left,int right,int pos=1)
{
	tree[pos].left = left;
	tree[pos].right = right;
	tree[pos].sum = 0;
	if(tree[pos].left==tree[pos].right) 
		return;
	int mid = (left+right)>>1;
	build(left,mid,pos<<1);
	build(mid+1,right,pos<<1|1);	
}
void Insert(int x,int pos=1)
{
	
	if(tree[pos].left==tree[pos].right)
	{
		++tree[pos].sum;
		return;
	}
		
	int mid = tree[pos].mid();
	if(x<=mid) Insert(x,pos<<1);
	else Insert(x,pos<<1|1);
	tree[pos].sum = tree[pos<<1].sum+tree[pos<<1|1].sum;
}
int quire(int left,int right,int pos=1)
{
	if(left>tree[pos].right||right<tree[pos].left)
		return 0;
	if(left<=tree[pos].left&&right>=tree[pos].right)
		return tree[pos].sum;
	int Ls = quire(left,right,pos<<1);
	int Rs = quire(left,right,pos<<1|1);
	return Ls+Rs;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	int m,n;
	For(ca,1,T)
	{
		scanf("%d%d",&n,&m);
		build(1,n); 
		For(i,1,n) scanf("%d",&a[i].x),a[i].id = i;
		For(i,0,m-1)
		{
			r[i].input(i);
		}
		sort(a+1,a+n+1,[](A xa,A xb){return xa.x<xb.x;});
		sort(r,r+m,[](Re xx,Re yy){return xx.h<yy.h;});
		int k = 1;
		For(i,0,m-1) 
		{
			while(k<=n&&a[k].x<=r[i].h) Insert(a[k++].id);
			r[i].ans = quire(r[i].L,r[i].R); 
		}
		sort(r,r+m,[](Re xx,Re yy){return xx.id<yy.id;});
		printf("Case %d:\n",ca);
		For(i,0,m-1)
			printf("%d\n",r[i].ans);
	}
	
	return 0;	
}

E-To the moon HDU - 4348
题意：

  • 维护区间和
  • 一开始给出数列a[n]的初值，时间戳t为0
  • C L R add 更新操作，把数列[L,R]这部分都加上add,并且时间戳t++
  • Q L R 询问操作，询问当前时间下数列区间[L,R]的和
  • H L R h 询问操作，询问过去某个时间h(h<t)的区间和[L,R]
  • B tt 时间点回到过去的tt(tt<t)

分析：
  可持久化线段树
  每次更新(C操作)的时候，时间戳t++,新建一棵线段树，并记录线段树根节点的在内存池中的编号为root[t]
  询问H时，在root[H]的那棵线段树中查询
  询问当前区间时，在root[t]的线段树中查询
  B操作时，直接把t该为tt,然后cnt=root[tt+1]这样省空间，相当于是delete了后面的所有树(我觉得这一点我写得非常好~)
  int build(left,right)函数用于建立第一棵t=0时的树，返回值为该节点从内存池中分配的下标
  update(left,right,x,y,add,&t,p)函数用引用的方式实现了返回新分配节点的下标，这个几点表示的区间为[left,right],要更新的范围是[x,y]，都+add, t用于返回下标，p是先前时间戳为t-1时候的线段树根节点的下标
  采用永久化标记的思想，lazy不push_down；不论是更新还是查询，当前节点代表的区间[left,right]一定包含了要查询或者更新的范围[x,y]。

  • 在更新中，进入函数的节点都是包含了更新范围的，都是要新建的节点，如果两个范围下好重合，那么直接lazy+=add;return;不必再往下新建子节点了
  • 在查询中，进入函数的节点区间一定也是包含了查询范围的，如果恰好重合，那么return sum[t];不然，就分类讨论要查询区间是在左子树，还是右子树，还是跨了mid。
  • 这个[left,righy]一定包含[x,y]的性质使得我们可以直接求出lazy*(y-x+1)
程序还是跑得飞快的，空间也不多

代码：

/* Status: Accepted Time: 218ms Memory: 10816kB Length: 2608 Lang: G++ Submitted: 2019-04-11 21:40:54 */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+4;
const int N = maxn*20;
int a[maxn];
int lson[N],rson[N],root[N],n,cnt;
LL sum[N],lazy[N];
int build(int left,int right)
{
    int t = ++cnt;
    lazy[t] = 0;
    if(left==right)
    {
        sum[t] = a[left];
        return t;
    }
    int mid = (left+right)>>1;
    lson[t] = build(left,mid);
    rson[t] = build(mid+1,right);
    sum[t] = sum[lson[t]]+sum[rson[t]];
    return t;
}
void update(int left,int right,int x,int y,int add,int &t,int p)
{
    t = ++cnt; ///该区间[left,right]一定包含要更新的区间[x,y]
    lazy[t] = lazy[p];
    lson[t] = lson[p];
    rson[t] = rson[p];
    sum[t] = sum[p]+1ll*(y-x+1)*add;
    if(left==x&&right==y)
    {
        lazy[t] += add;
        return;
    }
    int mid = (left+right)>>1;
    if(y<=mid) update(left,mid,x,y,add,lson[t],lson[p]);
    else if(x>mid) update(mid+1,right,x,y,add,rson[t],rson[p]);
    else
        update(left,mid,x,mid,add,lson[t],lson[p]),
        update(mid+1,right,mid+1,y,add,rson[t],rson[p]);
}
LL query(int left,int right,int qx,int qy,int t)
{
    if(left==qx&&right==qy) return sum[t];
    LL add = lazy[t]*(qy-qx+1);
    int mid = (left+right)>>1;
    if(qy<=mid) return query(left,mid,qx,qy,lson[t])+add;
    else if(qx>mid) return query(mid+1,right,qx,qy,rson[t])+add;
    else return
        query(left,mid,qx,mid,lson[t])+
        query(mid+1,right,mid+1,qy,rson[t])+add;
}

int main()
{
    int m,t,tt,h,l,r,add,ca=0;
    char op[3];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        For(i,1,n) scanf("%d",a+i);
        cnt = -1;
        root[0] = build(1,n);
        if(ca++) printf("\n");
        t = 0; ///current time
        while(m--)
        {
            scanf("%s",op);
            switch (op[0])
            {
                case 'Q':
                    scanf("%d%d",&l,&r);
                    printf("%lld\n",query(1,n,l,r,root[t]));
                    break;
                case 'B':
                    scanf("%d",&t);cnt = root[t+1]-1;
                    break;
                case 'H':
                    scanf("%d%d%d",&l,&r,&tt);
                    printf("%lld\n",query(1,n,l,r,root[tt]));
                    break;
                case 'C':scanf("%d%d%d",&l,&r,&add);
                    ++t;
                    update(1,n,l,r,add,root[t],root[t-1]);
                    break;
            }
        }
    }
    return 0;
}
全部评论

相关推荐

11-23 12:12
华东师范大学 FAE
点赞 评论 收藏
分享
11-26 13:37
已编辑
贵阳人文科技学院 Web前端
点赞 评论 收藏
分享
10-09 09:39
门头沟学院 C++
第一个正式offer
😭😭😭
HHHHaos：这也太虚了，工资就一半是真的
点赞 评论 收藏
分享
11-25 15:40
重庆理工大学 汽车电子工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
236982次浏览 2039人参与
# 机械求职避坑tips #
23542次浏览 249人参与
# 阿里云管培生offer #
62197次浏览 1759人参与
# 25届秋招总结 #
409261次浏览 4106人参与
# 25届机械人为了秋招做了哪些准备？ #
26210次浏览 363人参与
# 地方国企笔面经互助 #
6898次浏览 17人参与
# 北方华创开奖 #
66951次浏览 552人参与
# ai智能作图 #
28225次浏览 336人参与
# 虾皮求职进展汇总 #
90012次浏览 735人参与
# 实习，投递多份简历没人回复怎么办 #
2440125次浏览 34739人参与
# 软件开发投递记录 #
1481159次浏览 23946人参与
# 我的实习求职记录 #
6131487次浏览 84012人参与
# 我在牛爱网找对象 #
74774次浏览 554人参与
# 发工资后，你做的第一件事是什么 #
8944次浏览 41人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
82991次浏览 600人参与
# 机械人怎么评价今年的华为 #
157867次浏览 1351人参与
# 京东求职进展汇总 #
512706次浏览 4678人参与
# 如果可以，你希望哪个公司来捞你 #
33708次浏览 195人参与
# 你觉得通信/硬件有必要实习吗？ #
54755次浏览 697人参与
# 歌尔求职进展汇总 #
42887次浏览 294人参与
# 在职场上，你最讨厌什么样的同事 #
6022次浏览 91人参与
# 如果再来一次，你还会选择这个工作吗？ #
115248次浏览 1137人参与
牛客网
牛客企业服务