首页 > 其他分享 >平衡树

平衡树

时间：2023-10-25 10:12:18浏览次数：29  
标签：lc val int siz tr rc 平衡

20231025

平衡树

前期的内容写在PPT上面。。。

平衡树线段树五问：

  1. 每个节点需要记录那些信息？
  2. 需要哪些标记？
  3. 如何下传标记？
  4. 如何区间整体修改？
  5. 如何合并区间（上传信息）？

image

P3215 [HNOI2011] 括号修复 / [JSOI2011]括号序列

Statement

现在给你一个长度为 \(n\) 的由(和)组成的字符串，位置标号从 \(1\) 到 \(n\)。对这个字符串有下列四种操作：

  • Replace a b c：将 \([a,b]\) 之间的所有括号改成 \(c\)。假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。

  • Swap a b：将 \([a,b]\) 之间的字符串翻转。假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。

  • Invert a b：将 \([a,b]\) 之间的 ( 变成 ) ，) 变成 (。假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。

  • Query a b：询问 \([a,b]\) 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 ( 变成 ) 或 ) 变成 (。注意执行操作 Query 并不改变当前的括号序列。假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 \(2\)，因为要将位置 \(5\) 的)变成(并将位置 \(6\) 的(变成)。

对于 \(100\%\) 的数据，\(1\le n,q \le 10^5\)。

Solution

问题主要在于 query 时的查询，

我们钦定 ( 记作 -1 ，) 记作 1 ，于是我们只需要维护前缀最大值 \(prmx\) 和后缀最小值 \(sfmn\) ，那么一个区间的答案就是：

\[\lceil prmx/2 \rceil+\lceil sfmx/2 \rceil \]

画画图就很容易证明。

于是现在考虑具体操作：

  1. 每个节点需要记录那些信息：区间和，前缀最大最小，后缀最大最小
  2. 需要哪些标记：翻转标记，覆盖标记，取反标记
  3. 如何下传标记：翻转（直接像文艺平衡树），覆盖（把区间维护的信息都改变），取反（前后缀最大最小交换，\(prmx\to-prmn,prmn\to -prmax\)）
  4. 区间整体修改？把前驱后继分别转到根和根的右儿子。
  5. 合并区间？枚举是否有左右儿子即可。

为什么有那么长的代码？？？

注意前面有一个哨兵，所以转的时候是转 \(l,r+2\)

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,cnt=0,rt=0,a[N];
struct Splay{
  int fa,siz,sum,val,prmx,prmn,sfmx,sfmn,s[2],inv,rev,cov;
}tr[N];

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

void pu(int p){
  tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;
  tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum+tr[p].val;
  tr[p].prmx=max(tr[lc(p)].prmx,tr[rc(p)].prmx+tr[lc(p)].sum+tr[p].val);
  tr[p].prmn=min(tr[lc(p)].prmn,tr[rc(p)].prmn+tr[lc(p)].sum+tr[p].val);
  tr[p].sfmx=max(tr[rc(p)].sfmx,tr[rc(p)].sum+tr[p].val+tr[lc(p)].sfmx);
  tr[p].sfmn=min(tr[rc(p)].sfmn,tr[rc(p)].sum+tr[p].val+tr[lc(p)].sfmn);
} 

void cov(int p,int val){
  if(!p) return;
  tr[p].cov=val;
  if(val==1){
  	tr[p].sum=tr[p].siz;
  	tr[p].prmn=tr[p].sfmn=0;	
	tr[p].prmx=tr[p].sfmx=tr[p].sum;
  }
  else{
  	tr[p].sum=~tr[p].siz+1;
  	tr[p].prmx=tr[p].sfmx=0;
  	tr[p].prmn=tr[p].sfmn=tr[p].sum;
  }
  tr[p].val=val;
  tr[p].inv=0;
}

void rev(int p){
  if(!p) return;
  tr[p].rev^=1;
  swap(lc(p),rc(p));
  swap(tr[p].prmx,tr[p].sfmx);
  swap(tr[p].prmn,tr[p].sfmn);
}

void inv(int p){
  if(!p) return;
  if(tr[p].cov!=0){
  	if(tr[p].cov==1) cov(p,-1);
  	else cov(p,1);
  	return;
  }
  tr[p].inv^=1;
  int t=tr[p].prmx;
  tr[p].prmx=~tr[p].prmn+1;
  tr[p].prmn=~t+1;
  t=tr[p].sfmx;
  tr[p].sfmx=~tr[p].sfmn+1;
  tr[p].sfmn=~t+1;
  tr[p].sum=~tr[p].sum+1;
  tr[p].val=~tr[p].val+1;
}

void pd(int p){
  if(tr[p].cov!=0){
  	cov(lc(p),tr[p].cov);
  	cov(rc(p),tr[p].cov);
  	tr[p].cov=0;
  }
  if(tr[p].inv!=0) inv(lc(p)),inv(rc(p)),tr[p].inv=0;
  if(tr[p].rev!=0) rev(lc(p)),rev(rc(p)),tr[p].rev=0;
}

void rotate(int x){
  int y=tr[x].fa,z=tr[y].fa;
  int k=(rc(y)==x);
  pd(y);pd(x);
  tr[y].s[k]=tr[x].s[k^1];
  tr[tr[x].s[k^1]].fa=y;
  tr[x].s[k^1]=y;
  tr[y].fa=x;
  tr[z].s[(rc(z)==y)]=x;
  tr[x].fa=z;
  pu(y);pu(x); 
}

void splay(int x,int k){
  while(tr[x].fa!=k){
  	int y=tr[x].fa,z=tr[y].fa;
  	if(z!=k) ((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
  	rotate(x);
  }
  if(k==0) rt=x;
}

int find(int k){
  int p=rt;
  while(k){
  	pd(p);
  	if(k<=tr[lc(p)].siz) p=lc(p);
  	else if(k>tr[lc(p)].siz+1) k-=tr[lc(p)].siz+1,p=rc(p);
  	else break;
  }
  splay(p,0);
  return p;
}

void invert(int l,int r){
  int x=find(l),y=find(r+2);
  splay(x,0);splay(y,x);
  inv(lc(y));
  pu(y);pu(x);
}

void reverse(int l,int r){
  int x=find(l),y=find(r+2);
  splay(x,0);splay(y,x);
  rev(lc(y));
  pu(y);pu(x);
}

void replace(int l,int r,int val){
  int x=find(l),y=find(r+2);
  splay(x,0);splay(y,x);
  cov(lc(y),val);
  pu(y);pu(x);
}

int query(int l,int r){
  int x=find(l),y=find(r+2);
  splay(x,0);splay(y,x);
  x=lc(y);
  return ((tr[x].prmx+1)/2-(tr[x].sfmn-1)/2);
}

#define mid ((l+r)>>1)

int build(int l,int r,int fa){
  if(l>r) return 0;
  int p=++cnt;
  tr[p].val=tr[p].sum=a[mid];
  tr[p].siz=1;tr[p].fa=fa;
  tr[p].s[0]=build(l,mid-1,p);
  tr[p].s[1]=build(mid+1,r,p);
  pu(p);return p; 
} 

void dfs(int p){
  if(!p) return;
  pd(p);
  dfs(lc(p));
  printf("%d:%d %d->%d %d\n",p,lc(p),rc(p),tr[p].val,tr[p].siz);
  printf("%d %d %d %d %d\n",tr[p].sum,tr[p].prmx,tr[p].prmn,tr[p].sfmx,tr[p].sfmn);
  dfs(rc(p));
}

int main(){
  /*2023.10.23 H_W_Y P3215 [HNOI2011] 括号修复 / [JSOI2011]括号序列 Splay*/
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
  	char s=getchar();
  	while(s!='('&&s!=')') s=getchar();
  	if(s=='(') a[i]=-1;
  	else a[i]=1;
  }
  rt=build(0,n+1,0);
  for(int i=1;i<=m;i++){
  	char s[15];int l,r;
    scanf("%s",s);
    scanf("%d%d",&l,&r);
    if(s[0]=='R'){
      char ch;ch=getchar();
      while(ch!='('&&ch!=')') ch=getchar();
      replace(l,r,(ch=='(')?-1:1);
	}
	if(s[0]=='I') invert(l,r);
	if(s[0]=='S') reverse(l,r);
	if(s[0]=='Q') printf("%d\n",query(l,r));
  }
  return 0;
}

P4036 [JSOI2008] 火星人

Statement

序号 1 2 3 4 5 6 7 8 9 10 11 
字符 m a d a m i m a d a m

现在，火星人定义了一个函数 \(LCQ(x, y)\)，表示：该字符串中第 \(x\) 个字符开始的字串，与该字符串中第 \(y\) 个字符开始的字串，两个字串的公共前缀的长度。比方说，\(LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0\)

在求取 \(LCQ\) 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。

  1. 所有字符串自始至终都只有小写字母构成。
  2. \(M\leq150,000\)
  3. 字符串长度L自始至终都满足\(L\leq100,000\)
  4. 询问操作的个数不超过 \(10,000\) 个。

Solution

直接平衡树维护哈希值，查询时二分即可。

注意数据范围！！！

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
mt19937 rd(time(0));

const int N=5e5+5;
int n,l,r,x,y,idx=0,rt=0,z,pos;
const ll base=27;
ll hs[N];
char s[N];
struct Treap{
  int val,key,siz,s[2];
  ll hs;
}tr[N];

void init(){
  hs[0]=1ll;
  for(int i=1;i<=100000;i++) hs[i]=hs[i-1]*base;
}

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(int x){
  int p[15],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

int nwnode(int v){
  idx++;
  tr[idx].val=tr[idx].hs=v;
  tr[idx].key=rd();
  tr[idx].siz=1;
  tr[idx].s[0]=tr[idx].s[1]=0;
  return idx;
}

void pu(int p){
  tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;
  tr[p].hs=tr[lc(p)].hs+1ll*tr[p].val*hs[tr[lc(p)].siz]+tr[rc(p)].hs*hs[tr[lc(p)].siz+1];
}

void split(int p,int k,int &x,int &y){
  if(!p){x=y=0;return;}
  if(tr[lc(p)].siz<k) x=p,split(rc(p),k-tr[lc(p)].siz-1,rc(x),y);
  else y=p,split(lc(p),k,x,lc(p));
  pu(p);
}

int merge(int x,int y){
  if(!x||!y) return (x|y);
  if(tr[x].key<tr[y].key){
  	tr[x].s[1]=merge(tr[x].s[1],y);
  	pu(x);return x;
  }
  else{
  	tr[y].s[0]=merge(x,tr[y].s[0]);
  	pu(y);return y;
  }
}

void ins(int k,int val){
  split(rt,k,x,y);
  rt=merge(merge(x,nwnode(val)),y); 
}

void del(int k){
  split(rt,k,x,z);
  split(x,k-1,x,y);
  y=merge(lc(y),rc(y));
  rt=merge(merge(x,y),z);
}

ll query(int l,int r){
  split(rt,r,x,z);
  split(x,l-1,x,y);
  ll res=tr[y].hs;
  rt=merge(merge(x,y),z);
  return res;
}

int main(){
  /*2023.10.24 H_W_Y P4036 [JSOI2008] 火星人 FHQ-Treap*/
  scanf("%s",s);init();
  for(int i=0;i<(int)strlen(s);i++) ins(i,s[i]-'a');
  n=read();
  for(int i=1;i<=n;i++){
  	scanf("%s",s);
  	if(s[0]=='Q'){
  	  int L=read(),R=read();
	  l=0,r=tr[rt].siz-max(L,R)+1;
	  while(l<r){
	  	int mid=(l+r+1)/2;
	  	if(query(L,L+mid-1)==query(R,R+mid-1)) l=mid;
	  	else r=mid-1;
	  } 
	  print(l);
    }
    else if(s[0]=='R'){
      pos=read();char ch=getchar();
      del(pos);ins(pos-1,ch-'a');
	}
	else{
	  pos=read();char ch=getchar();
	  ins(pos,ch-'a');
	}
  }
  return 0;
}

P4200 千山鸟飞绝

最后一道题哩，写起来怪激动的。

Statement

给定二维平面上的 \(n\) 个带权点，每一时刻改变一个点的坐标，最后问对于每一个点，在每一时刻内与其坐标相同的其他点的个数的最大值 \(a\) 和权值最大值的最大值 \(b\) 之积。

\(1 \le n \le 30000,0 \le m \le 300000\)

Solution

首先需要将坐标离散化，再用多棵平衡树维护。

发现删除一个点的答案一定不会更有，而在加入一个点的时候，

我们首先可以先把该坐标上的点打上标记，再对当前点的答案更新，

直接加入即可。

具体而言，对于每一个节点我们维护 \(mx,siz,tag1,tag2\)，

每次加入一个节点时，我们用 \(mx\) 来更新新加入节点的答案，

而本来的平衡树中 \(tag1=\max(tag1,val),tag2=\max(tag2,siz)\) 即可。

居然一过了！！！

#include <bits/stdc++.h>
using namespace std;
#define ll long long
mt19937 rd(time(0));

const int N=3e5+5;
const ll inf=2e9;
int n,m,rt[N],idx=0,w[N],x,y,z;
ll pos[N],ans1[N],ans2[N];
struct node{
  ll w,x,y,pos;
}a[N],b[N];
struct Treap{
  int siz,id,s[2],key;
  ll val,tag1,tag2,mx,se;
}tr[N];
queue<int> q;

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

void pu(int p){
  tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;
  tr[p].mx=max(tr[p].val,max(tr[lc(p)].mx,tr[rc(p)].mx));
  if(tr[p].mx==tr[p].val) tr[p].se=max(tr[lc(p)].mx,tr[rc(p)].mx);
  else if(tr[p].mx==tr[lc(p)].mx) tr[p].se=max(max(tr[p].val,tr[lc(p)].se),tr[rc(p)].mx);
  else tr[p].se=max(max(tr[p].val,tr[rc(p)].se),tr[lc(p)].mx);  
}

void change(int p,ll tag1,ll tag2){
  if(!p) return;
  int id=tr[p].id;
  ans1[id]=max(ans1[id],tag1);
  ans2[id]=max(ans2[id],tag2);
  tr[p].tag1=max(tr[p].tag1,tag1);
  tr[p].tag2=max(tr[p].tag2,tag2);
}

void pd(int p){
  if(!p) return ;
  if(lc(p)) change(lc(p),tr[p].tag1,tr[p].tag2);
  if(rc(p)) change(rc(p),tr[p].tag1,tr[p].tag2);
  tr[p].tag1=tr[p].tag2=0;
}

int nwnode(ll val,int id){
  int it=0;
  if(!q.empty()) it=q.front(),q.pop();
  else it=++idx;
  tr[it].id=id;
  tr[it].key=rd();
  tr[it].mx=tr[it].val=val;
  tr[it].siz=1;
  tr[it].se=-inf;
  tr[it].s[0]=tr[it].s[1]=tr[it].tag1=tr[it].tag2=0;
  return it;
}

void split(int p,int k,int &x,int &y){
  if(!p){x=y=0;return;}
  pd(p);
  if(tr[p].id<=k) x=p,split(rc(p),k,rc(p),y);
  else y=p,split(lc(p),k,x,lc(p));
  pu(p);
}

int merge(int x,int y){
  if(!x||!y) return (x|y);
  pd(x);pd(y); 
  if(tr[x].key<tr[y].key){
    tr[x].s[1]=merge(tr[x].s[1],y);
	pu(x);return x; 
  }
  else {
  	tr[y].s[0]=merge(x,tr[y].s[0]);
  	pu(y);return y;
  }
}

void del(int id){
  int &rot=rt[w[id]];
  split(rot,id,x,z);
  split(x,id-1,x,y);
  q.push(y);
  y=merge(lc(y),rc(y));
  rot=merge(merge(x,y),z);
}

void ins(int id,int p){
  int &rot=rt[p];
  ans1[id]=max(ans1[id],tr[rot].mx);
  ans2[id]=max(ans2[id],1ll*tr[rot].siz);
  change(rot,a[id].w,tr[rot].siz);
  split(rot,id,x,y);
  rot=merge(merge(x,nwnode(a[id].w,id)),y);
  w[id]=p;
}

void dfs(int p){
  if(!p) return;
  pd(p);
  if(lc(p)) dfs(lc(p));
  if(rc(p)) dfs(rc(p));
}

int main(){
  /*2023.10.25 H_W_Y P4200 千山鸟飞绝 FHQ-Treap*/
  n=read();
  for(int i=1;i<=n;i++){
  	a[i].w=1ll*read(),a[i].x=1ll*read(),a[i].y=1ll*read();
  	pos[i]=a[i].pos=a[i].x*inf+a[i].y;
  }
  m=read();
  for(int i=1;i<=m;i++){
  	b[i].w=read(),b[i].x=1ll*read(),b[i].y=1ll*read();
  	pos[i+n]=b[i].pos=b[i].x*inf+b[i].y;
  }
  sort(pos+1,pos+n+m+1);
  int len=unique(pos+1,pos+n+m+1)-pos-1;
  for(int i=1;i<=n;i++) a[i].pos=lower_bound(pos+1,pos+len+1,a[i].pos)-pos;
  for(int i=1;i<=m;i++) b[i].pos=lower_bound(pos+1,pos+len+1,b[i].pos)-pos;
  for(int i=1;i<=n;i++) ins(i,a[i].pos);
  for(int i=1;i<=m;i++) del(b[i].w),ins(b[i].w,b[i].pos);
  for(int i=1;i<=len;i++) dfs(rt[i]);
  for(int i=1;i<=n;i++) print(ans1[i]*ans2[i]);
  return 0;
}

CF702F T-Shirts

Statement

有 \(n\) 种 T 恤，每种有价格 \(c_i\) 和品质 \(q_i\)。

有 \(m\) 个人要买 T 恤，第 \(i\) 个人有 \(v_i\) 元，每人每次都会买一件能买得起的 \(q_i\) 最大的 T 恤。一个人只能买一种 T 恤一件，所有人之间都是独立的。

问最后每个人买了多少件 T 恤？如果有多个 \(q_i\) 最大的 T 恤，会从价格低的开始买。

\(1 \le n,m \le 2 \times 10^5\) ，时限 \(4s\)

Solution

首先不难想到对于 \(n\) 种 T 恤，我们按照 \(q_i\) 从大到小排序，

如果 \(q_i\) 相同则按照 \(c_i\) 从小到大排序。

对于每一个人，我们可以从前往后遍历一遍，能买就买了。

现在考虑是否可以对于每一种 T恤，我们对整个序列进行操作，

具体来说也就是把 \(\ge c_i\) 的数全部减去 \(c_i\)，并且 \(ans+1\) 。

发现这样并不能保证序列的单调性，

中间在 \(c_i \le val \lt 2 c_i\) 的数有可能产生冲突，

那怎么办呢？

由于 \(c_i \le val \lt 2c_i\) ，那么 \(c_i \gt \frac{val}{2}\)，

所以对于这样的 \(val\) ，我们直接进行暴力的删除和插入，

因为这样的操作最多进行 \(\log val\) 次，每次都会减小到原来的一半。

时限是 \(4s\) ，足以通过，用平衡树维护即可。

时间复杂度 \(O((n+\sum \log_2q_i)\log_2 n)\)。

注意标记要清空！！！

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int n,idx=0,rt,m,ans[N],val[N],x,y,z;
struct node{
  int c,q;
  bool operator <(const node &rhs) const{
    if(q!=rhs.q) return q>rhs.q;
    return c<rhs.c;
  }
}a[N];
struct Treap{
  int siz,val,id,s[2],key,tag,add;
}tr[N];
mt19937 rd(time(0));
queue<int> q; 

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(int x){
  int p[15],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
    p[++tmp]=x%10;
    x/=10;
  } 
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar(' ');
}

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

int nwnode(int val,int id){
  int it;
  if(!q.empty()) it=q.front(),q.pop();
  else it=++idx;
  tr[it].val=val;
  tr[it].id=id;
  tr[it].key=rd();
  tr[it].siz=1;
  tr[it].s[0]=tr[it].s[1]=tr[it].tag=tr[it].add=0;
  return it;
}

void pu(int p){tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;}

void change(int p,int tag,int add){
  if(!p) return ;
  tr[p].tag+=tag;
  tr[p].add+=add;
  ans[tr[p].id]+=add;
  tr[p].val+=tag;
}

void pd(int p){
  if(tr[p].add==0) return;
  if(lc(p)) change(lc(p),tr[p].tag,tr[p].add);
  if(rc(p)) change(rc(p),tr[p].tag,tr[p].add);
  tr[p].tag=0;tr[p].add=0;
}

void split(int p,int k,int &x,int &y){
  if(!p){x=y=0;return;}
  pd(p);
  if(tr[p].val<=k) x=p,split(rc(p),k,rc(p),y);
  else y=p,split(lc(p),k,x,lc(p));
  pu(p); 
}

int merge(int x,int y){
  if(!x||!y) return (x|y);
  pd(x);pd(y);
  if(tr[x].key<tr[y].key){
  	tr[x].s[1]=merge(tr[x].s[1],y);
  	pu(x);return x;
  }
  else{
  	tr[y].s[0]=merge(x,tr[y].s[0]);
  	pu(y);return y;
  }
}

void ins(int &p,int val,int id){
  int xx=0,yy=0;
  split(p,val,xx,yy);
  p=merge(merge(xx,nwnode(val,id)),yy);
}

void dfs(int p,int c){
  if(!p) return ;
  pd(p); 
  if(lc(p)) dfs(lc(p),c);
  if(rc(p)) dfs(rc(p),c);
  q.push(p);ans[tr[p].id]++;
  if(tr[p].val-c>0) ins(x,tr[p].val-c,tr[p].id);
}

void update(int c){
  split(rt,c-1,x,y);
  split(y,2*c,y,z);
  if(z) change(z,-c,1);
  dfs(y,c);
  rt=merge(x,z);
}

void getans(int p){
  pd(p);
  if(lc(p)) getans(lc(p));
  if(rc(p)) getans(rc(p));
}

int main(){
  /*2023.10.25 H_W_Y CF702F T-Shirts FHQ-Treap*/
  n=read();
  for(int i=1;i<=n;i++) a[i].c=read(),a[i].q=read();
  sort(a+1,a+n+1);
  m=read();
  for(int i=1;i<=m;i++) val[i]=read(),ins(rt,val[i],i);
  for(int i=1;i<=n;i++) update(a[i].c);
  getans(rt);
  for(int i=1;i<=m;i++) print(ans[i]);
  return 0;
}

CF809D Hitchhiking in the Baltic States

Statement

给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\)，现在你要确定这 \(n\) 个数，使得 \(a_i\in[l_i,r_i]\)，并且这个序列的最长严格上升子序列尽可能大，求这个最大值。

\(1 \leq n\leq 3\times 10^5\)，\(1 \leq l_i,r_i\leq 10^9\)。

Solution

好题！

见这里

P3835 【模板】可持久化平衡树

Statement

您需要写一种数据结构（可参考题目标题），来维护一个可重整数集合，其中需要提供以下操作（ 对于各个以往的历史版本 ）：

1、 插入 \(x\)

2、 删除 \(x\)（若有多个相同的数，应只删除一个，如果没有请忽略该操作）

3、 查询 \(x\) 的排名（排名定义为比当前数小的数的个数 \(+1\)）

4、查询排名为 \(x\) 的数

5、 求 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数，如不存在输出 \(-2^{31}+1\) ）

6、求 \(x\) 的后继（后继定义为大于 \(x\)，且最小的数，如不存在输出 \(2^{31}-1\) ）

对于 \(100\%\) 的数据， $ 1 \leq n \leq 5 \times 10^5 $ , \(|x_i| \leq {10}^9\)，\(0 \le v_i < i\)，\(1\le \text{opt} \le 6\)。

Solution

顾名思义，就是可持久化的平衡树。

一般使用 FHQ -Treap完成，和普通平衡树的板子没有什么太大区别，

就是在 Split 的时候加上了新建一个节点的操作，再维护一下每一个状态的根即可。

#include <bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
#define ll long long

const int N=5e5+5;
int n,m,idx=0,rt[N];
struct Treap{
  int s[2],siz,key;
  ll val;
}tr[N*50];

int nwnode(ll v=0){
  tr[++idx].val=v;
  tr[idx].key=rd();
  tr[idx].siz=1;
  tr[idx].s[0]=tr[idx].s[1]=0;
  return idx;
}

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

void pushup(int p){tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;}

int merge(int x,int y){
  if(!x||!y) return (x|y);
  if(tr[x].key<tr[y].key){
  	tr[x].s[1]=merge(tr[x].s[1],y);
  	pushup(x);return x;
  }
  else{
  	tr[y].s[0]=merge(x,tr[y].s[0]);
  	pushup(y);return y;
  }
}

void split(int p,ll k,int &x,int &y){
  if(!p){x=y=0;return;}
  if(tr[p].val<=k){
  	x=nwnode();
  	tr[x]=tr[p];
  	split(tr[x].s[1],k,tr[x].s[1],y);
  	pushup(x);
  }
  else{
  	y=nwnode();
  	tr[y]=tr[p];
  	split(tr[y].s[0],k,x,tr[y].s[0]);
  	pushup(y);
  }
}

int find(int p,int k){
  while(1){
  	if(k<=tr[lc(p)].siz) p=lc(p);
  	else{
  	  if(k>tr[lc(p)].siz+1) k-=tr[lc(p)].siz+1,p=rc(p);
	  else return p;	
	}
  }
}

int main(){
  /*2023.10.23 H_W_Y P3835 【模板】可持久化平衡树 FHQ-Treap*/ 
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
  	int x=0,y=0,z=0,op,tmp;ll val;
  	scanf("%d%d%lld",&tmp,&op,&val);
  	rt[i]=rt[tmp];
  	if(op==1){
  	  split(rt[i],val,x,y);
	  rt[i]=merge(merge(x,nwnode(val)),y); 
	}
	if(op==2){
	  split(rt[i],val,x,z);
	  split(x,val-1,x,y);
	  y=merge(tr[y].s[0],tr[y].s[1]);
	  rt[i]=merge(merge(x,y),z);
	}
	if(op==3){
	  split(rt[i],val-1,x,y);
	  printf("%d\n",tr[x].siz+1);
	  rt[i]=merge(x,y);
	}
	if(op==4){
	  printf("%lld\n",tr[find(rt[i],val)].val);
	}
	if(op==5){
	  split(rt[i],val-1,x,y);
	  if(x==0) printf("-2147483647\n");
	  else printf("%lld\n",tr[find(x,tr[x].siz)].val),rt[i]=merge(x,y);
	}
	if(op==6){
	  split(rt[i],val,x,y);
	  if(y==0) printf("2147483647\n");
	  else printf("%lld\n",tr[find(y,1)].val),rt[i]=merge(x,y);
	}
  }
  return 0;
}

