当前位置:网站首页>P2617 Dynamic Rankings(PST套BIT)

P2617 Dynamic Rankings(PST套BIT)

2021-08-10 08:43:32 wx6110fa547fd20

P2617 Dynamic Rankings(PST套BIT)

题意

单点修改+区间第k小


思路

主席树套BIT,这里与求区间第 k k k小的upd和query方式有点不同,利用 B I T BIT BIT快速求前缀和,每次更新,修改 l o g n logn logn棵树,每次查询,也是 l o g n logn logn棵树。这里是动态开点建树,不是在前一个版本的上建树,所以每次upd都是只依据 r t i rt_i rti这个版本,进行动态开点。

时间复杂度: O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

空间复杂度: O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

所以空间要开到 N × 400 N\times 400 N×400最好。

code


// Problem: P2617 Dynamic Rankings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2617
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Date: 2021-03-10 10:40:38
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+5,M=200*N,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
#define lowbit(x) x&(-x)
int n,m,tot;
int a[N],rt[N],b[N<<1];
struct PST{//President Tree
	int lx[M],rx[M],s[M],cnt;
	int js[2],num[2][25];
	void upd(int &x,int l,int r,int p,int v){	//更新 
		//printf("x=%d\n",x);
		if(!x) x=++cnt;
		s[x]+=v;
		if(l==r){return;}
		int mid=(l+r)>>1;
		if(p<=mid) upd(lx[x],l,mid,p,v);
		else upd(rx[x],mid+1,r,p,v);
	}
	void updt(int p,int v){
		int k=lower_bound(b+1,b+tot+1,a[p])-b;
		for(int i=p;i<=n;i+=lowbit(i)) upd(rt[i],1,tot,k,v);
	}
	int query(int l,int r,int k){
		if(l==r) return l;
		int sum=0,mid=l+r>>1;
		for(int i=1;i<=js[1];i++) sum+=s[lx[num[1][i]]];
		for(int i=1;i<=js[0];i++) sum-=s[lx[num[0][i]]];
		if(k<=sum){
			for(int i=1;i<=js[1];i++) num[1][i]=lx[num[1][i]];
			for(int i=1;i<=js[0];i++) num[0][i]=lx[num[0][i]];
			return query(l,mid,k);
		}else {
			for(int i=1;i<=js[1];i++) num[1][i]=rx[num[1][i]];
			for(int i=1;i<=js[0];i++) num[0][i]=rx[num[0][i]];
			return query(mid+1,r,k-sum);
		}
	}
	int quet(int l,int r,int k){
		mst(num,0);js[0]=js[1]=0;
		for(int i=r;i;i-=lowbit(i)) num[1][++js[1]]=rt[i];
		for(int i=l-1;i;i-=lowbit(i)) num[0][++js[0]]=rt[i];
		return query(1,tot,k); 
	}
	
}T;
struct Query{
	bool op;
	int l,r,k;
	int p,v;
}q[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[++tot]=a[i];
	for(int i=1;i<=m;i++){
		char op;scanf("\n%c",&op);
		if(op=='Q')
			q[i].op=true,scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
		else scanf("%d%d",&q[i].p,&q[i].v),b[++tot]=q[i].v;
	}
	sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
	for(int i=1;i<=n;i++) T.updt(i,1);
	for(int i=1;i<=m;i++){
		if(q[i].op) printf("%d\n",b[T.quet(q[i].l,q[i].r,q[i].k)]);
		else {
			T.updt(q[i].p,-1);
			a[q[i].p]=q[i].v;
			T.updt(q[i].p,1);
		}
	}
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328406

随机推荐