CF558E A Simple Task

开一颗珂朵莉树,对于每个新的查询,先把l-1,l之间和r,r+1之间split开,然后对于剩下的部份用桶排序并暴力合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
const int N=100005;

struct Data{
	int l;int r;char id;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
	int l=it->l,r=it->r;char id=it->id;
	if(X<l||X>=r){
		return;
	}
	st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
	for(int i=0;i<26;++i){
		bckt[i]=0;
	}
}
inline void uni(int l,int r,int op){
	std::set<Data>::iterator itx,ity;
	itx=st.lower_bound((Data){0,l-1,0});
	split(itx,l-1);
	ity=st.lower_bound((Data){0,r,0});
	split(ity,r);
	itx=st.lower_bound((Data){0,l,0});
	ity=st.lower_bound((Data){0,r,0});
	++ity;
	for(std::set<Data>::iterator it=itx;it!=ity;++it){
		bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
	}
	st.erase(itx,ity);
	int loc,nl=l;
	for(int i=0;i<26;++i){
		loc=op?i:(26-i-1);
		if(bckt[loc]<=0){
			continue;
		}
		st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
		nl+=bckt[loc];
	}
	clr();
}
inline void prnt(){
	for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
		for(int j=it->l;j<=it->r;++j){
			putchar(it->id);
		}
	}
	puts("");
}
inline void init(){
	scanf("%d%d",&n,&q);
	std::cin>>ch+1;
	for(int i=1;i<=n;++i){
		st.insert((Data){i,i,ch[i]});
	}
	int l,r,op;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&l,&r,&op);
		uni(l,r,op);
//		prnt();
	}
	prnt();
}

int main(){
	init();
	return 0;
}

CF527C Glass Carving

开四个set,分别存切割的刀以及每个区间段,然后每次各自从行和列取最长的区间段,乘一起即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;


ll w,h;
std::set<ll> st[2];
std::multiset<ll> sm[2];
std::multiset<ll>::iterator it;

inline void init(){
	char ch[5];ll x,l,r;int id;
	std::cin>>ch+1;scanf("%lld",&x);
	id=(ch[1]=='H');
	set<ll> &nst=st[id];
	multiset<ll> &nsm=sm[id];
	nst.insert(x);
	it=nst.find(x);
	--it;l=*it;
	++it,++it;r=*it;
	it=nsm.find(r-l);
	nsm.erase(it);nsm.insert(r-x);nsm.insert(x-l);
	it=sm[0].end();--it;l=*it;
	it=sm[1].end();--it;r=*it;
	printf("%lld\n",l*r);
}

int main(){
	scanf("%lld%lld",&w,&h);
	int T;
	scanf("%d",&T);
	st[0].insert(0),st[0].insert(w);
	st[1].insert(0),st[1].insert(h);
	sm[0].insert(w),sm[1].insert(h);
	while(T--){
		init();
	}
	return 0;
}

lp3902 递增

最长上升子序列裸题。
dp+二分即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

int main(){
	init();
	return 0;
}

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询,那就可以考虑差分。
我们考虑将数列差分,维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D},就变成了三个操作:
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

int main(){
	init();
	return 0;
}

lp2757 [国家集训队]等差子序列

