I. query
比赛时候没有预处理因子疯狂t,其实预处理出来因子是\(O(nlog(n))\)级别的
每个数和他的因子是一对偏序关系,因此询问转化为(l,r)区间每个数的因子在区间(l,r)的个数
预处理出来每个位置上的数所有因子的位置,用可持久化线段树维护,区间询问
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define ft first
#define se second
#define pii pair<int,int>
#define db double
#define ls o<<1
#define rs o<<1|1
#define lowbit(x) (x&-x)
using namespace std;
const int M=1e5+5;
int V[M*200];
int lch[M*200],rch[M*200];
int rt[M],tot=0;
vector<int>fac[M];
int p[M],a[M];
int n,m;
void init(int N){
for(int i=1;i<=N;i++){
for(int j=2*i;j<=N;j+=i)
fac[j].push_back(i);
}
}
void upd(int &o,int pre,int l,int r,int p){
o=++tot;
V[o]=V[pre];
lch[o]=lch[pre];
rch[o]=rch[pre];
if(p==0||l==r){
V[o]++;
return ;
}
int mid=(l+r)/2;
if(p<=mid)
upd(lch[o],lch[pre],l,mid,p);
else
upd(rch[o],rch[pre],mid+1,r,p);
V[o]=V[lch[o]]+V[rch[o]];
}
int qy(int o,int pre,int l,int r,int L,int R){
if(!o)
return 0;
if(L<=l&&r<=R)
return V[o]-V[pre];
int mid=(l+r)/2;
int ans=0;
if(L<=mid)
ans+=qy(lch[o],lch[pre],l,mid,L,R);
if(R>mid)
ans+=qy(rch[o],rch[pre],mid+1,r,L,R);
return ans;
}
int main(){
cin>>n>>m;
init(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
}
for(int i=1;i<=n;i++){
upd(rt[i],rt[i-1],1,n,0);
for(auto v:fac[a[i]])
upd(rt[i],rt[i],1,n,p[v]);
}
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",qy(rt[r],rt[l-1],1,n,l,r));
}
return 0;
}
J. Random Access Iterator
需要计算能成功走到最深节点的概率,对于每个节点,有k次尝试机会,显然计算连续失败k次的概率比较简单
\(dp[u]\)代表从u往下走失败的概率,转移为\(dp[u]=(\frac{1}{sz[son]} \Sigma_{son} dp[v])^{sz[son]}\),答案为\(1-dp[root]\)
预处理出来每个节点的高度
树形概率从叶子往上推
M. Longest subsequence
字典序需要严格大于T,意味着下面两种情况满足任一种即可
选出的子序列s只要某一位对应T大,后面的可全选
子序列s所有位和T一样,那么s要比T长
对S贪心,肯定选出的位置越左越好
若S[i]>T[j],则S后面都可以选
若S[i]<T[j],该位不符合要求不能选
若S[i]==T[j],则在S中找到i后面第一个比T[j+1]大的位置更新答案
处理出S[i]后面第一个c可以用序列自动机
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define ft first
#define se second
#define pii pair<int,int>
#define db double
#define ls o<<1
#define rs o<<1|1
#define lowbit(x) (x&-x)
using namespace std;
const int M=1e6+5;
int f[M][27],w[27];
int n,m;
char s[M],t[M];
int main(){
scanf("%d%d",&n,&m);
scanf("%s%s",s,t);
for(int i=0;i<26;i++)
w[i]=-1;
for(int i=n-1;i>=0;i--){
for(int j=0;j<26;j++)
f[i][j]=w[j];
w[s[i]-'a']=i;
}
int ans=-1;
for(int i=t[0]-'a'+1;i<26;i++){
if(f[0][i]>=0){
ans=max(ans,n-f[0][i]);
}
}
int p=0;
for(int i=0;i<n;i++){
if(s[i]<t[p])continue;
if(s[i]>t[p])break;
if(p==m-1){
if(i+1<n)
ans=max(ans,p+1+n-i-1);
break;
}else{
for(int j=t[p+1]-'a'+1;j<26;j++){
if(f[i][j]>=0)
ans=max(ans,p+1+n-f[i][j]);
}
p++;
}
}
cout<<ans<<endl;
return 0;
}
