DZY 's BLOG

好久没炖题了。。上一次愉快的没有全部AC。。果然一定要先用小号交一遍才保险。。（目测进度会很慢。。

[UPD 4.11]赛程过半

[UPD 4.16]完结撒花！

[UPD 4.17]终于成功地在不手贱的情况下交完了！~

现在几题了？

50/50

因为有些逗，所以打算水一些这样的题目。囧rz。

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

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

（2）合并两个集合

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

树上的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;
}

如果没有鳄鱼的话。就是求邻接矩阵的k次幂了。

有鳄鱼的话。比如在第i个时刻第j个点上有鳄鱼。那么把第i-1时刻的矩阵中[1..n][j]置零，第i时刻的矩阵中[j][1..n]置零。很好想通。

注意到T=2、3、4。lcm是12。那么整个周期就是12。K/12的用快速幂。K%12的暴力求。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,s,e,k,nf,fb[52][52]={0},p[52];
struct mtx{
	int num[52][52];
	mtx(){	memset(num,0,sizeof(num));}
}M[12],org;
mtx mul(mtx a,mtx b){
	mtx c;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%10000;
	return c;
}mtx pow(mtx a,int b){
	mtx c;
	for(int i=0;i<n;i++)	c.num[i][i]=1;
	while(b){
		if(b&1)	c=mul(c,a);
		b>>=1;
		a=mul(a,a);
	}return c;
}inline void clear1(int x,int y){
	for(int i=0;i<n;i++)	M[x].num[y][i]=0;
}inline void clear2(int x,int y){
	for(int i=0;i<n;i++)	M[x].num[i][y]=0;
}int main(){
	scanf("%d%d%d%d%d",&n,&m,&s,&e,&k);
	int x,y,t;
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		for(int j=0;j<12;j++)	M[j].num[x][y]=M[j].num[y][x]=1;
	}scanf("%d",&nf);
	for(int i=0;i<nf;i++){
		scanf("%d",&t);
		for(int j=0;j<t;j++)	scanf("%d",&p[j]);
		for(int j=0;j<12;j++)	fb[j][p[j%t]]=1;
	}for(int j=0;j<12;j++)
		for(int i=0;i<n;i++)	if(fb[j][i])	clear1(j,i),clear2((j+11)%12,i);
	for(int i=1;i<12;i++)	M[i]=mul(M[i-1],M[i]);
	if(k%12)	cout << mul(pow(M[11],k/12),M[k%12-1]).num[s][e] << endl;
	else		cout << pow(M[11],k/12).num[s][e] << endl;
	return 0;
}

泥煤怎么会全WA呢。

回来再调。

备忘一下。

题意：给定一个序列，每次询问左端点在[a,b]中，右端点在[c,d]中的子序列中，最大的中位数。强制在线。

前几天做到与这道题有一点点类似的。那道题是给定一个序列，求多少个子序列的中位数大于等于给定值M。

这两道题中的中位数的定义都是一样的。设序列S从大到小排序后为S[1..k]，中位数为M=S[k/2向上取整]。

那就意味着，在序列S中，大于等于M的数大于等于k/2。如果把序列S转化为T，T[i]=1(S[i]>=M),-1(S[i]<M)，则ΣT[i]一定非负。

同理，如果对于任意一个M。将序列S转化为T之后，如果ΣT[i]非负。那么这个序列的中位数一定大于等于M。

回到这道题。我们可以先考虑一个弱版：只询问一次。

有了上面那道题的经验。对于M<M'，如果发现中位数大于等于M'，那一定也大于等于M。所以有单调性，很容易就想到了二分。二分M。得到T[]。因为要求了左端点和右端点。所以，如果能在满足要求的情况下找到这一段ΣT[i..j]（i∈[a,b]，j∈[c,d]）非负，那么中位数一定就大于等于M了。所以，我们只需要求出符合要求的最大子序列和，看是不是非负即可。

感觉回到了GSS。线段树维护lmax,rmax,sum即可。因为有a<b<c<d，所以[a,b],[c,d]是互不包含的。最大连续子序列和就是[a,b]的rmax+(b,c)的sum+[c,d]的lmax。

另外n个数都是要离散化的这是必然的。二分的时候二分下标。

现在感觉已经很明了了。这样的话。二分logn。重建序列T和线段树nlogn。总复杂度是O(nlog^2n)。可以很好的解决一次询问。= =

多个询问怎么办。O(nqlog^2n)作死？其实瓶颈在这：为什么每次都要重建线段树？根本就不需要。

假设离散化的时候数值是从小到大排序的。那我们可以这么想，二分到M时，排序后的下标第1~M-1位上都是-1。第M~n位上都是1。然后还是跟上面一样的方法判定。

这就要用到函数式编程的思想。在原来的基础上不做修改，继续建树，也就是函数式线段树。

具体来说：初始的树，每个位置都是1。序列从小到大插入主席树时，修改第i棵树的时候，第i-1大的数的位置上改为-1。这样以此类推，就有n棵不同版本的线段树。

