layout: post
title: 洛谷试炼场 4-17 主席树
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 主席树
- 数据结构
- 洛谷
P3834 【模板】可持久化线段树 1（主席树）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,cnt,root[maxn],a[maxn],x,y,k;
struct node{int l,r,sum;}T[maxn*20];
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int l,int r,int &x,int y,int pos){
T[++cnt]=T[y],T[cnt].sum++,x=cnt;
if(l==r)return;
int mid=(l+r)/2;
if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos);
else update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k){
if(l==r)return l;
int mid=(l+r)/2;
int sum=T[T[y].l].sum-T[T[x].l].sum;
if(sum>=k)return query(l,mid,T[x].l,T[y].l,k);
else return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
template <class T>
inline bool read(T &ret){
char c;int sgn;if(c=getchar(),c==EOF)return 0;
while(c!='-'&&(c<'0'||c>'9'))c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');ret*=sgn;return 1;
}
inline void out(int x){if(x>9)out(x/10);putchar(x%10+'0');}
int main()
{
/* std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);*/
read(n);read(m);
for(int i=1;i<=n;i++)read(a[i]),v.push_back(a[i]);
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],getid(a[i]));
while(m--){
// cin>>x>>y>>k;
read(x);read(y);read(k);
out(v[query(1,n,root[x-1],root[y],k)-1]);puts("");
// cout<<v[query(1,n,root[x-1],root[y],k)-1]<<endl;
}
return 0;
}
P2617 Dynamic Rankings (主席树套树状数组)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{int l,r,sum;}s[maxn*20];
vector<int>v;
struct quest{char op;int x,y,k;}Q[maxn];
inline int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
inline int lowbit(int x){return x&(-x);}
int a[maxn],b[maxn],T[maxn];
int n,m;
int tot;
int len;
int temp[2][100],cnt[2];
void update(int &now,int l,int r,int pos,int val){
if(now==0)now=++tot;
s[now].sum+=val;
if(l==r)return;
int mid=(l+r)/2;
if(pos<=mid)update(s[now].l,l,mid,pos,val);
else update(s[now].r,mid+1,r,pos,val);
}
void uptree(int x,int val){
int pos=get(a[x]);
for(int i=x;i<=n;i+=lowbit(i))update(T[i],1,len,pos,val);
}
int query(int l,int r,int k){
if(l==r)return l;
int x=0,mid=(l+r)/2;
for(int i=1;i<=cnt[1];i++)x+=s[s[temp[1][i]].l].sum;
for(int i=1;i<=cnt[0];i++)x-=s[s[temp[0][i]].l].sum;
if(k<=x){
for(int i=1;i<=cnt[1];i++)temp[1][i]=s[temp[1][i]].l;
for(int i=1;i<=cnt[0];i++)temp[0][i]=s[temp[0][i]].l;
return query(l,mid,k);
}
else{
for(int i=1;i<=cnt[1];i++)temp[1][i]=s[temp[1][i]].r;
for(int i=1;i<=cnt[0];i++)temp[0][i]=s[temp[0][i]].r;
return query(mid+1,r,k-x);
}
}
int qutree(int x,int y,int k){
memset(temp,0,sizeof(temp));
cnt[0]=cnt[1]=0;
for(int i=y;i;i-=lowbit(i))temp[1][++cnt[1]]=T[i];
for(int i=x-1;i;i-=lowbit(i))temp[0][++cnt[0]]=T[i];
return query(1,len,k);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i],v.push_back(a[i]);
for(int i=1;i<=m;i++){
cin>>Q[i].op>>Q[i].x>>Q[i].y;
if(Q[i].op=='Q')cin>>Q[i].k;
else v.push_back(Q[i].y);
}
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
len=v.size();
for(int i=1;i<=n;i++)uptree(i,1);
for(int i=1;i<=m;i++){
if(Q[i].op=='Q')cout<<v[qutree(Q[i].x,Q[i].y,Q[i].k)-1]<<endl;
else{
uptree(Q[i].x,-1);
a[Q[i].x]=Q[i].y;
uptree(Q[i].x,1);
}
}
return 0;
}
[P3157 CQOI2011]动态逆序对 (主席树套树状数组)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{int l,r,sum;}T[maxn*20];
int a[maxn],p[maxn],c[maxn],uu,pre[maxn],suf[maxn];
int xx[100],yy[100];
int n,m,ooo,rot[maxn];
inline int lowbit(int x){return x&(-x);}
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;
}
int getsum(int x){
int k=0;
for(int i=x;i;i-=lowbit(i))k+=c[i];return k;
}
int query(int o,int l,int r,int x,int y){
if(!o)return 0;
if(l>=x&&r<=y)return T[o].sum;
else{
int mid=(l+r)/2;
int ans=0;
if(x<=mid)ans+=query(T[o].l,l,mid,x,y);
if(mid<y)ans+=query(T[o].r,mid+1,r,x,y);
return ans;
}
}
int queryRange(int uu,int vv,int xx,int yy){
int tmp=0;
for(int i=uu-1;i;i-=lowbit(i))
tmp-=query(rot[i],1,n,xx,yy);
for(int i=vv;i;i-=lowbit(i))
tmp+=query(rot[i],1,n,xx,yy);
return tmp;
}
void update(int &rt,int l,int r,int x){
if(!rt)rt=++ooo;
T[rt].sum++;
if(l==r)return;
int mid=(l+r)/2;
if(x<=mid)update(T[rt].l,l,mid,x);
if(mid<x)update(T[rt].r,mid+1,r,x);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m;
ll ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
p[a[i]]=i;
pre[i]=getsum(n)-getsum(a[i]);
ans+=pre[i];
add(a[i],1);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
suf[i]=getsum(a[i]-1);
add(a[i],1);
}
while(m--){
cout<<ans<<endl;
cin>>uu;
uu=p[uu];
ans-=pre[uu]+suf[uu];
ans+=queryRange(1,uu-1,a[uu]+1,n);
ans+=queryRange(uu+1,n,1,a[uu]-1);
for(int i=uu;i<=n;i+=lowbit(i))
update(rot[i],1,n,a[uu]);
}
return 0;
}