总结

虽然 \(A\) 了一道题，但是 \(T1\) 人均切没有什么用

差距在 \(T2\) 和 \(T3\)

A. Manager

分析

发现子树内的贡献只能是原中位数或者原中位数后面的那一个数

而且权值小更改后的一定是较大的贡献，权值大的更改后一定是较小的贡献

以权值为下标开线段树，做线段树合并就行了

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=4e5+5;
int a[maxn],n,h[maxn],tot=1,fa[maxn];
struct asd{
	int to,nxt;
}b[maxn];
void ad(rg int aa,rg int bb){
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	h[aa]=tot++;
}
int siz[maxn],ans1[maxn],ans2[maxn],cnt,rt[maxn],id[maxn],rk[maxn];
bool cmp(rg int aa,rg int bb){
	if(a[aa]==a[bb]) return aa<bb;
	return a[aa]<a[bb];
}
struct trr{
	int lch,rch,siz;
	long long laz,val;
}tr[maxn*20];
void push_up(rg int da){
	tr[da].val=tr[tr[da].lch].val+tr[tr[da].rch].val;
	tr[da].siz=tr[tr[da].lch].siz+tr[tr[da].rch].siz;
}
void push_down(rg int da){
	if(!tr[da].laz) return;
	rg int lc=tr[da].lch,rc=tr[da].rch;
	if(lc){
		tr[lc].laz+=tr[da].laz;
		tr[lc].val+=1LL*tr[lc].siz*tr[da].laz;
	}
	if(rc){
		tr[rc].laz+=tr[da].laz;
		tr[rc].val+=1LL*tr[rc].siz*tr[da].laz;
	}
	tr[da].laz=0;
}
int ad(rg int da,rg int l,rg int r,rg int wz){
	if(!da) da=++cnt;
	push_down(da);
	if(l==r){
		tr[da].siz=1;
		return da;
	}
	rg int mids=(l+r)>>1;
	if(wz<=mids) tr[da].lch=ad(tr[da].lch,l,mids,wz);
	else tr[da].rch=ad(tr[da].rch,mids+1,r,wz);
	push_up(da);
	return da;
}
int bing(rg int aa,rg int bb,rg int l,rg int r){
	if(!aa || !bb) return aa+bb;
	push_down(aa),push_down(bb);
	rg int mids=(l+r)>>1;
	tr[aa].lch=bing(tr[aa].lch,tr[bb].lch,l,mids);
	tr[aa].rch=bing(tr[aa].rch,tr[bb].rch,mids+1,r);
	push_up(aa);
	return aa;
}
int cx(rg int da,rg int l,rg int r,rg int kth){
	if(l==r) return l;
	push_down(da);
	rg int mids=(l+r)>>1;
	if(tr[tr[da].lch].siz>=kth) return cx(tr[da].lch,l,mids,kth);
	else return cx(tr[da].rch,mids+1,r,kth-tr[tr[da].lch].siz);
}
void xg(rg int da,rg int l,rg int r,rg int nl,rg int nr,rg int val){
	if(!da) return;
	push_down(da);
	if(l>=nl && r<=nr){
		tr[da].val+=1LL*tr[da].siz*val;
		tr[da].laz+=val;
		return;
	}
	rg int mids=(l+r)>>1;
	if(nl<=mids) xg(tr[da].lch,l,mids,nl,nr,val);
	if(nr>mids) xg(tr[da].rch,mids+1,r,nl,nr,val);
	push_up(da);
}
void dfs1(rg int now){
	siz[now]=1;
	rt[now]=ad(rt[now],1,n,rk[now]);
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==fa[now]) continue;
		dfs1(u);
		siz[now]+=siz[u];
		rt[now]=bing(rt[now],rt[u],1,n);
	}
	if(siz[now]==1){
		ans1[now]=a[now];
		ans2[now]=1e5;
		xg(rt[now],1,n,1,n,1e5);
	} else {
		rg int tmp1=(siz[now]+1)>>1,tmp2,tmp3;
		tmp2=cx(rt[now],1,n,tmp1);
		tmp3=cx(rt[now],1,n,tmp1+1);
		ans1[now]=a[id[tmp2]];
		ans2[now]=a[id[tmp3]];
		xg(rt[now],1,n,1,tmp2,ans2[now]);
		xg(rt[now],1,n,tmp3,n,ans1[now]);
	}
}
long long ans[maxn],sum;
void dfs2(rg int da,rg int l,rg int r){
	if(!da) return;
	if(l==r){
		ans[id[l]]=tr[da].val;
		return;
	}
	push_down(da);
	rg int mids=(l+r)>>1;
	dfs2(tr[da].lch,l,mids);
	dfs2(tr[da].rch,mids+1,r);
	push_up(da);
}
void dfs3(rg int now,rg long long nval){
	nval+=ans1[now];
	ans[now]+=sum-nval;
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==fa[now]) continue;
		dfs3(u,nval);
	}
}
int main(){
	memset(h,-1,sizeof(h));
	n=read();
	for(rg int i=1;i<=n;i++) a[i]=read();
	for(rg int i=2;i<=n;i++){
		fa[i]=read();
		ad(i,fa[i]),ad(fa[i],i);
	}
	for(rg int i=1;i<=n;i++) id[i]=i;
	std::sort(id+1,id+n+1,cmp);
	for(rg int i=1;i<=n;i++) rk[id[i]]=i;
	dfs1(1);
	dfs2(rt[1],1,n);
	for(rg int i=1;i<=n;i++) sum+=ans1[i];
	dfs3(1,0);
	for(rg int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}

B. GCD再放送

分析

设 \(f[x]\) 为 \(gcd\) 为 \(x\) 的区间的个数

令 \(g[x] =\sum_{x|d} f[d]\)

求出 \(g\) 数组的值之后即可由莫比乌斯反演求出 \(f\) 数组的值

考虑如何快速地求出 \(g\) 的值

当 \(k=1\) 时，设有 \(m\) 个数为 \(x\) 的倍数，那么

\(g[x]=\sum_{i=1}^mC_m^ii!(n-i)!(n-i+1)\)

当 \(k>1\) 时，设 \(len[x]\) 为当前最近的一个 \(gcd\) 是 \(x\) 倍数的区间的长度，\(r[x]\) 为这个区间的右端点

如果当前扫到的值是 \(val\)

那么能够延长的区间只能是 \(val\) 的约数

所以枚举约数看一下能不能继续延长即可

把所有的序列分成三种

\(all\) 类序列:整个序列的 \(gcd\) 是 \(x\) 的倍数

\(pre\) 类序列:序列有一些前缀的 \(gcd\) 是 \(x\) 的倍数，但不是所有前缀

\(suf\) 类序列:序列有一些后缀的 \(gcd\) 是 \(x\) 的倍数，但不是所有后缀

可以把答案分成两部分，一个是序列单独的贡献，另一个是几个序列拼起来的贡献

单独的贡献就是 \(\frac{len[x](len[x]+1)}{2} n!\)

拼起来的贡献有四种情况

\(1\)、\(suf-all-all\)

\(2\)、\(all-all-pre\)

\(3\)、\(suf-all-pre\)

\(4\)、\(all-all-all\)

对于第一种情况，设有 \(x\) 个 \(suf\) 序列，\(y\) 个 \(all\) 序列

枚举中间有多少 \(all\) 序列以及左右两边是哪两个序列，那么答案就是

\(\sum_{i=0}^{y-1}\sum_{j=0}^y\sum_{k=0}^xC_{y-1}^ii!(n-i-2)!(n-i-1)len[j]len[k]\)

设 \(sum1\) 为 \(suf\) 序列的 \(len\) 之和，\(sum2\) 为 \(all\) 序列的 \(len\) 之和

那么答案就是 \(\sum_{i=1}^{y-1}C_{y-1}^ii!(n-i-1)!sum1sum2\)

对于其它三种情况同理

但是这样做会有不合法的情况

因为一个序列既可能是 \(pre\) 又可能是 \(suf\)

所以第三种情况还要把自己对自己的贡献减去，即同一个序列的 \(len[pre]\) 与 \(len[suf]\) 乘积的和

在第四中情况中一个 \(all\) 序列也会做两次贡献，还要记录一个 \(len[all]^2\) 的前缀和将其减去

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e5+5,mod=1e9+7,mmax=1e5;
inline int addmod(rg int now1,rg int now2){
	return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
	return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1>=mod?now1%mod:now1;
}
int a[maxn],n,jc[maxn],jcc[maxn],ny[maxn];
std::vector<int> v[maxn];
int cnt[maxn],pri[maxn],mu[maxn],k;
bool not_pri[maxn];
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=mmax;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=mmax;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
	for(rg int i=1;i<=mmax;i++){
		for(rg int j=i;j<=mmax;j+=i){
			v[j].push_back(i);
		}
	}
	not_pri[0]=not_pri[1]=1;
	mu[1]=1;
	for(rg int i=2;i<=mmax;i++){
		if(!not_pri[i]){
			pri[++pri[0]]=i;
			mu[i]=mod-1;
		}
		for(rg int j=1;j<=pri[0] && i*pri[j]<=mmax;j++){
			not_pri[i*pri[j]]=1;
			if(i%pri[j]==0) break;
			mu[i*pri[j]]=mod-mu[i];
		}
	}
}
int getC(rg int nn,rg int mm){
	if(nn<mm) return 0;
	return mulmod(jc[nn],mulmod(jcc[mm],jcc[nn-mm]));
}
int getsum(rg int now){
	return mulmod(now,mulmod(now+1,ny[2]));
}
int g[maxn],f[maxn],ans,cntpre[maxn],cntsuf[maxn],sumpresuf[maxn],sumall[maxn],sumall2[maxn],num[maxn],len[maxn],r[maxn],sta[maxn*20],tp;
int ncntpre[maxn],ncntsuf[maxn];
void solve(){
	tp=0;
	rg int tmp;
	for(rg int i=1;i<=k;i++){
		for(rg int j=0;j<v[a[i]].size();j++){
			tmp=v[a[i]][j];
			sta[++tp]=tmp;
			if(r[tmp]==i-1){
				len[tmp]++;
				r[tmp]=i;
			} else {
				if(len[tmp]){
					if(r[tmp]-len[tmp]+1==1){
						ncntpre[tmp]+=len[tmp];
						g[tmp]=addmod(g[tmp],mulmod(jc[n],getsum(len[tmp])));
					} else {
						g[tmp]=addmod(g[tmp],mulmod(jc[n],getsum(len[tmp])));
					}
				}
				len[tmp]=1;
				r[tmp]=i;
			}
		}
	}
	for(rg int i=1;i<=tp;i++){
		tmp=sta[i];
		if(len[tmp]){
			g[tmp]=addmod(g[tmp],mulmod(jc[n],getsum(len[tmp])));
			if(r[tmp]==k){
				if(len[tmp]==k){
					sumall[tmp]=addmod(sumall[tmp],k);
					sumall2[tmp]=addmod(sumall2[tmp],mulmod(k,k));
					num[tmp]++;
				} else {
					ncntsuf[tmp]+=len[tmp];
				}
			} else if(r[tmp]-len[tmp]+1==1){
				ncntpre[tmp]=addmod(ncntpre[tmp],len[tmp]);
			}
		}
		len[tmp]=r[tmp]=0;
	}
	for(rg int i=1;i<=tp;i++){
		tmp=sta[i];
		cntpre[tmp]=addmod(cntpre[tmp],ncntpre[tmp]);
		cntsuf[tmp]=addmod(cntsuf[tmp],ncntsuf[tmp]);
		sumpresuf[tmp]=addmod(sumpresuf[tmp],mulmod(ncntpre[tmp],ncntsuf[tmp]));
		ncntpre[tmp]=ncntsuf[tmp]=0;
	}
}
int js(rg int val){
	rg int nans=0,tmp=0;
	for(rg int i=0;i<=num[val]-1;i++){
		tmp=mulmod(getC(num[val]-1,i),mulmod(sumall[val],addmod(cntpre[val],cntsuf[val])));
		tmp=mulmod(tmp,mulmod(jc[i],jc[n-i-1]));
		nans=addmod(nans,tmp);
	}
	for(rg int i=0;i<=num[val];i++){
		tmp=mulmod(getC(num[val],i),delmod(mulmod(cntpre[val],cntsuf[val]),sumpresuf[val]));
		tmp=mulmod(tmp,mulmod(jc[i],jc[n-i-1]));
		nans=addmod(nans,tmp);
	}
	for(rg int i=0;i<=num[val]-2;i++){
		tmp=mulmod(getC(num[val]-2,i),delmod(mulmod(sumall[val],sumall[val]),sumall2[val]));
		tmp=mulmod(tmp,mulmod(jc[i],jc[n-i-1]));
		nans=addmod(nans,tmp);
	}
	return nans;
}
int main(){
	n=read();
	pre();
	for(rg int i=1;i<=n;i++){
		k=read();
		for(rg int j=1;j<=k;j++) a[j]=read();
		solve();
	}
	for(rg int i=1;i<=mmax;i++) g[i]=addmod(g[i],js(i));
	for(rg int i=1;i<=mmax;i++){
		for(rg int j=0;j<v[i].size();j++){
			f[v[i][j]]=addmod(f[v[i][j]],mulmod(g[i],mu[i/v[i][j]]));
		}
	}
	for(rg int i=1;i<=mmax;i++) ans=addmod(ans,mulmod(i,f[i]));
	printf("%d\n",ans);
	return 0;
}

