DZY 's BLOG

跟随大神们的脚步进军CF！希望能坚持。。。

太弱了。。挖坑。。

要求维护一个数据结构，支持：

（1）一开始有n个集合，每个集合内一个元素

（2）合并两个集合

（3）询问一个集合内元素的最小值，并删除

神结论。

先找出基环。

求树上路径第k大。

主席树。从根往孩子建。查询(x,y)路径时，在第x棵主席树+第y棵主席树-两倍的第lca(x,y)棵主席树上查询即可。还要特判一下lca(x,y)这个节点。

我写的速度慢出翔。QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010,maxm=500010,maxt=4000100;
int p[maxm],n1[maxm],h[maxn],T[maxn],lc[maxt],rc[maxt],s[maxt],a[maxn],bin[maxn];
int val[maxn],anc[maxn][20],dep[maxn],LcaVal,tot=0,ee=0,n,m,q[maxn],vis[maxn]={0};
char buf[8000000],*pt=buf,*o=buf;
inline int getint(){
    int s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}inline void print(int x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;};
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}void build(int l,int r,int &x){
	s[x=++tot]=0;
	if(l==r)	return;
	int mid=l+r>>1;
	build(l,mid,lc[x]);
	build(mid+1,r,rc[x]);
}void modify(int p,int v,int l,int r,int &x){
	s[x=++tot]=s[p]+1;
	lc[x]=lc[p];
	rc[x]=rc[p];
	if(l==r)	return;
	int mid=l+r>>1;
	if(v<=mid)	modify(lc[p],v,l,mid,lc[x]);
	else		modify(rc[p],v,mid+1,r,rc[x]);
}int ask(int a,int b,int c,int l,int r,int k){
	if(l==r)	return l;
	int cnt=s[lc[a]]+s[lc[b]]-(s[lc[c]]<<1),mid=l+r>>1;
	if(LcaVal>=l && LcaVal<=(l+r>>1))	cnt++;
	if(k<=cnt)	return ask(lc[a],lc[b],lc[c],l,mid,k);
	else		return ask(rc[a],rc[b],rc[c],mid+1,r,k-cnt);
}int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		k>>=1,j++;
	}if(u==v)	return u;
	for(int i=16;~i;i--)
		if(anc[u][i]!=anc[v][i])	u=anc[u][i],v=anc[v][i];
	return anc[u][0];
}int main(){
	fread(buf,1,8000000,stdin);
	n=getint();	m=getint();
	for(int i=1;i<=n;i++)	bin[i]=a[i]=getint();
	memset(h,-1,sizeof(h));
	int x,y;
	for(int i=1;i<n;i++)	ae(getint(),getint());
	sort(bin+1,bin+n+1);
	for(int i=1;i<=n;i++)	a[i]=lower_bound(bin+1,bin+n+1,a[i])-bin;
	build(1,n,T[0]);
	int head=0,tail=1;
	q[0]=vis[1]=dep[1]=1;
	modify(T[0],a[1],1,n,T[1]);
	while(head<tail){
		int u=q[head++];
		for(int i=h[u];~i;i=n1[i]){
			if(!vis[p[i]]){
				modify(T[u],a[p[i]],1,n,T[p[i]]);
				vis[p[i]]=1;
				dep[p[i]]=dep[u]+1;
				anc[p[i]][0]=u;
				q[tail++]=p[i];
			}
		}
	}for(int j=1;j<=16;j++)	
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int la=0,z,k;
	while(m--){
		x=getint();	y=getint();	k=getint();
		z=lca(x,y);
		LcaVal=a[z];
		if(x==y)	print(bin[a[x]]);
		else	print(bin[ask(T[x],T[y],T[z],1,n,k)]);
		if(m)	*o++='\n';
	}return fwrite(buf,1,o-buf,stdout),0;
}

树上的Nim取石子游戏。

说白了就是，维护一棵树，支持：修改点权，询问一条路径上点权的xor值是否为零。

可以用树链剖分做。但是介于n和q都50w这么大感觉常数很DT。。

既然它只修改点的话，影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。

先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零，然后再修改。

