Codeforces Round 879 (Div. 2)

D. Survey in Class

题意

学生 $i$ 看过编号在 $[l_i,r_i]$ 范围内的书，初始能力值为 $0$。老师可以选择一些书提问，每本书只能提问一次。看过这本书的学生能力值加一，没看过的能力值减一。问可能得到的最大能力值与最小能力值的差是多少。

题解

我们两两进行考虑，即钦定其中一个是最大能力值，另一个是最小能力值。将每位学生看过的书编号看成是一条线段，那么每两位学生之间可能有以下三种关系

• 相离，如 $[1,3],[5,5]$
• 相交，如 $[1,4],[3,5]$
• 包含，如 $[1,5],[2,4]$

记两条线段为 $[l_i,r_i],[l_j,r_j]$。对于第一种情况，贡献为 $2\times \max(r_i-l_i+1,r_j-l_j+1)$。对于第二种情况，贡献为 $2\times \max(l_j-l_i,r_j-r_i)$。对于第三种情况，贡献为 $2\times |(r_j-l_j+1)-(r_i-l_i+1)|$。

不难发现前两种情况可以合并处理：对于每一条线段，我们希望它成为能力值最大的，那么它的覆盖的书籍需要尽可能不被其它线段覆盖。所以只需要考虑右端点最小的线段和左端点最大的线段即可。

对于第三种情况。可以枚举左端点，将线段依次加入。用线段树维护右端点固定时区间长度的最大值，每次用右端点最大的去更新，用右端点最小的去查询。

但其实不用这么麻烦，我们只需要找到长度最长的线段和最短的线段，用 $2\times(\mathrm{max\_len}-\mathrm{min\_len})$ 更新答案即可。因为如果它们不是包含关系，得到的结果只会更大，并且在前两种情况已经处理出来了，所以对答案不会有影响。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int l[maxn],r[maxn];
int len,c[2*maxn];
int rk(int x){return lower_bound(c+1,c+len+1,x)-c;}
vector<int> v[2*maxn];
int tr2[8*maxn],tag2[8*maxn];
void build(int l,int r,int p)
{
    tr2[p]=tag2[p]=0;
	if(l==r) 
    {
        return;
    } 
	int m=l+((r-l)>>1);
	build(l,m,p*2),build(m+1,r,p*2+1);
	tr2[p]=max(tr2[p*2],tr2[p*2+1]);
}
void pushdown2(int p)
{
    tr2[p*2]=max(tr2[p*2],tag2[p]),tr2[p*2+1]=max(tr2[p*2+1],tag2[p]);
    tag2[p*2]=max(tag2[p*2],tag2[p]),tag2[p*2+1]=max(tag2[p*2+1],tag2[p]);
    tag2[p]=0;   
}
void update2(int ul,int ur,int k,int l,int r,int p)
{
	if(ul<=l&&ur>=r)
    {
        tr2[p]=max(tr2[p],k),tag2[p]=max(tag2[p],k);
        return ;
    }
    int m=l+((r-l)>>1);
    if(tag2[p]&&l!=r) pushdown2(p);
    if(ul<=m) update2(ul,ur,k,l,m,p*2);
    if(ur>m) update2(ul,ur,k,m+1,r,p*2+1);
    tr2[p]=max(tr2[p*2],tr2[p*2+1]);
}
int query2(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return tr2[p];
    int m=l+((r-l)>>1);
    if(tag2[p]) pushdown2(p);
    int mx=-0x3f3f3f3f;
	if(ql<=m) mx=max(mx,query2(ql,qr,l,m,p*2));
	if(qr>m) mx=max(mx,query2(ql,qr,m+1,r,p*2+1));
	return mx;    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        for(int i=1;i<=2*n;i++) v[i].clear();
        for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
        int mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
        for(int i=1;i<=n;i++) mn=min(mn,r[i]),mx=max(mx,l[i]);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(mn<l[i]) ans=max(ans,2*(r[i]-l[i]+1));
            else ans=max(ans,2*(r[i]-mn));
            if(mx>r[i]) ans=max(ans,2*(r[i]-l[i]+1));
            else ans=max(ans,2*(mx-l[i]));
        }
        for(int i=1;i<=n;i++) c[i*2-1]=l[i],c[i*2]=r[i];
        sort(c+1,c+2*n+1);
        len=unique(c+1,c+2*n+1)-c-1;
        for(int i=1;i<=n;i++) v[rk(l[i])].push_back(r[i]); 
        build(1,2*n,1);      
        for(int i=1;i<=2*n;i++)
        {
            if(v[i].empty()) continue;
            sort(v[i].begin(),v[i].end());
            int u=v[i].back();
            update2(1,rk(u),u-c[i]+1,1,2*n,1);
            int j=v[i].front();
            ans=max(ans,2*(query2(rk(j),2*n,1,2*n,1)-(j-c[i]+1)));
        }
        cout<<ans<<'\n';
    }
    return 0;
}

