差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day3 [2021/05/01 21:25]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day3 [2021/05/02 15:52] (当前版本)
jxm2001
@@ 行 211: / 行 211: @@
 	_rep(i,1,n)
 	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+===== H. 火山哥的序列 =====
+==== 题意 ====
+给定长度为 $n$ 的序列 $a_i$，给定以下函数
+$$
+g(l,r)=\max_{i,j\in [1,l)\cup (r,n],i\le j}\text{gcd}(i,j)
+$$
+若满足上述条件的 $(i,j)$ 不存在，则 $g(l,r)=0$。求 $\sum_{i=1}^n\sum_{j=i}^ng(i,j)$。
+==== 题解 ====
+$$
+\sum_{i=1}^n\sum_{j=i}^ng(i,j)=\sum_{k=1}^\text{V}k\sum_{i=1}^n\sum_{j=i}^n[g(i,j)==k]=\sum_{k=1}^\text{V}k\sum_{i=1}^n\sum_{j=i}^n([g(i,j)\ge k+1]-[g(i,j)\ge k])
+$$
+问题转化为如何计算 $\sum_{i=1}^n\sum_{j=i}^n[g(i,j)\ge k](k=1\sim V)$。
+设 $f(l,k)=\max\{r|g(l,r)\ge k\}$，于是有
+$$
+\sum_{i=1}^n\sum_{j=i}^n[g(i,j)\ge k](k=1\sim V)=\sum_{i=1}^n (f(i,k)-i+1)=\sum_{i=1}^n f(i,k)-\frac {n(n-1)}2
+$$
+问题转化为维护 $f(1\sim n,k)$，考虑 $f(i,k+1)\to f(i,k)$ 的状态转移。
+枚举 $k$ 的倍数，假定 $a_i\mid k$ 的所有位置从小到大依次为 $p_1,p_2\cdots p_{m-1},p_m$。
+若 $m\lt 2$，则有 $f(i,k)=f(i,k+1)$，否则有如下转移：
+\begin{equation}\begin{split}
+&1\le i\le p_1\to f(i,k)=\max\left(f(i,k+1),p_{m-1}-1\right)\\
+&p_1+1\le i\le p_2\to f(i,k)=\max\left(f(i,k+1),p_m-1\right)\\
+&p_2+1\le i\le n\to f(i,k)=\max\left(f(i,k+1),n\right)
+\end{split}\end{equation}
+吉司机线段树维护区间最值操作和区间和查询即可，$f(i,k)$ 初始值为 $i-1$，时间复杂度 $V\log V$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,inf=1e9,MAXV=2e5;
+int lef[MAXN<<2],rig[MAXN<<2],minv[MAXN<<2],minc[MAXN<<2],secv[MAXN<<2],lazy[MAXN<<2];
+LL s[MAXN<<2];
+void push_up(int k){
+	s[k]=s[k<<1]+s[k<<1|1];
+	if(minv[k<<1]==minv[k<<1|1]){
+		minv[k]=minv[k<<1];
+		minc[k]=minc[k<<1]+minc[k<<1|1];
+		secv[k]=min(secv[k<<1],secv[k<<1|1]);
+	}
+	else if(minv[k<<1]<minv[k<<1|1]){
+		minv[k]=minv[k<<1];
+		minc[k]=minc[k<<1];
+		secv[k]=min(secv[k<<1],minv[k<<1|1]);
+	}
+	else{
+		minv[k]=minv[k<<1|1];
+		minc[k]=minc[k<<1|1];
+		secv[k]=min(minv[k<<1],secv[k<<1|1]);
+	}
+}
+void push_tag(int k,int v){
+	if(minv[k]>=v)return;
+	s[k]+=1LL*(v-minv[k])*minc[k];
+	minv[k]=lazy[k]=v;
+}
+void push_down(int k){
+	if(lazy[k]){
+		push_tag(k<<1,lazy[k]);
+		push_tag(k<<1|1,lazy[k]);
+		lazy[k]=0;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,lazy[k]=0;
+	int M=L+R>>1;
+	if(L==R){
+		s[k]=minv[k]=M-1;
+		minc[k]=1;
+		secv[k]=inf;
+		return;
+	}
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update(int k,int L,int R,int v){
+	if(minv[k]>=v)return;
+	if(L<=lef[k]&&rig[k]<=R&&secv[k]>v)
+	return push_tag(k,v);
+	int mid=lef[k]+rig[k]>>1;
+	push_down(k);
+	if(mid>=L)
+	update(k<<1,L,R,v);
+	if(mid<R)
+	update(k<<1|1,L,R,v);
+	push_up(k);
+}
+int a[MAXN],p[MAXN];
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int();
+		build(1,1,n);
+		mem(p,0);
+		_rep(i,1,n){
+			a[i]=read_int();
+			p[a[i]]=i;
+		}
+		LL last=0,ans=0;
+		for(int i=MAXV;i;i--){
+			int max1=0,max2=0,min1=inf,min2=inf,cnt=0;
+			for(int j=1;i*j<=MAXV;j++){
+				if(p[i*j]){
+					if(p[i*j]>=max1){
+						max2=max1;
+						max1=p[i*j];
+					}
+					else
+					max2=max(max2,p[i*j]);
+					if(p[i*j]<=min1){
+						min2=min1;
+						min1=p[i*j];
+					}
+					else
+					min2=min(min2,p[i*j]);
+					cnt++;
+				}
+			}
+			if(cnt<2)continue;
+			update(1,1,min1,max2-1);
+			update(1,min1+1,min2,max1-1);
+			update(1,min2+1,n,n);
+			LL cur=s[1]-1LL*n*(n-1)/2;
+			ans+=1LL*(cur-last)*i;
+			last=cur;
+		}
+		enter(ans);
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具