P5055 【模板】可持久化文艺平衡树

Statement

您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（对于各个以往的历史版本）：

  1. 在第 \(p\) 个数后插入数 \(x\)。
  2. 删除第 \(p\) 个数。
  3. 翻转区间 \([l,r]\)，例如原序列是 \(\{5,4,3,2,1\}\)，翻转区间 \([2,4]\) 后，结果是 \(\{5,2,3,4,1\}\)。
  4. 查询区间 \([l,r]\) 中所有数的和。

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 \(4\) 即保持原版本无变化），新版本即编号为此次操作的序号。

本题强制在线。

对于 \(100\%\) 的数据，\(1 \le n \le 2 \times {10}^5\)，\(|x_i| < {10}^6\)。

Solution

同样是在每一次 split 的时候每次复制一个节点。

注意 \(lstans\) 是 long long，所以 \(l,r\) 都要开 long long。

#include <bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
#define ll long long

const int N=2e5+5;
int n,idx=0,rt[N];
ll lstans=0;
struct Treap{
  int key,s[2],siz,tag;
  ll val,sum;
}tr[N<<7];

int nwnode(ll v=0){
  idx++;
  tr[idx].val=tr[idx].sum=v;
  tr[idx].key=rd();
  tr[idx].siz=1;
  tr[idx].s[0]=tr[idx].s[1]=tr[idx].tag=0;
  return idx;
}

