1、Dynamic Rankings

區(qū)間帶修改的第 \(k\) 大需要用帶修改主席樹。

如果用平常的主席樹的效率是多少呢？

查詢 \(O(logn)\)，暴力修改 \(O(nlogn)\)，時間不支持

那么就需要平衡一下兩者的時間復(fù)雜度

我們用樹狀數(shù)組套主席樹，每次查詢把 \(logn\) 個 \(rt\) 取出來，\(l-1\) 和 \(r\) 的 \(sum\) 相減一下，在值域進(jìn)行 \(logn\) 的遍歷，時間復(fù)雜度 \(O(nlog^2n)\)

int query(int l,int r,int k){if(l == r) return l;int x=0,mid=(l+r)>>1;for(int i=1;i<=cnt1;i++) x-=sum[L[lT[i]]];for(int i=1;i<=cnt2;i++) x+=sum[L[rT[i]]];if(x >= k){for(int i=1;i<=cnt1;i++) lT[i]=L[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=L[rT[i]];return query(l,mid,k);}else {for(int i=1;i<=cnt1;i++) lT[i]=R[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=R[rT[i]];return query(mid+1,r,k-x);} }

每次修改在樹狀數(shù)組上，遍歷到一個點(diǎn)就 \(update\)，動態(tài)開點(diǎn)

void update(int &now,int l,int r,int x,int v){if(!now) now=++tot;sum[now]+=v;if(l == r) return ;int mid=(l+r)>>1;if(x <= mid) update(L[now],l,mid,x,v);else update(R[now],mid+1,r,x,v); }void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))update(T[i],1,n,a[x],v); }

每次修改要新開一條鏈上 \(logn\) 個結(jié)點(diǎn)，一共執(zhí)行 \(logn\) 次，空間復(fù)雜度 \(O(nlog^2n)\)

不難證明時間復(fù)雜度 \(O(nlog^2n)\)

\(Code\ Below:\)

#include <bits/stdc++.h> #define lowbit(x) ((x)&(-(x))) using namespace std; const int maxn=100000+10; int n,m,a[maxn],mp[maxn<<1],cnt; int T[maxn],lT[maxn],rT[maxn],L[maxn*400],R[maxn*400],sum[maxn*400],tot,cnt1,cnt2;struct Query{int opt,l,r,k; }q[maxn];inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; }void update(int &now,int l,int r,int x,int v){if(!now) now=++tot;sum[now]+=v;if(l == r) return ;int mid=(l+r)>>1;if(x <= mid) update(L[now],l,mid,x,v);else update(R[now],mid+1,r,x,v); }void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i)) update(T[i],1,cnt,a[x],v); }int query(int l,int r,int k){if(l == r) return l;int x=0,mid=(l+r)>>1;for(int i=1;i<=cnt1;i++) x-=sum[L[lT[i]]];for(int i=1;i<=cnt2;i++) x+=sum[L[rT[i]]];if(x >= k){for(int i=1;i<=cnt1;i++) lT[i]=L[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=L[rT[i]];return query(l,mid,k);}else {for(int i=1;i<=cnt1;i++) lT[i]=R[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=R[rT[i]];return query(mid+1,r,k-x);} }int main() {n=read(),m=read();for(int i=1;i<=n;i++) mp[++cnt]=a[i]=read();char ch;for(int i=1;i<=m;i++){ch=getchar();while(!isalpha(ch)) ch=getchar();q[i].opt=(ch=='Q')?1:2;if(q[i].opt==1) q[i].l=read(),q[i].r=read(),q[i].k=read();else q[i].l=read(),mp[++cnt]=q[i].k=read();}sort(mp+1,mp+cnt+1);cnt=unique(mp+1,mp+cnt+1)-mp-1;for(int i=1;i<=n;i++) a[i]=lower_bound(mp+1,mp+cnt+1,a[i])-mp,add(i,1);for(int i=1;i<=m;i++){if(q[i].opt==1){cnt1=cnt2=0;for(int j=q[i].l-1;j>0;j-=lowbit(j)) lT[++cnt1]=T[j];for(int j=q[i].r;j>0;j-=lowbit(j)) rT[++cnt2]=T[j];printf("%d\n",mp[query(1,cnt,q[i].k)]);}else {q[i].k=lower_bound(mp+1,mp+cnt+1,q[i].k)-mp;add(q[i].l,-1);a[q[i].l]=q[i].k;add(q[i].l,1);}}return 0; }

\([1,pos[x]-1]\) 中大于 \(x\) 的數(shù)的個數(shù)和當(dāng)前在 \([pos[x]+1,n]\) 中小于 \(x\) 的數(shù)

帶修改主席樹即可，時間復(fù)雜度 \(O(nlog^2n)\)，空間復(fù)雜度 \(O(nlog^2n)\)

\(Code\ Below:\)

#include <bits/stdc++.h> #define ll long long #define lowbit(x) ((x)&(-(x))) using namespace std; const int maxn=100000+10; int n,m,a[maxn],pos[maxn];ll ans; int T[maxn],lT[maxn],rT[maxn],L[maxn*400],R[maxn*400],sum[maxn*400],tot,cnt1,cnt2;inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; }namespace unorder_pair{struct Binary_Index_Tree{int c[maxn];void update(int x,int y){for(;x<=n;x+=lowbit(x)) c[x]+=y;}int sum(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=c[x];return ans;}}T;ll solve(){ll ans=0;for(int i=n;i>=1;i--){ans+=T.sum(a[i]);T.update(a[i],1);}return ans;} }void update(int &now,int l,int r,int x,int v){if(!now) now=++tot;sum[now]+=v;if(l == r) return ;int mid=(l+r)>>1;if(x <= mid) update(L[now],l,mid,x,v);else update(R[now],mid+1,r,x,v); }void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))update(T[i],1,n,a[x],v); }int query(int l,int r,int v,int sta){if(l>r) return 0;cnt1=cnt2=0;for(int i=l-1;i>0;i-=lowbit(i)) lT[++cnt1]=T[i];for(int i=r;i>0;i-=lowbit(i)) rT[++cnt2]=T[i];l=1,r=n;int mid,ans=0;while(l!=r){mid=(l+r)>>1;if(mid < v){if(!sta){for(int i=1;i<=cnt1;i++) ans-=sum[L[lT[i]]];for(int i=1;i<=cnt2;i++) ans+=sum[L[rT[i]]];}for(int i=1;i<=cnt1;i++) lT[i]=R[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=R[rT[i]];l=mid+1;}else {if(sta){for(int i=1;i<=cnt1;i++) ans-=sum[R[lT[i]]];for(int i=1;i<=cnt2;i++) ans+=sum[R[rT[i]]];}for(int i=1;i<=cnt1;i++) lT[i]=L[lT[i]];for(int i=1;i<=cnt2;i++) rT[i]=L[rT[i]];r=mid;}}return ans; }int main() {n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]]=i;ans=unorder_pair::solve();for(int i=1;i<=n;i++) add(i,1);int x;for(int i=1;i<=m;i++){x=read();printf("%lld\n",ans);ans-=(ll)query(1,pos[x]-1,x,1);ans-=(ll)query(pos[x]+1,n,x,0);add(pos[x],-1);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/owencodeisking/p/9978768.html

總結(jié)

以上是生活随笔為你收集整理的[学习笔记]带修改主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。