CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/20 17:29]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本)
jxm2001 [题解]
@@ 行 2: / 行 2: @@
 ====== 题解 ======
+===== A. Arithmetic Progression =====
+==== 题意 ====
+给定一个序列，问有多少连续子串从小到大排列后可以构成等差序列。
+==== 题解 ====
+给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。
+等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3#等差序列判定|证明]]。
+于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。
+考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。
+线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。
+对每个区间将 $b_i=r\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的数值个数计入贡献。
+易知 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间最多只有 $O(\log v)$ 个，于是总询问次数 $O(n\log v)$。
+然后移动 $r$ 更新区间，需要维护 $\max(a[l\sim r]),\min(a[l\sim r]),i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化。
+对 $\max(a[l\sim r]),\min(a[l\sim r])$ 的变化可以用单调栈维护，总更新次数 $O(n)$。
+对 $i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化，可以维护 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的段。
+每次 $r$ 变化时暴力遍历 $O(\log v)$ 个段，每个段的值发生变化时暴力遍历整个段更新。
+由于每个位置的 $\text{gcd}$ 值最多变化 $O(\log v)$ 次，所以总更新次数 $O(n\log v)$。
+于是线段树只需要支持区间加操作和区间查询操作，总时间复杂度 $O(n\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+struct Node{
+	LL v;
+	int cnt;
+	Node operator + (const Node &b)const{
+		Node c;
+		if(v==b.v)c.v=v,c.cnt=cnt+b.cnt;
+		else if(v<b.v)c=*this;
+		else c=b;
+		return c;
+	}
+}s[MAXN<<2];
+LL tag[MAXN<<2];
+int lef[MAXN<<2],rig[MAXN<<2];
+void push_up(int k){
+	s[k]=s[k<<1]+s[k<<1|1];
+}
+void push_add(int k,LL v){
+	s[k].v+=v;
+	tag[k]+=v;
+}
+void push_down(int k){
+	if(tag[k]){
+		push_add(k<<1,tag[k]);
+		push_add(k<<1|1,tag[k]);
+		tag[k]=0;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,tag[k]=0;
+	if(L==R){
+		s[k].v=0;
+		s[k].cnt=1;
+		return;
+	}
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update(int k,int L,int R,LL v){
+	if(L<=lef[k]&&rig[k]<=R){
+		push_add(k,v);
+		return;
+	}
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)
+	update(k<<1,L,R,v);
+	if(mid<R)
+	update(k<<1|1,L,R,v);
+	push_up(k);
+}
+Node query(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)
+	return s[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=R)
+	return query(k<<1,L,R);
+	else if(mid<L)
+	return query(k<<1|1,L,R);
+	else
+	return query(k<<1,L,R)+query(k<<1|1,L,R);
+}
+int gcd(int a,int b){
+	while(b){
+		int t=b;
+		b=a%b;
+		a=t;
+	}
+	return a;
+}
+int a[MAXN],st1[MAXN],st2[MAXN];
+pair<int,int> st3[MAXN];
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int();
+		_rep(i,1,n)a[i]=read_int();
+		build(1,1,n);
+		LL ans=n;
+		int top1=0,top2=0,top3=0;
+		_rep(i,1,n){
+			while(top1&&a[st1[top1]]<=a[i]){
+				update(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]);
+				top1--;
+			}
+			st1[++top1]=i;
+			while(top2&&a[st2[top2]]>=a[i]){
+				update(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]);
+				top2--;
+			}
+			st2[++top2]=i;
+			if(i==1)continue;
+			st3[++top3]=make_pair(abs(a[i]-a[i-1]),i-1);
+			update(1,i-1,i-1,1LL*(i-1)*st3[top3].first);
+			for(int j=top3-1;j;j--){
+				if(st3[j+1].first%st3[j].first!=0){
+					int temp=st3[j].first;
+					st3[j].first=gcd(st3[j].first,st3[j+1].first);
+					_rep(k,st3[j-1].second+1,st3[j].second)
+					update(1,k,k,1LL*k*(st3[j].first-temp));
+				}
+			}
+			int temp=0;
+			_rep(j,1,top3){
+				if(st3[j].first==st3[temp].first)
+				st3[temp].second=st3[j].second;
+				else
+				st3[++temp]=st3[j];
+			}
+			top3=temp;
+			_rep(j,1,top3){
+				Node temp=query(1,st3[j-1].second+1,st3[j].second);
+				if(temp.v==1LL*i*st3[j].first)
+				ans+=temp.cnt;
+			}
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== B. Cannon =====
@@ 行 15: / 行 178: @@
 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。
-对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=n-k}^{n} C(n+m-k,i)$
+对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=k-m}^{n} C(n+m-k,i)$
 虽然没有直接的结论，但是这个可以用步移算法来解决。

CVBB ACM Team

用户工具

站点工具

页面工具