(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。

没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define YES *o++='Y',*o++='e',*o++='s',*o++='\n'
#define NO *o++='N',*o++='o',*o++='\n'
const int maxn=500100,maxm=1000100;
int p[maxm],n1[maxm],h[maxn],begin[maxn],end[maxn],bit[maxm],st[maxn],a[maxn],n,ee=0,tot=0;
int anc[maxn][20],dep[maxn];	char buf[25000000],*o=buf,*pt=buf;
inline int getint(){
    int s=0;	while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; 
	return s;
}inline char getop(){
	while(*pt!='Q'&&*pt!='C')	pt++;	return *pt++;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}inline void dfs(int s){
	int top=0;
	begin[st[++top]=s]=dep[s]=++tot;
	while(top){
		int u=st[top],f=0;
		for(int i=h[u];~i;i=n1[i]){
			if(!~begin[p[i]]){
				begin[p[i]]=++tot;
				anc[p[i]][0]=u;
				dep[p[i]]=dep[u]+1;
				st[++top]=p[i];
				h[u]=n1[i];
				f=1;
				break;
			}
		}if(!f){
			end[u]=++tot;
			top--;
		}
	}
}inline int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		j++,k>>=1;
	}if(u==v)	return u;
	for(int j=19;~j;j--)
		if(anc[u][j]!=anc[v][j])	u=anc[u][j],v=anc[v][j];
	return anc[u][0];
}inline void modify(int i){
	for(int x=begin[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
	for(int x=end[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
}inline int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r^=bit[x];
	return r;
}int main(){
	fread(buf,1,25000000,stdin);
	n=getint();
	for(int i=1;i<=n;i++)	a[i]=getint();
	memset(h,-1,sizeof(h));
	memset(begin,-1,sizeof(begin));
	for(int i=1;i<n;i++)	ae(getint(),getint());
	dfs(1);
	for(int i=1;i<=n;i++)	modify(i);
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int q=getint(),x,y,z;
	while(q--){
		if(getop()=='Q'){
			x=getint();y=getint();
			if(ask(begin[x])^ask(begin[y])^a[lca(x,y)])	YES;
			else	NO;
		}else{
			x=getint();y=getint();
			modify(x);
			a[x]=y;
			modify(x);
		}
	}return fwrite(buf,1,o-buf,stdout),0;
}

求一个数表示为几个Fib[]之和的方案数。n<=10^18。

首先发现fib增长的很快。到了89就爆long long了。那么总共就88个数可用。

然后可以利用贪心从大到小得到一种方案。比如25。先从大的fib数开始取。所以25=f[7]+f[3]+f[1]=21+3+1。

用二进制来表示选中的fib数就是：1010001（从小到大）

注意到：因为fib[i]=fib[i-1]+fib[i-2]。所以001和110是等价的。那么我们就可以从第一个推到最后一个每一位可以取1也可以不取1。

如果不取1。那就有cnt/2种取法（cnt为这个1和前面一个1中间的0的个数）。然后乘法原理就行了。

dp的时候只需要枚举1的位置即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[89],a[89],n,g[89][2];	int m=0;
int main(){
	cin >> n;
	f[1]=1;	f[2]=2;
	for(int i=3;i<=88;i++)	f[i]=f[i-1]+f[i-2];
	for(int i=88;i>=1;i--)	if(f[i]<=n)	n-=f[i],a[++m]=1LL*i;
	reverse(a+1,a+m+1);
	g[1][1]=1;
	g[1][0]=(a[1]-1)>>1;
	for(int i=2;i<=m;i++){
		g[i][1]=g[i-1][0]+g[i-1][1];
		g[i][0]=((a[i]-a[i-1]-1)>>1)*g[i-1][1]+((a[i]-a[i-1])>>1)*g[i-1][0];
	}cout << g[m][1]+g[m][0] << endl;
	return 0;
}

构造一个n×n的矩阵A。其中A[i][j]=gcd(i,j)。求A的行列式。n<=200w。

一看就不能暴力嘛。

暴力一下求了几个值放到OEIS上查。

结果惊呆了。

然后欧拉筛出phi。然后就行了。

（求大神告诉我这是为什么）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int flag[2000010],n,m,cnt=0;
long long prime[500000],phi[2000010],maxn=0,an[500010];
char buf[5000000],*o=buf,*pt=buf;
inline long long getint(){
    long long s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}inline void print(long long x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}*o++='\n';
}int main(){
	fread(buf,1,5000000,stdin);
	n=getint();	for(long long i=1;i<=n;i++)	an[i]=getint(),maxn=(an[i]>maxn)?an[i]:maxn; 
	memset(flag,0,sizeof(flag));
	for(int i=2;i<=maxn;i++){
		if(!flag[i])	prime[cnt++]=i,phi[i]=i-1;
		for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){
			flag[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else	phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}phi[1]=1;
	for(int i=2;i<=maxn;i++)	phi[i]=phi[i-1]*phi[i]%1000003;
	for(int i=1;i<=n;i++)	print(phi[an[i]]);
	return fwrite(buf,1,o-buf,stdout),0;
}