#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]

void pu(int p){
  tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;
  tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum+tr[p].val;  
}

int cn(int p){
  int x=nwnode();
  tr[x]=tr[p];
  return x;
}

void pd(int p){
  if(!tr[p].tag) return ;
  if(lc(p)) lc(p)=cn(lc(p));
  if(rc(p)) rc(p)=cn(rc(p));
  swap(lc(p),rc(p));
  if(lc(p)) tr[lc(p)].tag^=1;
  if(rc(p)) tr[rc(p)].tag^=1;
  tr[p].tag=0;
}

void split(int p,int k,int &x,int &y){
  if(!p){x=y=0;return;}
  pd(p);
  if(tr[lc(p)].siz<k){
  	x=cn(p);
  	split(rc(x),k-tr[lc(x)].siz-1,rc(x),y);
  	pu(x);
  }
  else {
  	y=cn(p);
  	split(lc(y),k,x,lc(y));
    pu(y);
  }
}

int merge(int x,int y){
  if(!x||!y) return (x|y);
  pd(x);pd(y);
  if(tr[x].key<tr[y].key){
  	tr[x].s[1]=merge(tr[x].s[1],y);
  	pu(x);return x;
  }
  else{
  	tr[y].s[0]=merge(x,tr[y].s[0]);
  	pu(y);return y;
  }
}

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int main(){
  /*2023.10.24 H_W_Y P5055 【模板】可持久化文艺平衡树 FHQ-Treap*/
  n=read();
  for(int i=1;i<=n;i++){
  	int v,opt;ll val,l,r;
  	int x=0,y=0,z=0;
  	scanf("%d%d",&v,&opt);
  	rt[i]=rt[v];
  	if(opt==1){
  	  scanf("%lld%lld",&l,&val);
  	  l^=lstans;val^=lstans; 
	  split(rt[v],l,x,y);
	  rt[i]=merge(x,merge(nwnode(val),y));
	} 
	if(opt==2){
	  scanf("%lld",&l);l^=lstans;
	  split(rt[v],l,x,z);
	  split(x,l-1,x,y);
	  rt[i]=merge(x,z);
	}
	if(opt==3){
	  scanf("%lld%lld",&l,&r);
	  l^=lstans;r^=lstans;
	  split(rt[i],r,x,z);
	  split(x,l-1,x,y);
	  tr[y].tag^=1;
	  rt[i]=merge(merge(x,y),z);
	}
	if(opt==4){
	  scanf("%lld%lld",&l,&r);
	  l^=lstans;r^=lstans;
	  split(rt[v],r,x,z);
	  split(x,l-1,x,y);
	  printf("%lld\n",lstans=tr[y].sum);
	  rt[i]=merge(merge(x,y),z); 
	}
  }
  return 0;
}

