bzoj 3600: 没有人的算术

柔光的暖阳◎ 2021-10-01 02:04 219阅读 0赞

## Description ##

![1146405-20180701193722774-1631134025.jpg][]

## Solution ##

我们可以给每一个数钦定一个权值 , 这样就可以 \\(O(1)\\) 比较大小了.  
考虑怎么确定权值:  
用平衡树来维护 , 我们假设根节点管辖 \\(\[1,2^\{60\}\]\\) 的数 , 根节点的右儿子都比根节点权值大 , 左儿子权值都都比根节点小  
左儿子管辖 \\(\[1,2^\{59\}-1\]\\) , 右儿子管辖 \\(\[2^\{59\}+1,2^\{60\}\]\\) 这样分下去 , 但是插入可能会导致不平衡 , 使得深度过大, 不断除以 \\(2\\) 最后变成小数 , 导致精度误差 , 最后无法比较大小 .  
于是我们就采用替罪羊树维护 , 这样就可以保证深度了 , 当某个节点 \\(x\\) 满足 \\(max(size\[lson\],size\[rson\])>=size\[x\]\*0.75\\) 我们就暴力重构 .  
询问用线段树维护 , 每个节点维护每个位置在替罪羊树上对应的节点编号 , 每一次通过查询权值就可以比较大小 .

#include<bits/stdc++.h> #define LS (o<<1) #define RS (o<<1|1) #define I set<int>::iterator using namespace std; typedef long long ll; const int N=1e6+10;const ll M=1ll<<60; int n,Q,ls[N],rs[N],P; ll w[N];int tr[N*4],id[N]; struct data{ int x,y; inline bool operator <(const data &p)const{ return x!=p.x?w[x]<w[p.x]:w[y]<w[p.y];} }v[N]; inline int merge(int x,int y){ return id[x]==id[y]?x:(w[id[x]]>w[id[y]]?x:y); } inline void build(int l,int r,int o){ if(l==r){tr[o]=l;id[l]=0;return ;} int mid=(l+r)>>1; build(l,mid,LS);build(mid+1,r,RS); tr[o]=merge(tr[LS],tr[RS]); } inline void ins(int l,int r,int o,int sa){ if(l==r){id[l]=P;return ;} int mid=(l+r)>>1; if(sa<=mid)ins(l,mid,LS,sa); else ins(mid+1,r,RS,sa); tr[o]=merge(tr[LS],tr[RS]); } inline int qry(int l,int r,int o,int sa,int se){ if(sa<=l && r<=se)return tr[o]; int mid=(l+r)>>1; if(se<=mid)return qry(l,mid,LS,sa,se); if(sa>mid)return qry(mid+1,r,RS,sa,se); return merge(qry(l,mid,LS,sa,mid),qry(mid+1,r,RS,mid+1,se)); } ll _l,_r;int *t,rt=0,tt=0,sz[N],top=0,st[N]; inline void insert(ll l,ll r,int &x,data p){ ll mid=(l+r)>>1; if(!x)x=++tt,w[x]=mid,v[x]=p; ++sz[x]; if(v[x].x==p.x && v[x].y==p.y){P=x;return ;} if(p<v[x])insert(l,mid-1,ls[x],p); else insert(mid+1,r,rs[x],p); if(max(sz[ls[x]],sz[rs[x]])>sz[x]*0.75)t=&x,_l=l,_r=r; } inline void dfs(int x){ if(!x)return ; dfs(ls[x]);st[++top]=x; dfs(rs[x]); } inline void build(int l,int r,ll L,ll R,int &x){ int mid=(l+r)>>1; x=st[mid],w[x]=(L+R)>>1,ls[x]=rs[x]=0; if(l<mid)build(l,mid-1,L,w[x]-1,ls[x]); if(mid<r)build(mid+1,r,w[x]+1,R,rs[x]); sz[x]=sz[ls[x]]+sz[rs[x]]+1; } inline void Insert(data p){ t=NULL,insert(1,M,rt,p); if(t!=NULL){ top=0; dfs(*t);build(1,top,_l,_r,*t); } } int main(){ freopen("calc.in","r",stdin); freopen("calc.out","w",stdout); cin>>n>>Q; build(1,n,1); char op[2];int x,y,k; while(Q--){ scanf("%s%d%d",op,&x,&y); if(op[0]=='C'){ Insert((data){id[x],id[y]}); scanf("%d",&k); ins(1,n,1,k); } else printf("%d\n",qry(1,n,1,x,y)); } return 0; }

转载于:https://www.cnblogs.com/Yuzao/p/9251058.html

[1146405-20180701193722774-1631134025.jpg]: /images/20210724/821837b042d54b829ff9d0b47e0b1fdc.png