2024.2.6 【寒假集训】20240206测试
T1 珠子
T2 数组
这个题，我没考虑到的是要保留全部的 \(x,y\) 操作信息，以及上一次 \(A\) 操作的时间等等。
代码（参考 lcy）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int t1[500001],t2[500001];
int lst[50000100];
int pos,dx;
signed main()
{
cin>>n>>m;
int su=(n+1)*n/2;
pos=0,t1[0]=1,t2[0]=0;
// for(int i=1;i<=n;i++)lst[i]=i;
for(register int i=1;i<=m;++i)
{
char c=getchar();
int x,y;cin>>x>>y;
t1[i]=x,t2[i]=y;
if(c=='A')
{
pos=i,dx=0;
printf("%lld\n",x*su+n*y);
}
else
{
if(lst[t1[i]]<=pos)
{
dx+=t2[i]-(t1[i]*t1[pos]+t2[pos]);
lst[t1[i]]=i;
}
else
{
int last=lst[t1[i]];
dx-=t2[last]-(t1[i]*t1[pos]+t2[pos]);
dx+=t2[i]-(t1[i]*t1[pos]+t2[pos]);
lst[t1[i]]=i;
}
printf("%lld\n",t1[pos]*su+t2[pos]*n+dx);
}
}
return 0;
}
T3 幸运区间
题意：在序列 \(a\) 中，求出所有子序列 \(b\) 中， \(\gcd(b)=1\) 的个数。
\[\sum_{x=1}^{n}\sum_{y=x}^{n}[\gcd(x \sim y)==1] \](\(\sim\) 表示从 \(x\) 到 \(y\) 的所有元素)
考虑画出一个表示所有子序列的 \(\gcd\) 的三角形矩阵：
1
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
5 1 4 1 3 1 2 1 1
5 5 4 4 3 3 2 2 1 1
我们可以看到，从最下面开始，对于每个左端点确定的区间，只要在右端点为 \(r\) 的时候 \(\gcd=1\) ，那么从\([l,r]\) 到 \([l,n]\)，所有区间的 \(\gcd=1\)。
有一个定理：只要一个序列的子序列 \(\gcd=1\)，那么这个序列 \(\gcd=1\)。
所以，我们需要实现两个东西：
-
查找区间 \([l,r]\) 的 \(\gcd\)。
-
找到对于一个 \(l\in [1,n]\)，\(r\) 最小并且 \(\gcd=1\) 的子序列，统计答案
ans+=n-r+1。
对于查找，由上面的定理可知， \(\gcd\) 具有传递性，因此我们可以构建一棵线段树来实现此操作。
tr[now].gcd=__gcd(tr[lid].gcd,tr[rid].gcd);
对于找到一个 \(l\)、满足条件的最小的 \(r\)，我们考虑直接 for 循环去找（区间伸缩）。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[200100];
class emw{
public:
#define lid now<<1
#define rid now<<1|1
void build(int now,int l,int r)
{
if(l==r){
tr[now].g=a[l];return ;
}
int mid=(l+r)>>1;
build(lid,l,mid),build(rid,mid+1,r);
tr[now].g=__gcd(tr[lid].g,tr[rid].g);
}
int getgcd(int now,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return tr[now].g;
int mid=(l+r)>>1;
int res=0;
if(x<=mid) res=__gcd(res,getgcd(lid,l,mid,x,y));
if(y>mid) res=__gcd(res,getgcd(rid,mid+1,r,x,y));
return res;
}
private:
struct segTree{
int g;
}tr[200100<<2];
}st;
int ans;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
st.build(1,1,n);
int l=1,r=1;
for(l=1;l<=n;l++)
{
r=max(l,r);
while(l<=r&&r<=n)
{
if(st.getgcd(1,1,n,l,r)==1)
{
break;
}
r++;
}
ans+=(n-r+1);
}
cout<<ans;
return 0;
}