D. Empty Graph

思路：
$ans = \max\limits_{1 \le i \le n - 1}{\operatorname{d}(i, i + 1)} = \min \left( \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}, 2 \cdot \min(a_1 \ldots a_n) \right)$

所有最短路的上界是$2*minv$。

因此每次我们二分答案的时候首先必须对所有满足$2 * a_i <res$的非法数字进行操作.

如果操作不够说明答案非法 继续二分即可.

如果操作是够的 但是操作会有剩余部分.

分为三种情况:

1.$k=0$:此时直接检查操作后的序列答案是否$>= res$即可.
2.$k=1$:此时可以直接将$maxv$相邻的数字变成$1e9$,判断$maxv>=res$/
3.$k>1$:此时直接将任意相邻两项取成$1e9$也能够直接取到$res$直接返回真.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<int>a;
int n,k;
int res=1e9;
bool check(int x)
{
        int cnt=0;
        vector<int>b(n+1);
        for(int i=1;i<=n;i++)
        {
                if(a[i]*2<x)b[i]=res,cnt++;
                else b[i]=a[i];
        }//先处理下非法的情况 
        int minv=*min_element(b.begin()+1,b.end());
        int maxv=*max_element(b.begin()+1,b.end());
        if(k-cnt<0)return false;//分类讨论一下 
        if(k-cnt==0)
        {
                int ans=0;
                for(int i=1;i+1<=n;i++)ans=max(ans,min({b[i],b[i+1],2*minv}));
                return ans>=x;
        }else if(k-cnt==1)return maxv>=x;
        else return true;//1e9>=x;
}
void solve()
{
       cin>>n>>k;
       a=vector<int>(n+1,0);
       for(int i=1;i<=n;i++)cin>>a[i];
       int l=1,r=1e9;//二分答案 
       while(l<r)
       {
               int mid=l+r+1>>1;
               if(check(mid))l=mid;
               else r=mid-1;
       }
       cout<<l<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

E1. LCM Sum (easy version)

思路:

由于直接求,$\operatorname{lcm}(i,j,k) \ge i + j + k$ 是非常麻烦的

而且满足这样不等式的三元组数量十分庞大.

因此我们转换思路不妨先求出:$\operatorname{lcm}(i,j,k) \lt i + j + k$.

每一个询问的答案就是:$C_{r-l+1}^{3} <=> \frac { (r-l+1) * (r-l) * (r-l-1) } {6}$

推导一下公式可以知道,$lcm(i , j , k)$ 一定是 $k$的倍数 又由于 $( i ,j ) < k$

因此 $lcm(i ,j ,k) = k$ 或者 $lcm( i ,j , k) = 2 *k 且 i + j >k$

由于简单版的询问非常的少,因此我们暴力的枚举所有区间内$2 * k$的因子即可.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<int>prime[2*N];
void solve()
{
       int l,r;
       cin>>l>>r;
       ll ans=(ll)(r-l+1)*(r-l)*(r-l-1)/6;
       for(int k=l+2;k<=r;k++)
       {
               for(int i=0;i<prime[2*k].size();i++)
               {
                       int x=prime[2*k][i];//枚举i
                       if(x>=k||x<l)continue;//i<j<k
                       for(int j=i+1;j<prime[2*k].size();j++)
                       {
                               int y=prime[2*k][j];
                               if(y>=k||y<=x)continue;//i<j<k
                               if( k % x== 0 && k % y== 0 || ( x + y ) > k )ans--;
                       }
               }
       }
       cout<<ans<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
  //      freopen("test.in","r",stdin);
        for(int i=1;i<=N;i++)
         for(int j=i;j<=N*2-1;j+=i)prime[j].push_back(i);
         //预处理出因数 
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

E2. LCM Sum (hard version)

思路:
在简单版的基础上,困难版本加大了询问量.

因此我们不能暴力的对每一个区间的$2 * k$的因子进行枚举了.

但是我们可以离线的处理所有的询问:对于所有询问,我们固定$k$

同时从小到大枚举所有因子,利用树状数组 维护每一个三元组当前的贡献.

每次枚举结束的时候 对每一个$k$所对应的询问单独处理即可.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<int>prime[2*N];
ll tr[N];
int lowbit(int x)
{
        return x&-x;
}
void add(int x,ll c)
{
        for(int i=x;i<=200000;i+=lowbit(i))tr[i]+=c;
}
int query(int l,int r)
{
        ll res=0;
        for(int i=r;i;i-=lowbit(i))res+=tr[i];
        for(int i=l;i;i-=lowbit(i))res-=tr[i];
        return res; 
}
struct node{
        int l,id;
};
vector<node>a[N];
ll ans[N];
void solve()
{
       int n;cin>>n;
       for(int i=1;i<=n;i++)
       {
               int l,r;
               cin>>l>>r;
               a[r].push_back({l,i});
               ll x=r-l+1;
               ans[i]=x*(x-1)*(x-2)/6;
       }

       for(int k=1;k<=200000;k++)
       {
                for(int i=0;i<prime[2*k].size();i++)
                {
                        int x=prime[2*k][i];
                        if(x>=k)break;
                        int cnt=0;
                        for(int j=i+1;j<prime[2*k].size();j++)
                        {
                                int y=prime[2*k][j];
                                if(y>=k)break;
                                if(k%x==0&&k%y==0||(x+y)>k)cnt++;
                        }
                        add(x,cnt);
                }
                for(auto c:a[k])ans[c.id]-=query(c.l-1,k);
       }
       for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        for(int i=1;i<=200000;i++)
         for(int j=i;j<=400000;j+=i)prime[j].push_back(i);
         //预处理出因数 
        solve();
        return 0;
}