C. dict

分析

枚举 \(A\) 序列和 \(B\) 序列从第几个数开始不一样

对于每一种情况，枚举开始不一样的那个数的值

然后每个未知区间的方案都是关于值域和长度的一个组合数可以直接计算

这样做是 \(n^3\) 的

发现确定一个点只会把一个大区间分成两个小区间

把大区间的贡献除掉把两个小区间的贡献乘上就变成了 \(n^2\)

现在的瓶颈主要在于枚举合法的值

这个东西其实也可转换成总的方案减去不合法的值

看一下合法的值和不合法的值哪一个更少就去枚举哪一个

类似于启发式分裂，复杂度就是 \(nlogn\) 的

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=2e5+5,mod=998244353;
inline int addmod(rg int now1,rg int now2){
	return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
	return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1>=mod?now1%mod:now1;
}
inline int ksm(rg int ds,rg int zs){
	rg int nans=1;
	while(zs){
		if(zs&1) nans=mulmod(nans,ds);
		ds=mulmod(ds,ds);
		zs>>=1;
	}
	return nans;
}
int a[maxn],n,jc[maxn],jcc[maxn],ny[maxn],m,p[maxn],ans,nans;
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=m;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=m;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
}
int getC(rg int nn,rg int mm){
	if(nn<mm) return 0;
	return mulmod(jc[nn],mulmod(jcc[mm],jcc[nn-mm]));
}
std::set<int> s;
int main(){
	n=read(),m=read();
	pre();
	for(rg int i=1;i<=n;i++) a[i]=read();
	std::sort(a+1,a+n+1);
	for(rg int i=1;i<=n;i++) p[i]=read();
	a[n+1]=m+1;
	nans=getC(m,n);
	s.insert(0),s.insert(n+1);
	rg int hf,bhf,le,ri,minval,maxval;
	for(rg int i=1;i<=n;i++){
		le=*--s.upper_bound(p[i]),ri=*s.upper_bound(p[i]);
		minval=a[le],maxval=a[ri];
		hf=a[p[i]]-minval-1,bhf=maxval-a[p[i]];
		nans=mulmod(nans,ksm(getC(a[ri]-a[le]-1,ri-le-1),mod-2));
		rg int tmp=0;
		if(hf<bhf){
			for(rg int j=minval;j<a[p[i]];j++) tmp=addmod(tmp,mulmod(getC(j-a[le]-1,p[i]-le-1),getC(a[ri]-j-1,ri-p[i]-1)));
		}  else {
			for(rg int j=a[p[i]];j<=maxval;j++) tmp=delmod(tmp,mulmod(getC(j-a[le]-1,p[i]-le-1),getC(a[ri]-j-1,ri-p[i]-1)));
			tmp=addmod(tmp,getC(a[ri]-a[le]-1,ri-le-1));
		}
		s.insert(p[i]);
		ans=addmod(ans,mulmod(tmp,nans));
		nans=mulmod(nans,mulmod(getC(a[p[i]]-a[le]-1,p[i]-le-1),getC(a[ri]-a[p[i]]-1,ri-p[i]-1)));
	}
	printf("%d\n",ans);
	return 0;
}