因为只要求存在性,故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ,于是用两个 bitset 分别维护前缀桶和后缀桶,稍微左右移一下求交即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
/*

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。

题目的题意就是,求 n 个点的点、边均有标号的生成树个数。

n 个点的无根有标号生成树个数,根据某个叫做 Cayley 的古老定理, 值是:

当然,由于边有标号,所以这里的值还要乘上一个​。

问题是 Cayley 定理要如何证明。

一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造,我们发现,有且仅有 ​ 种不同的方法来构造一棵有标号无根树。

这个序列是如何构造的呢?

我们考虑递归地构造这个序列。对于当前的树,我们选其中的编号最小的叶子节点,将它的相邻点——显然是唯一的——加入序列,然后删掉这个叶子节点。

这样,我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。

由此我们可以构造出这个序列。

通过 Prufer 序列,我们无损地将一棵有标号无根树的信息压缩成了一个序列。

那么要怎么把 Prufer 序列还原为一棵有标号无根树呢?我们有一种系统的方法。

首先选择一个数,这个数既不在已有的树中,也不在当前的序列中,并且它最小。那么,我们就可以确定,这个数便是我们当前要处理的叶子节点。

然后,我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。

是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢?

假设我们当前正在处理第 i 个节点,序列中剩下 k 种数,那么已经被作为叶子节点,已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点,至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ,所以叶子节点必然不会不够。

那么完成最后一步以后叶子节点会不会有剩呢?每个节点会被连接的次数正好是它在序列中出现的次数 +1 ,这也就意味着,总度数恰好是 2n-2 ,由于每一条边都无向,所以构成的正好是一张 n-1 条边的图。

最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的,我们不妨尝试证明它无环。

我们称,一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」,那么每个点的向上连边操作会且仅会发生一次。在这种情况下,环会出现,只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。

然而,向上连边的目标,一定还在 Prufer 序列中,而可以向上连边的点,一定不在 Prufer 序列中。我们于是证明了这张图无环。

既然这张 n-1 条边的图无环,那么它一定连通。

由此,我们发现,每一棵树都能唯一对应地生成一个 Prufer 序列,并且每一个 Prufer 序列都能生成一棵树。

这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;

inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;
			RT%=MOD;
		}
		A*=A;A%=MOD;X>>=1;
	}
	return RT;
}
int n;
void init(){
	scanf("%d",&n);
	ll fac=1;
	for(int i=1;i<n;++i){
		fac=fac*i%MOD;
	}
	printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
	init();
	return 0;
}

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 \(S\) ,其中 \(S_i\) 表示,长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\), 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。 问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢? 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ,足以通过此题。 具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

CF102268C

贪心构造即可。
具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以及x(贡献是下标比x小且<-x)的数。
贪心地构造,可以保证x只出现一次。暴力枚举检验即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
	scanf("%d%lld",&n,&m);
	for(int i=0;i<=n;++i){
		bckt[i]=0;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		a[p[i]]=-n+i-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&q[i]);
		if(m==0){
			b[q[i]]=n;
		}else if(m>=q[i]-1){
			m-=q[i]-1;
			b[q[i]]=-1;
		}else{
			for(int j=1;j<q[i];++j){
				++bckt[a[j]+n];
			}
			for(int j=1;j<=n;++j){
				bckt[j]+=bckt[j-1];
			}
			for(int j=1;j<q[i];++j){
				if(bckt[a[j]+n]==m){
					m=0;b[q[i]]=-a[j]-1;
					break;
				}
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	puts("");
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}
	puts("");
}
int main(){
	init();
	return 0;
}

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。
它本质上就是一种优化的暴力:对于树上的信息,我们先把树以某种方式剖分,然后对于关键链直接上传,非关键链暴力合并。
其中,长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中,我们考虑暴力维护每个点为根的子树中每一层的信息,并把非长儿子的信息合并到长儿子中。
为了保证线性,我们使用指针。
我们建一个指针数组f,其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp,那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n,所以空间是足够的。
那就昨晚了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}

lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到一个n+1个数的序列,使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性,我们可以尝试把无序数对看成一条边,然后建一张图。在这种情况下,这个序列就是这张图上的一个遍历顺序,使得经过每一条边至少一次。
深入考虑,这个序列也只能经过每条边至多一次。这是因为,一条n条边的路径,恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中,恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点,我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上,只需从奇数入度点开始,就是合法的?
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是,为什么搜索的时候不会直接走到链的另一端,而是先把环跑完,或者反过来?
我们注意到把点加入答案数组的方式:对于两个栈——答案栈和搜索栈来说,点被加入的顺序是不仅相同的。
模拟一下,一个点能从搜索栈出来,被加入答案栈,当且仅当从这个点出发无路可走了。
显然,有且仅有终点是无路可走的。那么,无论终点是在什么时候被访问到的,只要它被访问到,那么它就会被立刻退出搜索栈并被加入答案栈,剩下的点也是同理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}

lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得:
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说,购买的A和B券的数量分别是:
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么,我们从j转移到i的方程是:
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设:
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$
那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。
通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意:要判一下分母不能等于极小数,否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得: $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说,购买的A和B券的数量分别是: $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么,我们从j转移到i的方程是: $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设: $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$ 那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。 通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意:要判一下分母不能等于极小数,否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp2564 SCOI2009 生日礼物

尺取法即可。
开一个桶维护珍珠的颜色,然后扫一遍。每一次将最前端的点弹出,然后移动至下一个合法点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
	scanf("%d%d",&n,&K);
	int T;
	for(int i=1;i<=K;++i){
		scanf("%d",&T);
		for(int j=1;j<=T;++j){
			++tp;
			scanf("%d",&a[tp].val);
			a[tp].id=i;
		}
	}
	std::sort(a+1,a+1+n,cmp);
	int ans=2147483647;
	int l=1,r=0;
	while(r<n){
		while(r<n){
			++r;
			if(!bckt[a[r].id]){
				++cnt;
			}
			++bckt[a[r].id];
			if(cnt==K){
				break;
			}
		}
		if(cnt==K){
			ans=min(ans,a[r].val-a[l].val);
		}
		while(l<=r){
			--bckt[a[l].id];
			if(!bckt[a[l].id]){
				--cnt;
				++l;
				break;
			}
			++l;
			if(cnt==K){
//				printf("%d %d %d\n",ans,l,r);
				ans=min(ans,a[r].val-a[l].val);
			}
			
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp2219 HAOI2007 修筑绿化带

我们知道,如果我们确定了每个大矩形包含的权值最小的小矩形,那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。

那么我们考虑用单调队列来预处理出每一个小矩形的权值,然后用二维线段树来维护这个权值,那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然,我们可以维护2n个单调队列来计算这个最大值。
那么,对于这题的强化板,我们该怎么做呢?
如果确定了右下角,那么整个矩形的权值是已经固定了的。那么,我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题,我们发现,每个花坛的最小值是可以预处理的。这样,我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂,且不要混淆单调队列里的数的意义。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1005;

int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
	scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&val[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
		}
	}
	for(int i=B;i<=n;++i){
		for(int j=A;j<=m;++j){
			b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
//			printf("%d ",b[i][j]);
		}
//		puts("");
	}
	for(int i=D;i<=n;++i){
		for(int j=C;j<=m;++j){
			a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
//			printf("%d ",a[i][j]);
		}
//		puts("");
	}
	int ans=0;
	for(int i=D+1;i<n;++i){
		for(int j=C+1;j<m;++j){
//			printf("%d %d\n",i,j);
			while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
			q[j].push_back(i);
			while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
		}
		while(!qq.empty()){qq.pop_back();}
		for(int j=C+1;j<m;++j){
			while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
			qq.push_back(j);
			while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
			if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp3285 SCOI2014 方伯伯的OJ

题目要求维护一个编号序列和一个排名序列,并支持四种操作:
1.按照编号修改编号,并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名,然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8,那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续:这一题是我在190103的时候写完的,然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用,这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误,进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后,经由此处,我发现有个节点的相邻节点是一个大小为空的节点,进而发现这个节点在被分配下标之前就被访问了。
最终,我注意到它第一次出现所相接的节点,并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错,并通过了此题。
注意点:
1.对于空节点的情况一定要认真考虑,因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」!!!!!!
4.如果一个点本来就是排名最后的点而要移到排名最后,有可能会出错。

#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);

bool bo=0;
class Splay{
	public:
		class Node{
			public:
				int l;
				int r;
				int sz;
				int sn[2];
				int fa;
				inline void set(int L,int R,int FA){
					l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
				}
		};
		//i表示mp[i]这个节点的右端点的标号。 
		std::map<int,int> mp;
		Node tr[400005];
		int cnt,rt;
		//寻找当前节点与父亲的关系。 
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		//更新当前节点。 
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
//			if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
		}
		//旋转套装。 
		inline void splayOne(int X){
			if(!X){return;}
			int D=fndD(X),D2=fndD(tr[X].fa);
//			if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
//				puts("FKFKFK");
//				printf("X");debug(X);
//				printf("FA");debug(tr[X].fa);
//				printf("BR");debug(tr[tr[X].fa].sn[D^1]);
//			}
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
//			if(bo&&X==38190){debug(X);}
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){splayTwo(X);}
			rt=X;
		}
//		inline void splayRnw(int X){
//			while(tr[X].fa){
//				int F=tr[X].fa,FF=tr[tr[X].fa].fa;
//				if(!FF)
//			}
//		}
		//找到排名为X的元素。 
		inline int fnd(int X){
			int P=rt;
			while(P){
				if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
					X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
					P=tr[P].sn[1];
				}else if(X>tr[tr[P].sn[0]].sz){
					X-=tr[tr[P].sn[0]].sz;
					splayRnw(P);
//					debug(P);
					return tr[P].l+X-1;
				}else{
					P=tr[P].sn[0];
				}
			}
			return -1; 
		}
		//开一个新节点,以X为它的父亲。 
		inline int nwlc(int X,int L,int R){
			int P=++cnt;
//			if(P==65505){
//				printf("START:");
//				debug(P);
//			}
			tr[P].set(L,R,X);
			return P;
		}
		//将编号为X的节点单独弄成一个新的节点,然后将它的两个子节点接到它的左右,并更改相应的编号的映射 
		inline int split(int P,int X){
			if(tr[P].l==tr[P].r){return P;}
			if(P==-1){return error(192600404),192600404;}
			if(X>tr[P].l){
				int L=tr[P].sn[0];
				L?(cut(L),0):(tr[0].fa=0);
				tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
				L?(cnnct(L,tr[P].sn[0],0),0):0;
				mp[X-1]=tr[P].sn[0];
//				updt(tr[P].sn[0]);
			}
			if(X<tr[P].r){
				int R=tr[P].sn[1];
				R?(cut(R),1):(tr[0].fa=0);
				tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
				R?(cnnct(R,tr[P].sn[1],1),1):1;
				mp[tr[P].r]=tr[P].sn[1];
//				updt(tr[P].sn[1]);
			}
			tr[P].l=tr[P].r=X;mp[X]=P;
			updt(P);
			return P;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0]; 
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline void cut(int X){
			int D=fndD(X);
			tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
		}
		inline void cnnct(int X,int Y,int D){
			tr[Y].sn[D]=X,tr[X].fa=Y;
			updt(Y);
		}
		inline void prnt(int X,int dep=0){
			if(!X){return;}
			for(int i=1;i<=dep;++i){
				printf(" ");
			}debug(X);
			prnt(tr[X].sn[0],dep+1);
			prnt(tr[X].sn[1],dep+1);
		}
	public:
		inline int CHANGE(int X,int Y){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			tr[P].l=tr[P].r=Y;
			mp[Y]=P;
			splayRnw(P);
			return tr[tr[P].sn[0]].sz+1;
		}
		inline int LST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!L){
				return RT;
			}
			R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。 
			return RT;
		}
		inline int RST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!R){
				return RT;
			}
			L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
			return RT;
		}
		inline int ARNK(int X){
			return fnd(X);
		} 
		//初始化。 
		inline void INIT(int N){
			cnt=1;
			rt=1;
			tr[1].set(1,N,0);
			mp[N]=1;
		}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。 
*/

int n,m;
Splay T;
void init(){
	int code=0;
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int op,x,y;
	for(int i=1;i<=m;++i){
		scanf("%d",&op);
		switch(op){
			case 1:{
				scanf("%d%d",&x,&y);
				x-=code,y-=code;
				printf("%d\n",code=T.CHANGE(x,y));
//				if(code==95204&&i>=80000){
//					puts("fk1");
//					printf("%d\n",x);
//					return;
//				}
				break;
			}
			case 2:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.LST(x));
				break;
			}
			case 3:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.RST(x));
				break;
			}
			case 4:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.ARNK(x));
				break;
			}
		}
//		printf("CORESIZE:%d\n",T.tr[54567].sz);
	}
}

int main(){
//	freopen("input1.in","r",stdin);
//	freopen("output1.out","w",stdout);
	init();
	return 0;
} 

lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树,我们可能可以想到用LCT来维护。但是代码难度太高,而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作,也就是说,每一次,我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树,我们暴力更新其中的每一个节点。于是可以证明,每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意:主席树的L,R本身就是节点位置;合并的时候要记得更新小树的根节点;返回的值是第k大的值而非第k大的排名因而要逆离散化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp5395 【模板】第二类斯特林数·行

第二类斯特林数,指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n,m)\)或\(\left\{\begin{matrix}n\\m\end{matrix}\right\}\)
从题意来看,我们可以容易地想到一个递推方案:每个新的元素,可以为它新开一个集合,或者放到已有的任何一个集合里面。所以我们得到一个递推式:
$$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$$
然后问题是怎么求值。

首先我们有一个式子,我们称之为二项式反演的通项式。
$$ f(n)=\sum_{i=0}^nC_{n}^{i}g(n) \Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}C_{i}{n}f(n)$$
举个例子:
$$\begin{matrix} f_{1}&=&g_{1}\\f_{2}&=&g_{1}&+&g_{2}\\f_{3}&=&g_{1}&+&2*g_{2}&+&g_{3}\\f_{4}&=&g_{1}&+&3*g_{2}&+&3*g_{3}&+&g_{4} \end{matrix}$$

由此可得:

$$\begin{matrix} g_{1}&=&f_{1}\\g_{2}&=&f_{2}&-&f_{1}\\g_{3}&=&f_{3}&-&2*g_{2}&-&g_{1}\\&=&f_{3}&-&2*f_{2}&+&f_{1}\\g_{4}&=&f_{4}&-&3*g_{3}&-&3*g_{2}&-&g_{1}\\&=&f_{4}&-&3*f_{3}&-&3*g_{2}&-&4*g_{1}\\&=&f_{4}&-&3*f_{3}&+&3*f_{2}&-&f_{1} \end{matrix}$$

然后我们考虑\(m^n\)的组合意义,也就是,将\(n\)个不同的球,放到\(m\)个不同的盒子(可以有空盒)的方案数。
我们不妨枚举有装东西的盒子的个数。令它为\(i\),那么选取这些盒子的方案数即是\(C_{m}^{i}\)。
选取了盒子之后,问题就转化为了将\(n\)个不同物品装到\(m\)个不同盒子里,使得每个盒子非空。这就相当于,将\(n\)个不同物品装到\(m\)个相同盒子里,使得每个盒子非空的方式——也就是\(S(n,m)\),乘上盒子的排列顺序——也就是\(m!\)。
形式化的说,就是:
$$m^n=\sum_{i=0}^{m}S(n,i)i!C_{m}^{i}$$
我们发现这个式子的形式符合二项式反演的通项式。
因而我们将\(m^n\)作为\(f\),将\(S(n,i)i!\)作为\(g\)。
那么反演得到:
$$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}i^nC_{m}^{i}$$
考虑\(C_{m}^{i}=\frac{m!}{i!(m-i)!}\),我们可以将上式化简得到:
$$S(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
于是我们有:
$$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
考虑函数卷积的本质,对于卷积\(f=gu\),其本质是: $$f(n)=\sum_{i=0}^{n}g(i)u(n-i)$$ 因而,我们发现,上式本质上就是: $$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}*\frac{i^n}{i!}$$
上一个NTT卷积一下就好了。

