带修改的主席树和BZOJ 1901

tonyfang posted @ 2015年8月17日 22:07 in Algorithm with tags c++ Algorithm , 763 阅读

主席树其实就是维护$[1,i]$的前缀权值线段树。那么修改一个地方的值$j$,会影响$[1,j]$到$[1,n]$的所有的前缀和,数量级是$O(n)$的,加上维护主席树的$O(log_n)$,就是$O(nlog_n)$,明显不符合复杂度,但是查询却是$O(1)$的,所以无修改的区间第k大用主席树(前缀)就够啦

对于维护前缀和的东西,一般用树状数组维护起来就能有一个比较漂亮的复杂度了!

那么用树状数组维护这$n$个线段树,每次修改和查询的复杂度都为$O(log^{2}_{n})$,这样$m$次操作的复杂度就为$O(mlog^{2}_{n})$,就够啦!

题目:BZOJ1901 ZJU2112

bzoj需要权限啊TAT

$zju$内存卡这么紧TAT

update: 2015/08/25:Bzoj通过

Accepted 35032 kb 696 ms

但是空间$35032kb$好像在$zju$的限制内啊= =

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
const int Maxn=100010;
struct segtree {
	int l,r,w;
	segtree() {l=r=w=0;}
}T[21*Maxn];
# define lc(a) T[(a)].l
# define rc(a) T[(a)].r
# define w(a) T[(a)].w
int a[Maxn],t[Maxn*2],tn=0,root[Maxn],P[Maxn],Q[Maxn],K[Maxn];
int n,m;
int size;
char op[Maxn][4];
inline int lb(int x) {return x&(-x);}
void build(int &roots,int l,int r) {
	roots=++size;
	w(roots)=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(lc(roots),l,mid);
	build(rc(roots),mid+1,r);
}
void insert(int last,int l,int r,int &roots,int x,int p) {
	roots=++size;
	lc(roots)=lc(last),rc(roots)=rc(last);w(roots)=w(last)+x;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) insert(lc(last),l,mid,lc(roots),x,p);
	else insert(rc(last),mid+1,r,rc(roots),x,p);
}
inline void bitinsert(int x,int num,int del) {
	for (;x<=n;x+=lb(x)) insert(root[x],1,tn,root[x],del,num);
}
int N,M,L[Maxn],R[Maxn];
int query(int l,int r,int k) {
	if(l==r) return l;
	int mid=(l+r)>>1;
	int suma,sumb;
	suma=sumb=0;
	for (int i=1;i<=N;++i) suma+=w(lc(L[i]));
	for (int i=1;i<=M;++i) sumb+=w(lc(R[i]));
	int delta=sumb-suma;
	if(k<=delta) {
		for (int i=1;i<=N;++i) L[i]=lc(L[i]);
		for (int i=1;i<=M;++i) R[i]=lc(R[i]);
		return query(l,mid,k);
	} else {
		for (int i=1;i<=N;++i) L[i]=rc(L[i]);
		for (int i=1;i<=M;++i) R[i]=rc(R[i]);
		return query(mid+1,r,k-delta);	
	}
}
inline int ask(int l,int r,int k) {
	M=N=0;
	for(;l>0;l-=lb(l)) L[++N]=root[l];
	for(;r>0;r-=lb(r)) R[++M]=root[r];
	return query(1,tn,k);
}
int main() {
	int Case;
	scanf("%d",&Case);
	while(Case--) {
		scanf("%d%d",&n,&m);
		size=0;root[0]=0;tn=0;
		memset(t,0,sizeof(t));
		memset(a,0,sizeof(a));
		memset(root,0,sizeof(root));
		for (int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			t[++tn]=a[i];
		}
		for (int i=1;i<=m;++i) {
			scanf("%s%d%d",op[i],&P[i],&Q[i]);
			if(op[i][0]=='Q') scanf("%d",&K[i]);
			else t[++tn]=Q[i];
		}
		sort(t+1,t+tn+1);
		tn=unique(t+1,t+tn+1)-t-1;
		for (int i=1;i<=n;++i) a[i]=lower_bound(t+1,t+1+tn,a[i])-t;
		build(root[0],1,tn);
		for (int i=1;i<=n;++i) bitinsert(i,a[i],1);
		for (int i=1;i<=m;++i) {
			if(op[i][0]=='Q') {
				printf("%d\n",t[ask(P[i]-1,Q[i],K[i])]);
			} else {
				int pos=lower_bound(t,t+tn+1,Q[i])-t;
				bitinsert(P[i],a[P[i]],-1);
				a[P[i]]=pos;
				bitinsert(P[i],a[P[i]],1);
			}
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter