互测2
A. 游行
发现可以转化成最小点覆盖，每条路径不覆盖起点
没有覆盖的点产生 \(C\) 的贡献
于是两点之间的边权连最短路，用 \(EK\) 跑费用流
跑出覆盖 \(i\) 个点的最小代价
然后询问的时候可以二分也可以直接扫一遍，找出最小的答案
Code
#include
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,Q,ans,C,S,T,now;
int head[510],ver[130000],cost[130000],to[130000],edge[130000],tot=1;
int f[510][510];
int c[510],dis[510],mf[510],pre[510],q[130000],h,t;
bool inq[510];
inline void add(int x,int y,int z,int w){
ver[++tot]=y;edge[tot]=z;cost[tot]= w;to[tot]=head[x];head[x]=tot;
ver[++tot]=x;edge[tot]=0;cost[tot]=-w;to[tot]=head[y];head[y]=tot;
}
inline bool spfa(){
for(int i=1;i<=T;i++) dis[i]=inf,inq[i]=0;
dis[S]=0;q[h=t=1]=S;mf[S]=inf;inq[S]=1;
while(h<=t){
int x=q[h++];inq[x]=0;
for(int i=head[x];i;i=to[i]) if(edge[i]){
int y=ver[i];
if(dis[y]>dis[x]+cost[i]){
dis[y]=dis[x]+cost[i];
mf[y]=min(mf[x],edge[i]);pre[y]=i;
if(!inq[y]) inq[q[++t]=y]=1;
}
}
}
return dis[T]!=inf;
}
inline void ek(){
int x=T;
while(x!=S){
int i=pre[x];
edge[i]-=mf[T];edge[i^1]+=mf[T];x=ver[i^1];
}
now++;c[now]=c[now-1]+mf[T]*dis[T];
}
inline void solve(){
ans=inf;for(int i=0;i<=now;i++) ans=min(ans,c[i]+C*(n-i));
printf("%lld\n",ans);
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read(),m=read(),Q=read();memset(f,0x3f,sizeof(f));S=n+n+1,T=n+n+2;
for(int i=1,x,y,z;i<=m;i++){x=read(),y=read(),z=read();f[x][y]=min(f[x][y],z);}
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int i=1;i<=n;i++) add(S,i,1,0),add(i+n,T,1,0);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) add(i,j+n,1,f[i][j]);
while(spfa()) ek();
for(int i=1,l,r;i<=Q;i++){C=read();solve();}
return 0;
}
B. 暴力题
推式子懒得写，直接给出最后的（默认 \(n
\(\sum\limits_{T=1}^n\sum\limits_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})\sum\limits_{i=1}^{n/T}\varphi(iT)\sum\limits_{j=1}^{m/T}\varphi(jT)\)
预处理出所有的 \(\sum\limits_{d|T}\frac{d}{\varphi(d)}\) 和 \(\sum\limits_{i=1}^{m/T}\varphi(iT)\)
在处理出 \(\sum\limits_{T=1}^x\sum\limits_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})\sum\limits_{i=1}^{y}\varphi(iT)\sum\limits_{j=1}^{z}\varphi(jT)\)
然后对于每次询问把 \(T<\frac{m}{B}\) 的暴力算，剩下的整数分块算
Code
#include
#define int long long
#define rint signed
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int T,n,m;
int f[100010],s[42][42][100010],inv[100010];
vector g[100010];
int prime[100010],phi[100010],mu[100010],cnt;
bool is[100010];
inline void md(int x){x=(x>=mod)?x-mod:x;}
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
return res;
}
inline int G(int x,int y){
if(x<=40) return g[x][y];
int res=0;for(int i=1;i<=y;i++) md(res+=phi[x*i]);return res;
}
inline void solve(){
n=read(),m=read();if(n>m) swap(n,m);
int res=0;
for(int i=1;i<=m/40;i++) (res+=f[i]*g[i][n/i]%mod*g[i][m/i])%=mod;
for(int l=m/40+1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
(res+=(s[n/l][m/l][r]-s[n/l][m/l][l-1]+mod))%=mod;
}
printf("%lld\n",res);
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
phi[1]=mu[1]=1;
for(int i=2;i<=100000;i++){
if(!is[i]) prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=cnt&&i*prime[j]<=100000;j++){
is[i*prime[j]]=1;
if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
for(int i=1;i<=100000;i++) inv[i]=qpow(i,mod-2);
for(int i=1;i<=100000;i++) for(int j=1;i*j<=100000;j++) f[i*j]+=i*inv[phi[i]]%mod*mu[j]%mod;
for(int i=1;i<=100000;i++) md(f[i]=f[i]%mod+mod);
for(int i=1;i<=100000;i++){
g[i].emplace_back(0);
for(int j=1;i*j<=100000;j++){
g[i].emplace_back(0);
g[i][j]=g[i][j-1]+phi[i*j];
}
}
for(int i=1;i<=40;i++) for(int j=1;j<=40;j++) for(int k=1;k<=100000&&k*i<=100000&&k*j<=100000;k++) (s[i][j][k]=s[i][j][k-1]+f[k]*g[k][i]%mod*g[k][j])%=mod;
T=read();while(T--) solve();
return 0;
}
C. 卡常题
分块搞一搞卡卡常就行， \(O(n\sqrt{n}\log n)\) 可过
正解也好写，提前对每块排序，然后直接归并算序列间的逆序对数就行
就是把树状数组替换掉
答案要开 \(long long\)
Code
#include
//#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,typ;
long long lst;
int a[100001],b[100001],bl[100001];
int BIT[100001];
int le[646],ri[646];
int sum[100001][646],sum2[100001][646],bsum[646][646],S[646];
bool vis[100001];
inline bool cmp1(int x,int y){return a[x]>a[y];}
inline bool cmp2(int x,int y){return a[x]>1;
if(pos<=mid){for(int i=pos;i>=le[bl[pos]];i--) res+=vis[i];}
else{res=S[bl[pos]];for(int i=pos;i<=ri[bl[pos]];i++) res-=vis[i];}
vis[pos]=1;S[bl[pos]]++;sum[pos][bl[pos]]=res;bsum[bl[pos]][bl[pos]]+=res;
for(int i=bl[pos]-1;i;i--){res+=S[i];sum[pos][i]=res;bsum[bl[pos]][i]+=res;}
}
void insc(int pos){
int res=0,mid=(le[bl[pos]]+ri[bl[pos]])>>1;
if(pos<=mid){res=S[bl[pos]];for(int i=pos;i>=le[bl[pos]];i--) res-=vis[i];}
else{for(int i=pos;i<=ri[bl[pos]];i++) res+=vis[i];}
vis[pos]=1;S[bl[pos]]++;sum2[pos][bl[pos]]=res;
for(int i=bl[pos]+1;i<=bl[n];i++){res+=S[i];sum2[pos][i]=res;}
}
long long queryb(int l,int r){
long long res=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++){res+=query(a[i]);ins(a[i]);}
for(int i=l;i<=r;i++){del(a[i]);}
return res;
}
for(int i=r;i>=le[bl[r]];i--) res+=sum[i][bl[l]+1];
for(int i=l;i<=ri[bl[l]];i++) res+=sum2[i][bl[r]-1];
for(int i=bl[l]+1;i<=bl[r]-1;i++) res+=bsum[i][bl[l]+1];
for(int i=l;i<=ri[bl[l]];i++) ins(a[i]);
for(int i=le[bl[r]];i<=r;i++) res+=query(a[i]);
for(int i=l;i<=ri[bl[l]];i++) del(a[i]);
return res;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n=read(),m=read(),typ=read();
for(int i=1;i<=n;i++) a[i]=read(),bl[i]=(i-1)/155+1;
for(int i=1;i<=bl[n];i++) le[i]=(i-1)*155+1,ri[i]=min(155*i,n);
for(int i=1;i<=n;i++) b[i]=i;sort(b+1,b+1+n,cmp1);for(int i=1;i<=n;i++) insb(b[i]);
memset(vis,0,sizeof(vis));memset(S,0,sizeof(S));
sort(b+1,b+1+n,cmp2);for(int i=1;i<=n;i++) insc(b[i]);
for(int i=1,l,r;i<=m;i++){
l=read()^(lst*typ),r=read()^(lst*typ);
printf("%lld\n",lst=queryb(l,r));
}
return 0;
}