二分到M时，就在第M棵线段树上查询。可以保证此时下标为1~M-1的位置上的数都是-1。其余位置上都是1。这样就可以进行查询了。

这样就没问题了。二分logn。建函数式线段树nlogn。查询一次logn。总复杂度(nlogn+qlog^2n)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	int sum,lmax,rmax;
	node(){};
	node(int s,int l,int r):sum(s),lmax(l),rmax(r){}; 
}seg[5000000],z;
int lc[5000000],rc[5000000],T[30000],q[4],ans=0,tot=0,n,Q;
pair<int,int>a[30000];
char buf[4000000],*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;}*o++='\n';
}
inline node operator + (const node &a,const node &b){
	return node(a.sum+b.sum,max(a.lmax,a.sum+b.lmax),max(b.rmax,b.sum+a.rmax));
}void build(int l,int r,int &rt){
	rt=++tot;
	if(l==r){	seg[rt]=node(1,1,1);	return;}
	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}void modify(int p,int k,int v,int l,int r,int &rt){
	rt=++tot;
	lc[rt]=lc[p];	rc[rt]=rc[p];
	if(l==r){	seg[rt]=node(v,v,v);	return;}
	int m=l+r>>1;
	if(k<=m)	modify(lc[p],k,v,l,m,lc[rt]);
	else		modify(rc[p],k,v,m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}node ask(int L,int R,int l,int r,int rt){
	if(L>R)	return node(0,0,0); 
	if(L==l&&r==R)	return seg[rt];
	int m=l+r>>1;
	if(R<=m)	return ask(L,R,l,m,lc[rt]);
	else if(L>m)	return ask(L,R,m+1,r,rc[rt]);
	else	return ask(L,m,l,m,lc[rt])+ask(m+1,R,m+1,r,rc[rt]);
}inline int check(int k){
	return ask(q[0],q[1],0,n-1,T[k]).rmax+ask(q[1]+1,q[2]-1,0,n-1,T[k]).sum+ask(q[2],q[3],0,n-1,T[k]).lmax>=0;
}int main(){
	fread(buf,1,4000000,stdin);	n=getint();
	for(int i=0;i<n;i++)	a[a[i].second=i].first=getint();
	sort(a,a+n);			build(0,n-1,T[0]);
	for(int i=1;i<n;i++)	modify(T[i-1],a[i-1].second,-1,0,n-1,T[i]);
	Q=getint();
	while(Q--){
		q[0]=(getint()+ans)%n;	q[1]=(getint()+ans)%n;	q[2]=(getint()+ans)%n;	q[3]=(getint()+ans)%n;
		sort(q,q+4);
		int l=0,r=n-1,mid;
		while(l<=r)	if(check(mid=l+r>>1))	l=mid+1;	else	r=mid-1;
		print(ans=a[l-1].first);
	}return fwrite(buf,1,o-buf,stdout),0;
}

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

很容易的想到如果是割点塌掉的情况。

如果这个割点把整张图分裂了，那么就要保证每块里面都要装一个救援出口。

所以可以 这样做，先求出割点。然后dfs剩下的块。如果一个块只连接到了一个割点，那么这个块里面要有一个救援出口。否则就不用了。

如果没割点的话，要两个出口。不然有可能出口塌了= =。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[50010],n1[50010],h[10010],v[10010],dfn[10010],low[10010],b[10010];
int s[50010],c[50010],tmp[50010],m,n,ee,tot,col;long long An1,An2;
void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
}void dfs(int u){
	v[u]=1;dfn[u]=low[u]=++tot;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		dfs(p[i]);
		low[u]=min(low[u],low[p[i]]);
		if(low[p[i]]>=dfn[u])	b[u]++;
	}else	low[u]=min(low[u],dfn[p[i]]);
}void dfs2(int u){
	v[u]=1,s[col]++;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		if(!b[p[i]])	dfs2(p[i]);
		else	if(c[p[i]]!=col)	c[p[i]]=col,tmp[col]++;
	}
}void init(){
	memset(h,-1,sizeof(h));
	memset(v,0,sizeof(v));
	memset(b,0,sizeof(b));
	memset(v,0,sizeof(v));
	memset(c,0,sizeof(c));
	memset(s,0,sizeof(s));
	memset(tmp,0,sizeof(tmp));
	n=ee=tot=col=An1=0;An2=1;
}int main(){
	int tc=0;
	while(scanf("%d",&m),m){
		int x,y;init();
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			ae(x,y);ae(y,x);
			n=max(n,max(x,y));
		}for(int i=1;i<=n;i++)	if(!v[i]){
			dfs(i);b[i]--;
		}memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++)	if(!v[i]&&!b[i]){
			col++;dfs2(i);
			if(tmp[col]==1)	An1++,An2*=1ll*s[col];
		}if(col==1)	An1=2,An2=1ll*n*(n-1)>>1;
		printf("Case %d: %lld %lld\n",++tc,An1,An2);
	}return 0;
}