【纪中集训2019.3.25】芬威克树

题目

描述

​ 第一段代码正确第用(k)进制(BIT)维护了前缀和;

​ 第二段代码由于写错了(line 4),所以意义发生了改变;

​ 维护第二段代码执行(ADD(x,v))(QUERY(x))的答案;

范围

​ $1 le n le 10^9 , 1 le q le 2 imes 10^5 , 2 le k le 10^5 $ ;

题解

  • 首先不管如何变化,这都是一个树形结构;

  • 但是由于(n)较大,所以无法直接支持维护树链;

  • (k = t imes 2 ^ p (t \% 2=1)) ;

  • 对于(v = x 2^y (x \% 2=1))

    • 1.当(y ge p)时,执行ADD时(v)的最低位是不会改变的,同时由于(x)(t)的意义下有逆元,所以(v)至多有一个满足$yge p $的儿子,即这些节点形成了很多条链;
    • 2.当(y<p)时,执行一次加最低位值会让(y++),注意有可能最低位变化然后重新来过,但是最多有(log_k n)次,即这些点最多向上$log_k n imes p = log_{k} n log_2 k = log_2 n $ 次就会到1中的链上去;
  • 可以暴力(HASH)维护(2),离散后用(BIT)维护(1) ;

  • 只需要找到(1)中的链的叶子,注意在链上每次的进位是确定的,为对最低位的高一位进1;

  • 链叶子满足(x)处于最低位,同时无法退位,所以形如:$ (2x+1) 2^p k^y , (y ge 0 , 0 le x lt frac{frac{t}{2^p}-1}{2}) $即可;

  • 可以(klog k)倍增方便地找到这些位置;

  • 时间复杂度应该是:$k log_2 k + q (log_2 n + log_2 q +loq_2 k ) $ ; ?(似乎和出题人分析的有点不太一样。。。)

  • orz 租酥雨

    #include<bits/stdc++.h>
    #define pb push_back
    #define mk make_pair
    #define fi first
    #define se second
    #define ull unsigned long long 
    #define il inline 
    #define rg register 
    using namespace std;
    const int N=200010,M=31;
    int n,m,k,MX,A,B,S,cnt,id;
    struct data{int op,x,y;}Q[N];
    int f[N][M],bin[M];
    pair<int,int>v1[N];
    //map<int,int>mp1;//,mp2;
    vector<int>vec[N],val[N],v2[N];
    ull pw[100];
    il char gc(){
    	static char*p1,*p2,s[1000000];
    	if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
    	return(p1==p2)?EOF:*p1++;
    }
    il int rd(){
    	int x=0;char c=gc();
    	while(c<'0'||c>'9')c=gc();
    	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
    	return x;
    }
    const int sz=123451;
    struct Hash{
    	int o,hd[sz],nt[N*M],v[N*M],w[N*M];
    	int& operator [](const int&x){
    		int y=x%sz;
    		for(rg int i=hd[y];i;i=nt[i]){
    			if(v[i]==x)return w[i];
    		}
    		nt[++o]=hd[y],hd[y]=o,v[o]=x,w[o]=0;
    		return w[o];
    	}
    }mp1,mp2;
    il void init(){
    	int iv2=A+1>>1;
    	for(rg int i=1;i<A;++i){
    		if(i&1)f[i][0]=(ull)i*iv2%A;
    		else f[i][0]=f[i>>1][0];
    		while((f[i][0]&1)==0)f[i][0]>>=1;
    	}
    	for(rg int i=1;i<MX;++i)
    	for(rg int j=0;j<A;++j)f[j][i]=f[f[j][i-1]][i-1];
    }
    il int get(int x,int y){
    	int t=x/k;x%=k;x>>=B;
    	while(x&&((x&1)==0))x>>=1; 
    	for(rg int i=0;i<MX;++i)if(bin[i]&t)t^=bin[i],x=f[x][i];
    	x<<=B;x*=pw[y];
    	if(!mp1[x])return mp1[x]=++id;
    	return mp1[x];
    }
    il int inc(int&x,int&y,int c){while(x%c==0&&(x/=c))y++;}
    il void add(int x,int y,int z){for(;y<=vec[x].size();y+=y&-y)val[x][y]^=z;}
    il int ask(int x,int y){
    	int re=0;
    	for(;y;y-=y&-y)
    	re^=val[x][y];
    	return re;
    }
    il void upd(int x,int y,int z){
    	y=lower_bound(vec[x].begin(),vec[x].end(),y)-vec[x].begin()+1;
    	add(x,y,z);
    }
    il int que(int x,int y){
    	if(vec[x].begin()==vec[x].end())return 0;
    	y=lower_bound(vec[x].begin(),vec[x].end(),y+1)-vec[x].begin();
    	return ask(x,y);
    }
    char ps[1000000],*pp=ps;
    void flush(){fwrite(ps,1,pp-ps,stdout);}
    void push(char x){
    	if(pp==ps+1000000)fwrite(ps,1,1000000,stdout),pp=ps;
    	*pp++=x;
    }
    void write(int x){
    	static int sta[N],top;
    	if(!x){push('0');push('
    ');return;}
    	while(x)sta[++top]=x%10,x/=10;
    	while(top)push(sta[top--]^'0');
    	push('
    ');
    }
    int main(){
    	freopen("fenwick.in","r",stdin);
    	freopen("fenwick.out","w",stdout);
    	n=rd();m=rd();k=rd();
    	for(rg int i=bin[0]=pw[0]=1;i<=30;++i){
    		bin[i]=bin[i-1]<<1;
    		pw[i]=pw[i-1]*k;
    	}
    	inc(A=k,B=0,2);S=(1<<B)-1;
    	MX=log2(n)+1;init();
    	for(rg int i=1,op,t,p;i<=m;++i){
    		Q[i].op=op=rd();
    		if(op&1){
    			Q[i].x=rd(),Q[i].y=rd();
    			inc(p=Q[i].x,t=0,k);
    			while((p%k&S) && (ull)p*pw[t]<=n){
    				v2[i].pb(p*pw[t]);
    				inc(p+=p%k,t,k);
    			}
    			if((ull)p*pw[t]<=n)vec[v1[i].fi=get(p,t)].pb(v1[i].se=p*pw[t]);
    		}else Q[i].x=rd();
    	}
    	for(rg int i=1;i<=id;++i){
    		sort(vec[i].begin(),vec[i].end());
    		unique(vec[i].begin(),vec[i].end());
    		for(int j=0;j<vec[i].size();++j)val[i].pb(0);val[i].pb(0);
    	}
    	for(rg int i=1,x,p,t;i<=m;++i){
    		if(Q[i].op&1){
    			for(int j=0;j<v2[i].size();++j)mp2[v2[i][j]]^=Q[i].y;
    			if(v1[i].fi)upd(v1[i].fi,v1[i].se,Q[i].y);
    		}else{
    			int ans=0;inc(p=Q[i].x,t=0,k);
    			while(p){
    				if((p%k&S)==0)ans^=que(get(p,t),p*pw[t]);
    				else ans^=mp2[p*pw[t]];
    				inc(p-=p%k,t,k);
    			}
    		//	printf("%d
    ",ans);	
    			write(ans);
    		}
    	}
    	flush();
    	return 0;
    }
    
原文地址:https://www.cnblogs.com/Paul-Guderian/p/10638687.html