| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 60 | 15 | - | 175 | 8/22 |
A. 开挂
首先我们希望总步数最小，排序后一次使每个数成为大于它的最小的数即可。
然后根据排序不等式，我们希望修改操作尽可能的集中，倒着扫即可。此时需要确定比这个数大的最小的数，我使用了线段树。动态开点会被卡空间，提前离散化一下即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
#define lid id<<1
#define rid id<<1|1
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,inf=2e9;
int n,a[maxn],b[maxn],c[maxn],d[maxn],cnt,tr[maxn<<2];
il void build(int id,int l,int r){tr[id]=l;if(l==r){return ;}int mid=(l+r)>>1;build(lid,l,mid);build(rid,mid+1,r);
}
il void upd(int id,int l,int r,int p){if(l==r){tr[id]=inf;return ;}int mid=(l+r)>>1;if(p<=mid){upd(lid,l,mid,p);}else{upd(rid,mid+1,r,p);}tr[id]=min(tr[lid],tr[rid]);
}
il int query(int id,int L,int R,int l,int r){if(L>=l&&R<=r){return tr[id];}int mid=(L+R)>>1,res=inf;if(l<=mid){res=min(res,query(lid,L,mid,l,r));}if(r>mid){res=min(res,query(rid,mid+1,R,l,r));}return res;
}
namespace cplx{bool end;il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
// freopen("sample_openhook6.in","r",stdin);ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++){d[i]=a[i];if(d[i-1]>=d[i]){d[i]=d[i-1]+1;}}build(1,1,n);for(int i=n;i;i--){int t=query(1,1,n,lwrb(d+1,d+n+1,a[i])-d,n);
// cout<<t<<'\n';c[++cnt]=d[t]-a[i];upd(1,1,n,t);}sort(c+1,c+cnt+1);ull ans=0;for(int i=cnt,j=1;i;i--,j++){ans+=c[i]*1llu*b[j];}cout<<ans;return 0;
}
}
int main(){return asbt::main();}
B. 叁仟柒佰万
首先可以暴力 DP，枚举 \(\operatorname{mex}\)，设 \(f_i\) 表示以 \(i\) 为结尾的方案数。然后可以发现有贡献的 \(\operatorname{mex}\) 只有全局 \(\operatorname{mex}\)。证明如下：
设全局 \(\operatorname{mex}\) 为 \(k\)。若最终的 \(\operatorname{mex}=x\)，分类讨论：
- \(x<k\)，由于全局 \(\operatorname{mex}\) 为 \(k\)，则必然有一个区间中有 \(x\)，即该区间的 \(\operatorname{mex}\ne x\)，矛盾。
- \(x>k\)，由于全局 \(\operatorname{mex}\) 不为 \(k\)，则序列中没有 \(k\)，此情况不可能。
故最终的 \(\operatorname{mex}\) 只能为 \(k\)。
于是就不用枚举 \(\operatorname{mex}\) 了。转移式长这样：
\[f_i=\sum_{j=0}^{p}f_j
\]
其中满足 \(\operatorname{mex}[p+1,i]=k\) 且 \(\operatorname{mex}[p,i]\ne k\)。显然 \(p\) 关于 \(i\) 是不降的，双指针即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=4e7+5,mod=1e9+7;
il int pls(int x,int y){return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){x=pls(x,y);
}
il int mns(int x,int y){return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){x=mns(x,y);
}
int T,n,a[maxn],f[maxn],vis[maxn];
il void input(){int x,y;cin>>x>>y;for(int i=2;i<=n;i++){a[i]=(a[i-1]*1ll*x+y+i)&262143;}
}
il int mex(){int t=0;for(int i=1;i<=n;i++){vis[a[i]]=1;while(vis[t]){t++;}}for(int i=0;i<=n;i++){vis[i]=0;}return t;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n;if(n<=3e5){for(int i=1;i<=n;i++){cin>>a[i];}}else{input();}int k=mex();
// cout<<k<<'\n';f[0]=1;int p=1,cnt=0;for(int i=1;i<=n;i++){vis[a[i]]++;if(cnt<k&&a[i]<k&&vis[a[i]]==1){cnt++;}int t=0;if(cnt==k){while(p<i&&(a[p]>=k||vis[a[p]]>1)){vis[a[p++]]--;}t=f[p-1];
// cout<<i<<' '<<p<<'\n';}f[i]=pls(f[i-1],t);}cout<<mns(f[n],f[n-1])<<'\n';for(int i=0;i<=n;i++){f[i]=vis[i]=0;}}return 0;
}
}
int main(){return asbt::main();}
C. 超级加倍
考虑建出 kruskal 重构树 T1 和 T2，于是题目要求变为 \(x\) 在 T1 上是 \(y\) 的祖先并且 \(y\) 在T2 上是 \(x\) 的祖先。在 T1 上跑出 dfn 后在 T2 上二维偏序即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e6+5;
int n,fa[maxn],dfn[maxn],cnt,sz[maxn];
ll ans;
struct edge{int u,v,w;il bool operator<(const edge &x)const{return w<x.w;}
}e[maxn];
struct{#define lowbit(x) (x&-x)int tr[maxn];il void add(int p,int v){for(;p<=n;p+=lowbit(p)){tr[p]+=v;}}il int query(int p){int res=0;for(;p;p-=lowbit(p)){res+=tr[p];}return res;}#undef lowbit
}F;
struct{vector<int> e[maxn];il void dfs1(int u){sz[u]=1,dfn[u]=++cnt;for(int v:e[u]){dfs1(v);sz[u]+=sz[v];}}il void dfs2(int u){ans+=F.query(dfn[u]+sz[u]-1)-F.query(dfn[u]-1);F.add(dfn[u],1);for(int v:e[u]){dfs2(v);}F.add(dfn[u],-1);}
}T1,T2;
il int find(int x){return x!=fa[x]?fa[x]=find(fa[x]):x;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1,j;i<=n;i++){cin>>j;if(j){e[i-1]={min(i,j),max(i,j),max(i,j)};}fa[i]=i;}sort(e+1,e+n);for(int i=1;i<n;i++){int u=e[i].u,v=e[i].v;T1.e[v].pb(find(u));fa[find(u)]=find(v);e[i].w=-u;}T1.dfs1(find(1));sort(e+1,e+n);for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<n;i++){int u=e[i].u,v=e[i].v;T2.e[u].pb(find(v));fa[find(v)]=find(u);}T2.dfs2(find(1));cout<<ans;return 0;
}
}
int main(){return asbt::main();}
D. 虚树
原