【BZOJ1901】【Luogu2617】Dynamic Ranking(主席树,树状数组)

【BZOJ1901】【Luogu2617】Dynamic Ranking(主席树,树状数组)

题面

神TM BZOJ权限题

Luogu真良心

题解

如果不考虑修改

很容易的主席树区间第K大

考虑修改

那么修改操作复杂度\(O(nlogn)\)

因此,将区间的和利用树状数组来维护

修改复杂度降为\(O(log^2n)\)

虽然查询的复杂度升为\(O(log^2n)\)

但是整体复杂度变为\(O(mlog^2n)\)

于是就愉快的AC了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 20005
#define lson t[now].ls
#define rson t[now].rs
#define mid ((l+r)>>1)
#define Q q
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
int v;
int ls,rs;
}t[MAX<<9];
int tot;
int S[MAX],sum,a[MAX],n,m;
int rt[MAX],cnt0,cnt1;
int tmp[3][MAX];
struct OPT
{
bool opt;
int l,r,k;
int pos,t;
}Q[MAX];
inline int lowbit(int x){return x&(-x);}
void Modify(int &now,int l,int r,int pos,int val)
{
if(!now)now=++tot;
t[now].v+=val;
if(l==r)return;
if(pos<=mid)Modify(lson,l,mid,pos,val);
else Modify(rson,mid+1,r,pos,val);
}
void PreModify(int x,int val)
{
int k=lower_bound(&S[1],&S[sum+1],a[x])-S;
while(x<=n)
{
Modify(rt[x],1,sum,k,val);
x+=lowbit(x);
}
}
int Query(int l,int r,int k)
{
if(l==r)return l;
int s=0;
for(int i=1;i<=cnt1;++i)s+=t[t[tmp[1][i]].ls].v;
for(int i=1;i<=cnt0;++i)s-=t[t[tmp[0][i]].ls].v;
if(k<=s)
{
for(int i=1;i<=cnt1;++i)tmp[1][i]=t[tmp[1][i]].ls;
for(int i=1;i<=cnt0;++i)tmp[0][i]=t[tmp[0][i]].ls;
return Query(l,mid,k);
}
else
{
for(int i=1;i<=cnt1;++i)tmp[1][i]=t[tmp[1][i]].rs;
for(int i=1;i<=cnt0;++i)tmp[0][i]=t[tmp[0][i]].rs;
return Query(mid+1,r,k-s);
}
}
int PreQuery(int l,int r,int k)
{
cnt0=cnt1=0;l--;
while(r)tmp[1][++cnt1]=rt[r],r-=lowbit(r);
while(l)tmp[0][++cnt0]=rt[l],l-=lowbit(l);
return Query(1,sum,k);
}
char opt[3];
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)S[++sum]=a[i]=read();
for(int i=1;i<=m;++i)
{
scanf("%s",opt);
q[i].opt=opt[0]=='Q';
if(q[i].opt)q[i].l=read(),q[i].r=read(),q[i].k=read();
else q[i].pos=read(),q[i].t=S[++sum]=read();
}
sort(&S[1],&S[sum+1]);
sum=unique(&S[1],&S[sum+1])-S-1;
for(int i=1;i<=n;++i)PreModify(i,1);
for(int i=1;i<=m;++i)
{
if(q[i].opt)
{
printf("%d\n",S[PreQuery(Q[i].l,Q[i].r,Q[i].k)]);
}
else
{
PreModify(Q[i].pos,-1);
a[Q[i].pos]=Q[i].t;
PreModify(Q[i].pos,1);
}
}
return 0;
}
上一篇:【HDOJ图论题集】【转】


下一篇:【LeetCode】862. Shortest Subarray with Sum at Least K 解题报告(C++)