E. MEX of LCM

题意

给定一个数组 $a$，求最小的正整数 $x$ 使得数组中不存在一个子段的 $\mathrm{lcm}$ 为 $x$。

题解

因为数组的子段至多有 $\dfrac{n(n+1)}{2}$ 个，所以答案肯定不超过 $n^2$，对于 $\mathrm{lcm}$ 超过 $n^2$ 的子段也不用考虑了。考虑子段 $a_l,a_{l+1},\cdots,a_r$ 和 $a_l,a_{l+1},\cdots,a_r,a_{r+1}$。若后者的 $\mathrm{lcm}$ 大于前者，则其至少增加两倍。所以以 $a_i$ 为左端点的子段，其不超过 $n^2$ 的本质不同的 $\mathrm{lcm}$ 是 $\log$ 级别的，直接暴力枚举就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const ll uplimit=9e10;
int a[maxn];
ll lcm(ll a,ll b) {return a*b/__gcd(a,b);}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        set<ll> s,pre;
        for(int i=1;i<=n;i++)
        {
            set<ll> cur;
            s.insert(a[i]),cur.insert(a[i]);
            for(auto j:pre)
            {
                ll k=lcm(a[i],j);
                if(k<uplimit)
                {
                    s.insert(k);
                    cur.insert(k);
                }
            }
            pre=cur;
        }
        for(int i=1;;i++)
        {
            if(s.find(i)==s.end())
            {
                cout<<i<<'\n';
                break;
            }
        }
    }
    return 0;
}

F. Typewriter

题意

给定 $n$ 个数 $p_1,p_2,...,p_n$ 和一个容量为 $1$ 的移动窗口。初始窗口停靠在位置 $1$。每次可以执行以下操作：

1. 若停靠位置 $i$ 有数 $p_i$ 且窗口为空，将 $p_i$ 装入窗口。
2. 若停靠位置 $i$ 没有数且窗口为空，将窗口内的数放入位置 $i$。
3. 若停靠位置 $i$ 有数且窗口非空，交换这两个数。
4. 窗口由位置 $i$ 移动到 $i+1$。
5. 窗口回到位置 $1$。

同时，给出 $q$ 次询问，每次询问有以下三种类型：

1. 将所有数向左移动 $k$ 。
2. 将所有数向右移动 $k$。
3. 将整个序列翻转。

对每次询问前后，输出想要将序列还原成 $1,2,\cdots,n$ 所需要的操作 $5$ 次数最小值。

题解

先不考虑询问：考虑将 $i$ 向 $p_i$ 连一条有向边。对于每一个环进行考虑，若环上的边 $(u,v)$ 满足 $u>v$ 则需要一次操作 $5$。也就是所有的 $i>p_i$ 的位置都会对答案作出贡献。

对于询问 $1$ 和询问 $2$，最多有 $n$ 种不同的情况，可以预处理出来。对于询问 $3$，只需要将序列翻转再处理一遍即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
int n,p[maxn],rp[maxn];
int c1[maxn],c2[maxn],ans[2][maxn];
void solve(int *a,int *c,int *sum)
{
    for(int i=1;i<=n;i++)
    {
        sum[0]+=(a[i]<i);
        if(i<=a[i]) c[a[i]-i+1]++,c[n-i+1]--;
        else c[n-i+1]--,c[n-i+a[i]+1]++;
    }
    for(int i=1;i<n;i++) sum[i]=sum[i-1]+c[i];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i],rp[n-i+1]=p[i];
    solve(p,c1,ans[0]),solve(rp,c2,ans[1]);
    int op=0,cur=0;
    cout<<ans[op][cur]<<'\n';
    int q;cin>>q;
    while(q--)
    {
        int t;cin>>t;
        if(t==1) 
        {
            int k;cin>>k;
            cur=(cur-k+n)%n;
        }
        else if(t==2)
        {
            int k;cin>>k;
            cur=(cur+k)%n;
        }
        else 
        {
            op^=1;
            cur=(n-cur)%n;
        }
        cout<<ans[op][cur]<<'\n';
    }
    return 0;
}