link
DMY Round 50 D-E
[R50D]三元组2
link.
妙妙题，不是很难，但需要想清楚。
经典套路，枚举中间？ 其实不好做。
考虑枚举\(i\)或\(k\)，这里为枚举\(k\)。
可以在\(b\)序列上二分出区间\([c_k-d,c_k]\)。
对于此区间内的每一个\(b_j\)，统计满足一下两个条件的\(a_i\)的个数：
1.\(a_i\ \leq \ b_j\)；
2.\(a_i\ \geq \ c_k-d\)。
可以发现第 2 项为定值，与\(j\)无关。
第 1 项可以预处理，对于每一个\(b_j\)，二分出满足\(a_i\ \leq \ b_j\)的\(i\)的数量，然后做前缀和。
用第 1 项的总和 - 第 2 项的总和即为\(c_k\)的答案。
时间复杂度：\(O(nlogn)\).
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 1e10
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=2e5+5,M=4e4;
const int mod=998244353;
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*10+ch-'0',ch=getchar();return x*f;
}
int n,m,k,d;
int a[N],b[N],c[N],sum[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m>>k>>d;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=m;i++) cin>>b[i];sort(b+1,b+m+1);for(int i=1;i<=k;i++) cin>>c[i];sort(c+1,c+k+1);for(int i=1;i<=m;i++){int pos=upper_bound(a+1,a+n+1,b[i])-a-1;sum[i]=sum[i-1]+pos;}int ans=0;for(int i=1;i<=k;i++){int L=lower_bound(b+1,b+m+1,c[i]-d)-b;int R=upper_bound(b+1,b+m+1,c[i])-b-1;int now=sum[R]-sum[L-1];int pos=lower_bound(a+1,a+n+1,c[i]-d)-a-1;ans=ans+now-pos*(R-L+1);
// cout<<now<<' '<<pos<<' '<<(R-L+1)<<"---\n";}cout<<ans<<'\n';return 0;
}[R50E]数据同步
link.
可以发现，令\(i\)向\(X_i\)连边，一定会形成一个基环森林。
对于一颗基环树，可以发现只有环上有奇数个元素时，才会需要代价。
而代价一定会贪心地选择环上最小的\(C_i\)。
而找环，方法多种多样，std使用拓扑排序找环。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 1e10
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=2e5+5,M=4e4;
const int mod=998244353;
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*10+ch-'0',ch=getchar();return x*f;
}
bool c[N],vis[N];
int n,p[N],val[N],ans;
int f[N],siz[N],Min[N],d[N];
vector<int>E[N];
inline int find(int x){if(x==f[x]) return x;return f[x]=find(f[x]);
}
inline void merge(int x,int y){int xx=find(x),yy=find(y);if(xx==yy) return ;if(siz[xx]>siz[yy]) swap(xx,yy);f[xx]=yy,siz[yy]+=siz[xx];Min[yy]=min(Min[yy],Min[xx]);return ;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>p[i]>>val[i];f[i]=i,siz[i]=1,Min[i]=val[i];E[i].push_back(p[i]);d[p[i]]++;}queue<int>q;for(int i=1;i<=n;i++)if(!d[i]) q.push(i);while(!q.empty()){int u=q.front(); q.pop();for(auto to : E[u]){d[to]--;if(!d[to]) q.push(to);}} for(int i=1;i<=n;i++)if(d[i]) merge(i,p[i]);else vis[i]=1;for(int i=1;i<=n;i++){if(!vis[find(i)] && siz[find(i)]&1){vis[find(i)]=1;ans+=Min[find(i)];}}cout<<ans;return 0;
}