#include<iostream>
#include<cstdio>

#define Swap(A,B) (A^=B^=A^=B)
const long long P=167772161;
const long long g0=3,gi=55924054;
int L=1,R[1<<21|1];
long long invL;
inline int pw(int A,int X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=RT*BS%P;
		}
		BS=BS*BS%P;
		X>>=1;
	}
	return RT;
}
inline void prpr(int LEN){
	int B=0;
	while(L<=LEN){
		L<<=1;
		++B;
	}
	invL=P-(P-1)/L;
	for(int i=0;i<L;++i){
		R[i]=R[i>>1]>>1|(i&1)<<(B-1);
	}
}
inline void FNTT(int *A,int typ){
	for(int i=0;i<L;++i){
		if(R[i]<i){
			Swap(A[R[i]],A[i]);
		}
	}
	int gn,g,X,Y,M;
	for(int i=2;i<=L;i<<=1){
		M=i>>1;
		gn=pw(~typ?g0:gi,(P-1)/i);
		for(int j=0;j<L;j+=i){
			g=1;
			for(int k=0;k<M;++k,g=1ll*g*gn%P){
				X=A[j+k],Y=1ll*g*A[M+j+k]%P;
				A[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;
			}
		}
	}
}
int n,a[1<<21|1],b[1<<21|1],inv[1<<21|1];
void init(){
	scanf("%d",&n);
	prpr(n+1<<1);
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=1ll*(P-P/i)*inv[P%i]%P;
	}
	for(int i=1;i<=n;++i){
		inv[i]=1ll*inv[i-1]*inv[i]%P;
	}
	for(int i=0;i<=n;++i){
		a[i]=1ll*pw(-1,i)*inv[i]%P;
		b[i]=1ll*pw(i,n)*inv[i]%P;
	}
	FNTT(a,1);
	FNTT(b,1);
	for(int i=0;i<L;++i){
		a[i]=1ll*a[i]*b[i]%P;
	}
	FNTT(a,-1);
	for(int i=0;i<=n;++i){
		printf("%d ",1ll*(a[i]+P)*invL%P);
	}
}

int main(){
	init();
	return 0;
}