标签：lc,val,int,siz,tr,rc,平衡
From： https://www.cnblogs.com/hwy0622/p/balancetree.html

相关文章

  • CF809D Hitchhiking in the Baltic States-平衡树+DP
    CF809DHitchhikingintheBalticStates-平衡树+DPStatement给出\(n\)个区间\([l_i,r_i]\)和\(n\)个未知数\(a_1,a_2,\dots,a_n\)，现在你要确定这\(n\)个数，使得\(a_i\in[l_i,r_i]\)，并且这个序列的最长严格上升子序列尽可能大，求这个最大值。\(1\leqn\leq3\times1......
  • 普通平衡树
    很久以前，我很抗拒使用平衡树。但是这现在是8级算法，我不得不学之。FHQ-Treap核心只有两个操作split和merge。考虑像Treap一样每个点打上rand，使得其满足是rnd的小根堆。然后考虑分裂。考虑每次对于值归类<=的归在\(lt\)，其他归在\(rt\)。考虑每次归入\(lt\)一......
  • 【数据结构】7.平衡搜索树（AVL树和红黑树）
    0.概述对于普通的搜索树，如果一直插入比第一个元素小的元素，它会退化成一个无限向左下角眼神的单链表，使得时间复杂度退化为O(n)。如果我们在插入时保持树的结构是平衡的，则可以保证查找、插入和删除的时间复杂度有对数级的时间性能，下面讲到的AVL树和红黑树都是平衡搜索树，通过旋......
  • 父图子图平衡
      ......
  • 平衡进制问题/对称的2k+1进制问题
    定义平衡\(2k+1\)进制数码为\(-k,-(k-1),,,0,,,k-1,k\)，请求出一个十进制数的\(2k+1\)进制表示。对于该问题，解决的思路是首先算出普通的\(2k+1\)进制下的表示，然后分别对每一位进行考虑.1:这一位的数属于\(0-k\)不用管2:这一位的数属于\(k+1-2k\)设此数等于$k+p$,则将下一......
  • P9233 [蓝桥杯 2023 省 A] 颜色平衡树 （dfs序 莫队）
    P9233[蓝桥杯2023省A]颜色平衡树（dfs序莫队）莫队原理:https://zhuanlan.zhihu.com/p/115243708对于树上的每个结点，按照dfs序打上时间戳，这样就可以把每一个结点对应的子树的答案转化为一个区间的答案。将子树询问离线下来变成\(n\)个区间查询。用\(cnt\)数组维护颜色......
  • 平衡树
    平衡树真的恶心死了！！！！！！好烦啊，又臭又长。有很多种平衡树，替罪羊,treap，fhq,slpay。这里就说splay，和bst和替罪羊了，因为其他我都不会（悲先说二叉排序树（二叉搜索树），他的关系就是左子树所有节点<根节点<右子树所有节点。也就是说，按照中序遍历可以找到有序序列。这个时候我......
  • 深度学习中的样本不平衡问题
    1.什么是样本不平衡问题？所谓的类别不平衡问题指的是数据集中各个类别的样本数量极不均衡。以二分类问题为例，假设正类的样本数量远大于负类的样本数量，通常情况下把样本类别比例超过4:1（也有说3:1）的数据就可以称为不平衡数据。样本不平衡实际上是一种非常常见的现象。比如：在欺诈交易......
  • 化学反应原理 —— 平衡 | 浓缩版
    平衡浓缩版2023.10.10\(\it0\)\(\sfGeneral\Solution\)这一块需要建立一个体系，把所有的知识建立一个结构，把它们互相联系起来。\(\it0.1\)动力学与热力学从动力学的角度考虑问题，就是考虑反应的速率。\(v_正\)\(v_逆\)相等且不变时，反应达到平衡。影响速率的因素：内......
  • 三维模型3DTile格式轻量化的数据压缩与性能平衡关系分析
    三维模型3DTile格式轻量化的数据压缩与性能平衡关系分析 对于三维模型的3DTile格式轻量化处理，数据压缩和性能之间的平衡关系是一个重要的考虑因素。以下是这两者关系的详细分析：1、数据压缩与加载速度：显然，更高级别的压缩可以创造更小的文件大小，从而加快从服务器到客户端的传输......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99