Codeforces Round #813 (Div. 2)
D. Empty Graph
分析
我们通过简单的分析，可以得出一个结论，我们的答案一定来自于相邻两个点的位置或是最小值的两倍。
我们考虑如何给构造。
第一种
我们希望最终的最大值来自于u直接走到v，根据刚才的结论答案就是min(a[i], a[i + 1])，那么他们之间一定存在一个最小值。因此我们要用一次操作把其中一个变成无穷大，因此最终我们一定能取到最大权值的那个数。剩余的k - 1次我们只需要把最小的那k - 1次变成正无穷即可。
第二种
我们希望最终的最大值来自于2 * 最小权值。我们要尽量抬高最小的值，因此我们只需要将最小k个权值变成无穷大即可。那么最终答案就来自于2 * minv并且枚举一遍相邻位置上的最小值min(a[i], a[i + 1])即可。
我们直接看代码。
AC_code
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10,M = N*2,INF = 1e9;
void solve() {
int n,k;cin>>n>>k;
vector<int> a(n);
vector<PII> p(n);
for(int i=0;i<n;i++) cin>>a[i],p[i] = {a[i],i};
sort(p.begin(),p.end());
for(int i=0;i<k-1;i++)
{
p[i].first = INF;
a[p[i].second] = INF;
}
sort(p.begin(),p.end());
int res1 = INF,res2 = INF;
res1 = min(res1,p[0].first*2);
res1 = min(res1,p[n-1].first);
p[0].first = INF;a[p[0].second] = INF;
sort(p.begin(),p.end());
res2 = min(res2,p[0].first*2);
int tmp = -INF;
for(int i=0;i<n;i++) a[p[i].second] = p[i].first;
for(int i=0;i<n-1;i++) tmp = max(tmp,min(a[i],a[i+1]));
res2 = min(tmp,res2);
cout<<max(res1,res2)<<"\n";
}
int main()
{
ios;
int T=1;
cin>>T;
while(T -- ) {
solve();
}
return 0;
}
E2. LCM Sum (hard version)
题目大意
有t组样例，每组给定一个区间[l,r]\(（r\leq2*10^5）\)。问满足\(l\leq i\leq j \leq k \leq r,lcm(i,j,k)\geq i+j+k\)的三元组数目。
easy version中\(t\leq5\),hard version中\(t\leq 10^5\)。
分析
如果直接去分析\(lcm(i,j,k)\geq i + j + k\)，其并不好求。我们考虑逆向求，\(lcm(i,j,k)<i+j+k<3k\)。
此时，只有两种情况。lcm(i,j,k)=k与lcm(i,j,k)=2k。
对于第一种情况，则不等式成立当且i与j都为k的因子。
第二种情况，不等式成立，当且仅当i和j都为2k的因子，且需要i+j>k*（这里是因为\(lcm(i,j,k)=2k<i+j+k\)）。
先计算每个k在[l,r]中有多少个小于k的因子，记作f[k]。
枚举k，第一种情况答案等于从f[k]个因子中随机任取两个的因子，即为(f[k]-1)*f[k]/2。
此时我们可以推导出来，j只能等于2k/3，而i只能等于k/2或者2k/5。
因为\(k/2<j<k\)，同时又必须是2k的因子，因此设j=2k/p。
所以可以推出，2<p<4，即p只能等于3，j=2k/3。
而i+j>k可知，\(i>\frac{1}{3}k\)，又因i为2k因子，则设i = 2k/q。
则我们可以推得，3<q<6，因此q只能等于4或5，此时i=k/2或者2k/5。
则第二种减去这些情况即可。
对于easy version我们考虑直接暴力枚举即可。
但是对于hard version。若我们每个询问都暴力枚举，铁炸无疑。同时考虑没有修改，我们考虑离线。
我们发现一个位置其对后面的其所有倍数有影响，因此我们只需要从后向前枚举，枚举到当前点时，我们直接考虑将该点对后面的点的影响加上。
同时维护当前点作为i时，对后面合法的j的影响即可。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
struct Node
{
int l,r,id;
bool operator<(const Node &W) const
{
return l>W.l;
}
}query[N];
LL tr[N];
LL cnt[N],ans[N];
vector<vector<int>> ks(N);
int q;
void add(int x,int c)
{
while(x<N)
{
tr[x] += c;
x += x & -x;
}
}
LL sum(int x)
{
LL res = 0;
while(x)
{
res += tr[x];
x -= x & -x;
}
return res;
}
int main()
{
ios;cin>>q;
for(int i=0;i<q;i++)
{
int l,r;cin>>l>>r;
query[i] = {l,r,i};
int n = r - l + 1;
ans[i] = 1ll*n*(n-1)*(n-2)/6;
}
sort(query,query+q);
int now = N;
for(int i=0;i<q;i++)
{
int l = query[i].l,r = query[i].r,id = query[i].id;
while(now>l)
{
now--;
if(now%6==0) ks[now/2].push_back(now);
if(now%15==0) ks[now/5*2].push_back(now);
for(int j=2*now;j<N;j+=now) add(j,cnt[j]++);
for(auto j:ks[now]) add(j,1);
}
ans[id] -= sum(r);
}
for(int i=0;i<q;i++) cout<<ans[i]<<'\n';
return 0;
}