这次的题解超迟到了。
C - Odd One Subsequence
用一个桶记录 \(i\) 出现的次数 \(c_i\)。
则构造三元组相当于从一个桶中任选 \(2\) 个，再从另一个桶中选 \(1\) 个。
所以答案即为：
\[\sum_i \binom{c_i}{2}\times (n-c_i)
\]
可以 \(O(n)\) 做。代码用的 map 所以是 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,ans;
map<int,int> c;
signed main(){cin>>n;for(int i=1,x;i<=n;i++){cin>>x,c[x]++;}for(auto i:c){int x=i.second;ans+=x*(x-1)/2*(n-x);}cout<<ans<<"\n";return 0;
}
D - On AtCoder Conference
考虑倍增。记 \(f[i][j]\) 为从 \(i\) 开始跳 \(2^j\) 步经过的人数（算开头不算结尾），每次查询 \(\log\) 地跳就行。
但是 \(m\) 有 \(10^{12}\)，必须先离散化。
离散化后第 \(i\) 个点算得的贡献，放在原图上需要乘上 \(i\) 和前一个人的距离再累加。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,c,f[N][20],ans,a[N],b[N],tn;
signed main(){cin>>n>>m>>c;for(int i=0;i<n;i++){cin>>a[i];b[tn++]=a[i];}sort(b,b+tn),tn=unique(b,b+tn)-b;for(int i=0;i<n;i++){a[i]=lower_bound(b,b+tn,a[i])-b;f[a[i]][0]++;}for(int i=1;i<20;i++){for(int j=0;j<tn;j++){f[j][i]=f[j][i-1]+f[(j+(1<<(i-1)))%tn][i-1];}}for(int i=0;i<tn;i++){int cur=i,s=0,dis=(i?b[i]-b[i-1]:m-b[tn-1]+b[i]);for(int j=19;~j;j--){if(s+f[cur][j]<c){s+=f[cur][j];(cur+=(1<<j))%=tn;}}s+=f[cur][0];ans+=s*dis;}cout<<ans<<"\n";return 0;
}
E - Hit and Away
答案显然是每个 D 点出发到达 S 点的最短路 + 次短路之和。
求最短路和次短路，我们可以直接使用 BFS（因为边权都是 \(1\)）。初始时将所有点压入队列，为了避免一个点被另一个点同时转移最短路和次短路，我们记录下最短路和次短路的来源，保证它们不同即可。
时间复杂度 \(O(n+m)\)。
点击查看代码
#include<bits/stdc++.h>
#define PII pair<int,int>
#define eb emplace_back
using namespace std;
const int N=2e5+5,M=2e5+5;
struct Path{int o,u,d;};
queue<Path> q;
int n,m,f[N][2],d[N][2];
string s;
vector<int> G[N];
inline void uadd(int u,int v){G[u].eb(v),G[v].eb(u);}
signed main(){cin>>n>>m;for(int i=1,u,v;i<=m;i++) cin>>u>>v,uadd(u,v);cin>>s,s=' '+s;memset(f,-1,sizeof f);for(int i=1;i<=n;i++){if(s[i]=='S') f[i][0]=i,q.push({i,i,0});}while(!q.empty()){int o=q.front().o,u=q.front().u,td=q.front().d;q.pop();for(int i:G[u]){if(f[i][0]==-1){f[i][0]=o,d[i][0]=td+1;q.push({o,i,td+1});}else if(f[i][1]==-1&&f[i][0]!=o){f[i][1]=o,d[i][1]=td+1;q.push({o,i,td+1});}}}for(int i=1;i<=n;i++) if(s[i]=='D')cout<<d[i][0]+d[i][1]<<"\n";return 0;
}
F - Shortest Path Query
两个连续区间的答案是可合并的。
考虑在线段树上，用 \(d_x[i,j]\) 表示对于 \(x\) 管辖的区间 \([l,r]\)，\((l,i)\) 走到 \((r,j)\) 的最短路，则有转移：
\[d_x[i][j]=\max\limits_{k=0}^2(d_l[i][k]+d_r[k][j]+1)
\]
仅需维护单点修改，查询时直接取根节点即可。
时间复杂度 \(O(n+q\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f;
int n,a[N],q;
string s[3];
bitset<N> f;
struct SEG{int d[N<<2][3][3];inline void pushup(int x){memset(d[x],inf,sizeof d[x]);for(int i=0;i<3;i++){for(int j=0;j<3;j++){for(int k=0;k<3;k++){d[x][i][j]=min(d[x][i][j],d[lc][i][k]+d[rc][k][j]+1);}}}}inline void calc(int x,int p){for(int i=0;i<3;i++){bool f=1;for(int j=i;j<3;j++){if(s[j][p]=='#') f=0;d[x][i][j]=d[x][j][i]=(f?j-i:inf);}}}inline void build(int x,int l,int r){if(l==r) return calc(x,l),void();int mid=(l+r)>>1;build(lc,l,mid),build(rc,mid+1,r);pushup(x);}inline void chp(int x,int a,int l,int r){if(l==r) return calc(x,l),void();int mid=(l+r)>>1;if(a<=mid) chp(lc,a,l,mid);else chp(rc,a,mid+1,r);pushup(x);}
}seg;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<3;i++) cin>>s[i],s[i]=' '+s[i];seg.build(1,1,n);cin>>q;int x,y;while(q--){cin>>x>>y,x--;s[x][y]=(s[x][y]=='#'?'.':'#');seg.chp(1,y,1,n);if(seg.d[1][0][2]^inf) cout<<seg.d[1][0][2]<<"\n";else cout<<"-1\n";}return 0;
}
这个好像叫 ddp（动态dp）。