「UOI」 Beginner Contest 002 & Round 4 Tutorial

Crazyouth · 2024-11-25 10:08:08 · 算法·理论

「UOI」 Beginner Contest 002 & Round 4 Tutorial

A

sol

可以观察到，如果存在一位是 1, 2, 3, 4, 6, 7, 8, 9，则它前一位是否有“五入”是可以唯一确定的，这种情况可以枚举一遍得到答案。答案至多有一个。

若所有的 b_i 均是 0 或 5，则可以枚举其中一位是 b_i 还是 (b_i + 9) \bmod 10，然后即可判断。

答案至多有两个，并且两种答案中 a_i 一个为 b_i，一个为 (b_i + 9) \bmod 10，因此加起来不会进位（0 + 9 = 5 + 4 \lt 10）。

乘以 10^n - 1 相当于取循环节。

当然，更简单的方法是，枚举 a_n 是 b_n 还是 (b_n + 9) \bmod 10。

std

#include <iostream>
using namespace std;

#define MAXN 1000006

int n;

int v[MAXN], r[MAXN];

bool check(int l)
{
    int a = l;
    for (int i = n - 1; i; i--)
    {
        a = (v[i] + 10 - (a > 4)) % 10;
    }
    return (l + (a > 4)) % 10 == v[n];
}

void add(int l)
{
    r[n] += l;
    for (int i = n - 1; i; i--)
    {
        r[i] += l = (v[i] + 10 - (l > 4)) % 10;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        r[i] = 0;
    }
    if (check(v[n]))
    {
        add(v[n]);
    }
    if (check((v[n] + 9) % 10))
    {
        add((v[n] + 9) % 10);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << r[i];
    }
    cout << endl;
    return 0;
}

B

sol

挺诈骗的一题啊。

首先询问中我们的目标是把所有数变相等。不难看出实际上是把所有数变为最大值。

考虑变形询问中的操作 2。如果操作 2 选择了区间 [l,r] 且 r-l+1>2，那么你实际上可以通过 r-l 次选择长度为 2 的区间来达到完全等同的效果。比较一下两者代价大小？令 k=r-l+1，前者就是 k^2 的代价，后者则是 2^2\times (k-1)。前者代价减后者代价为 k^2-4k+4=(k-2)^2\ge 0。因此选择长度为 2 的区间一定更优。

此时不难想到，一个数需要变成最大值无非通过反复加一或者与旁边的数组成长为 2 的区间然后进行一次操作 2。因此询问转化为给定 l,r，求 \displaystyle\sum_{i=l}^r \min((\max\limits_{i=l}^ra_i)-a_i,4)。

由于 4 这个数太小了，考虑直接暴力找 mx,mx-1,mx-2,mx-3 在区间的出现数量（当然也不是纯暴力），这样除了这些数以外的数全部都是花费 4 的代价，而这些数分别花费 0,1,2,3 的代价。对于区间找数的方法，容易想到在某种存有出现的下标的容器上二分。但由于有修改操作，所以我们这个容器还需要支持从中间删除数。那么符合这样条件的容器自然是 pbds 中的 tree。由于值域小，我们直接开 2\times 10^5 个 tree，第 i 个存的是 i 在序列中的出现下标。每次查询就使用 order_of_key() 函数做个差分找区间某数的出现次数即可。修改的话，在原 tree 中删除下标 k，再在新 tree 中加入它就行了。

std

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=200010;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr[N];
int mx[N<<2],a[N],mxcnt[4];
void build(int s,int t,int p)
{
    if(s==t)
    {
        mx[p]=a[s];
        return;
    }
    int m=s+t>>1;
    build(s,m,p<<1);build(m+1,t,p<<1|1);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
void upd(int k,int s,int t,int p,int c)
{
    if(s==t)
    {
        mx[p]=c;
        return;
    }
    int m=s+t>>1;
    if(k<=m) upd(k,s,m,p<<1,c);
    else upd(k,m+1,t,p<<1|1,c);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int qry(int l,int r,int s,int t,int p)
{
    if(l<=s&&t<=r) return mx[p];
    int m=s+t>>1,ans=0;
    if(l<=m) ans=qry(l,r,s,m,p<<1);
    if(r>m) ans=max(ans,qry(l,r,m+1,t,p<<1|1));
    return ans;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],tr[a[i]].insert(i);
    build(1,n,1);
    while(q--)
    {
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1)
        {
            upd(x,1,n,1,y);
            tr[a[x]].erase(x);
            a[x]=y;
            tr[a[x]].insert(x);
        }
        else
        {
            int mx=qry(x,y,1,n,1);
            int ans=0;
            for(int i=0;i<4;i++)
            {
                if(mx-i>0&&tr[mx-i].size())
                mxcnt[i]=(tr[mx-i].order_of_key(y+1)-tr[mx-i].order_of_key(x));
                else
                mxcnt[i]=0;
                ans+=mxcnt[i]*i;
            }
            cout<<ans+(y-x+1-mxcnt[0]-mxcnt[1]-mxcnt[2]-mxcnt[3])*4<<'\n';
        }
    }
}

C

sol by cosf

下面用 [l, r] 表示点 l, l + 1, \dots, r 组成的点集，\text{path}(i, j) 表示点 i 到点 j 最短路径经过的点集，\text{dis}(i, j) = |\text{path}(i, j)|。

首先我们先转化题意：

给定一个 n 个点的树，每次询问给定区间 [l, r]，求是否存在一个一个异于 [l, r] 且在 [l, r] 最小连通块中的点 p。

还有一个特例：当 l = r 时，唯一满足的点 p = l，输出 Yes。

不难发现，其必要条件是 [l, r] 中不存在三点共链。除此之外，如果 r \gt l + 1 或者 \text{dis}(l, l + 1) \ge 3，则能反推出 p 的存在性。因此考虑是否存在三点共链。

令 r_i 表示最大的 r，使得点 i, i + 1, \dots, r 中不存在三点共链。显然，[l, r] 不存在三点共链等价于 r \le r_l。并且，r_i 存在单调性。证明：考虑反证，若存在 i \lt j, r_j \lt r_i，则 j, \dots, r_j + 1 中存在三点共链，i, r_i 也必然存在，矛盾。所以我们可以使用双指针来求。

假设当前区间为 [l, r]。我们可以维护两种点权 T_1, T_2。T_1 将 \text{path}(i, i + 1), \forall l \le i \lt r 赋为非零值，T_2 将 i, \forall l \le i \le r 赋为 1。当我们想判断 r + 1 的加入是否会导致三点共链时，只需检查三个东西：

确认不会造成共链后，更新相应的权值即可。它的正确性利用了一个引理：

这个引理的证明可以通过对每一条边计算贡献得到。具体证明就是分类讨论，就不写了。注：如果只有两个点则一定满足，不需要前面三条条件。

因此这部分是可以做到 O(n\log^2 n) 的。最终的复杂度是 O(n\log^2n + q\log n)。当然计算 \text{dis}(l, l + 1) 可以丢到预处理，这样就关于 q 线性了。

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005

using ll = long long;

int n, q;

struct SegTree
{
    struct Tree
    {
        ll s, t;
    } t[MAXN << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

    void pushup(int p)
    {
        t[p].s = t[ls].s + t[rs].s;
    }

    void pushdown(int p, int l, int r)
    {
        if (t[p].t)
        {
            int mid = (l + r) >> 1;
            t[ls].s += (mid - l + 1) * t[p].t;
            t[ls].t += t[p].t;
            t[rs].s += (r - mid) * t[p].t;
            t[rs].t += t[p].t;
            t[p].t = 0;
        }
    }

    void add(int p, int l, int r, int ql, int qr, ll v)
    {
        if (ql <= l && r <= qr)
        {
            t[p].s += v * (r - l + 1);
            t[p].t += v;
            return;
        }
        pushdown(p, l, r);
        int mid = (l + r) >> 1;
        if (mid >= ql)
        {
            add(ls, l, mid, ql, qr, v);
        }
        if (mid < qr)
        {
            add(rs, mid + 1, r, ql, qr, v);
        }
        pushup(p);
    }

    ll query(int p, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return t[p].s;
        }
        pushdown(p, l, r);
        int mid = (l + r) >> 1;
        ll res = 0;
        if (mid >= ql)
        {
            res += query(ls, l, mid, ql, qr);
        }
        if (mid < qr)
        {
            res += query(rs, mid + 1, r, ql, qr);
        }
        return res;
    }
} T1, T2;

vector<int> e[MAXN];

int fa[MAXN], son[MAXN], sz[MAXN], dep[MAXN];
int top[MAXN], rnk[MAXN], dfn[MAXN], idx = 0;

void dfs1(int p, int f)
{
    fa[p] = f;
    sz[p] = 1;
    dep[p] = dep[f] + 1;
    for (int u : e[p])
    {
        if (u == f)
        {
            continue;
        }
        dfs1(u, p);
        sz[p] += sz[u];
        if (sz[u] > sz[son[p]])
        {
            son[p] = u;
        }
    }
}

void dfs2(int p, int t)
{
    top[p] = t;
    dfn[p] = ++idx;
    rnk[idx] = p;
    if (!son[p])
    {
        return;
    }
    dfs2(son[p], t);
    for (int u : e[p])
    {
        if (u == fa[p] || u == son[p])
        {
            continue;
        }
        dfs2(u, u);
    }
}

void addPath(int u, int v, int w, SegTree &t) // 我也不知道我为什么要写三遍 lca
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            swap(u, v);
        }
        t.add(1, 1, n, dfn[top[u]], dfn[u], w);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])
    {
        swap(u, v);
    }
    t.add(1, 1, n, dfn[v], dfn[u], w);
}

ll queryPath(int u, int v, SegTree &t)
{
    ll res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            swap(u, v);
        }
        res += t.query(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])
    {
        swap(u, v);
    }
    return res + t.query(1, 1, n, dfn[v], dfn[u]);
}

int dis(int u, int v)
{
    int res = dep[u] + dep[v];
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            swap(u, v);
        }
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])
    {
        swap(u, v);
    }
    return res - 2 * dep[v];
}

int las[MAXN];

bool check(int l, int r)
{
    if (l + 2 > r)
    {
        return true;
    }
    return !T1.query(1, 1, n, dfn[r], dfn[r]) &&
           (queryPath(r - 1, r, T1) != T1.query(1, 1, n, dfn[r - 1], dfn[r - 1])) &&
           (queryPath(r - 1, r, T2) == T2.query(1, 1, n, dfn[r - 1], dfn[r - 1]));
}

void add(int l, int r, int w)
{
    T2.add(1, 1, n, dfn[r], dfn[r], w);
    if (l && l <= n)
    {
        addPath(l, r, w, T1);
    }
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    for (int l = 1, r = 0; l <= n; l++)
    {
        while (r < n && check(l, r + 1))
        {
            r++;
            add(r - 1, r, 1);
        }
        las[l] = r;
        add(l + 1, l, -1);
    }
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        if (l == r)
        {
            cout << "Yes" << endl;
        }
        else if (r > las[l])
        {
            cout << "No" << endl;
        }
        else if (r > l + 1 || dis(l, r) > 1)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

Another Sol. by Crazyouth

题意：给定 n 个点的树，q 次询问区间 [l,r] 的点有无三点共链（特别地，当区间长度为 2 且这两个点相邻，我们认为存在三点共链）。

题意转化证明见上。

首先我们以 1 为根，然后思考一堆点无三点共链等价于什么。

若这些点互相没有祖先后代关系，显然不会有三点共链。

若有，则有两种情况会存在三点共链。不妨设 p 为这些点中最浅的点中的任意一个，则两种情况分别是：

• 除 p 外的点不全在 p 的一个儿子的子树内。此时 p 的两个不同儿子的子树内的两个点与 p 三点共链。
• 除 p 外的点仍有祖先后代关系，此时有祖先后代关系的点与 p 全部共链。

其余情况下不会有三点共链。

考虑到直接求区间 [l,r] 是否符合这些条件太困难，但是我们可以预处理出每个 l 的最大 r 满足 [l,r] 无三点共链（双指针），因为若 [l,r] 有三点共链，则 [l,r+1] 也有；若 [l,r](l<r) 无三点共链，则 [l,r-1] 也必然没有。

所以只需对一个点集支持加点或删点并判断即可。那么我们分别看看上面这三个条件如何判断。

• 是否有祖先关系：求出对于一个点 i，编号小于 i 的最大编号的 i 的祖先，与大于它的最小祖先是谁，这样就能快速判断区间是否有祖先关系。至于求法，在 dfs 时维护一个 set，到 i 的时候使用 lower_bound() 找一下。
• 最浅的点：在双指针时也维护一个 set，记录 [l,r] 中点的深度，每次找第一个。
• 除最浅点以外的点是否有祖先关系：每次加点就把它的子树和到根路径的点权加一，并在此之前先判断这个点的点权是否大于等于 2（因为除最浅点外有祖先关系等同于存在某个点既有一个后代也有一个祖先）。这里可以把子树点权与到根路径点权分开，分别使用树上差分求得。
• 除最浅点以外的点是否都位于它的一个儿子的子树内：此条件等价于除最浅点以外的点的最近公共祖先是最浅点的后代，反证不难。然后我们发现因为最浅点子树内如果没有点但外面有，那么由于它们存在祖先关系，所以它们加上这个最浅点一定共链，此时那些子树外的点的最近公共祖先不然浅于最浅点；若最浅点子树内有点，若它们不在最浅点的同一个儿子的子树内，则它们的最近公共祖先必然是最浅点的祖先（或最浅点本身），总结一下就是“除最浅点以外的点是否都位于它的一个儿子的子树内”等价于“除最浅点以外的点的最近公共祖先是否深于最浅点”。所以我们可以发现我们要做的只是求剩下的点的最近公共祖先，我们可以把区间拆为 [l,p-1] 与 [p+1,r]（p 为最浅点编号），并求出两个区间的最近公共祖先然后合并。因为最近公共祖先满足结合律，所以可以使用线段树求一个区间的最近公共祖先。

至于判断相邻编号的点是否相邻，枚举一下每一条边并记录即可。

code by Crazyouth

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int fa[N][20],dep[N],lc[N<<2],fac[N],lac[N],ra[N],n,tr[N][2],dfn[N],mxdfn[N],dfncnt=0,vis[N];
vector<int> G[N],num[N];
set<pair<int,int>> stdep,acl;
set<pair<int,int>,greater<pair<int,int>>> acf;
set<int> st;
void upd(int k,int c,int t)//0 ancestor,1 descendant
{
    while(k<=n)
    {
        tr[k][t]+=c;
        k+=k&-k;
    }
}
int qry(int k,int t)
{
    int ret=0;
    while(k)
    {
        ret+=tr[k][t];
        k-=k&-k;
    }
    return ret;
}
void dfs(int u,int f)
{
    if(st.size()&&st.lower_bound(u)!=st.end()) lac[u]=(*st.lower_bound(u));
    else lac[u]=n+1;
    if(st.size()&&st.lower_bound(u)!=st.begin()) fac[u]=(*(prev(st.lower_bound(u))));
    st.insert(u);
    dfn[u]=++dfncnt;
    dep[u]=dep[f]+1;
    fa[u][0]=f;
    for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:G[u])
    {
        if(v==f) continue;
        dfs(v,u);
        mxdfn[u]=max(mxdfn[u],mxdfn[v]);
    }
    st.erase(u);
}
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=17;~i;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=17;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void build(int s=1,int t=n,int p=1)
{
    if(s==t)
    {
        lc[p]=s;
        return;
    }
    int m=s+t>>1;
    build(s,m,p<<1);build(m+1,t,p<<1|1);
    lc[p]=lca(lc[p<<1],lc[p<<1|1]);
}
int qlca(int l,int r,int s=1,int t=n,int p=1)
{
    if(l<=s&&t<=r) return lc[p];
    int m=s+t>>1;
    if(l<=m&&r>m) return lca(qlca(l,r,s,m,p<<1),qlca(l,r,m+1,t,p<<1|1));
    if(l<=m) return qlca(l,r,s,m,p<<1);
    return qlca(l,r,m+1,t,p<<1|1);
}
inline void add(int pt)
{
    acf.insert({fac[pt],pt});
    acl.insert({lac[pt],pt});
    stdep.insert({dep[pt],pt});
}
inline void del(int pt)
{
    acf.erase({fac[pt],pt});
    acl.erase({lac[pt],pt});
    stdep.erase({dep[pt],pt});
}
int main()
{
    int q;
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        for(auto j:G[i])
        if(j==i+1) vis[i]=1;
    }
    dfs(1,0);
    build();
    int pt=1;
    for(int i=1;i<=n;i++)
    {
        while(pt<=n)
        {
            add(pt);
            int now=stdep.begin()->second;
            if(acf.begin()->first>=i||acl.begin()->first<=pt)
            {
                if(qry(mxdfn[pt],0)-qry(dfn[pt]-1,0)+qry(dfn[pt],1)>1)
                {
                    del(pt);
                    ra[i]=--pt;
                    break;
                }
                int nlca;
                if(i==pt) goto E;
                else if(now==i) nlca=qlca(i+1,pt);
                else if(now==pt) nlca=qlca(i,pt-1);
                else nlca=lca(qlca(i,now-1),qlca(now+1,pt));
                if(dep[nlca]<=dep[now])
                {
                    del(pt);
                    ra[i]=--pt;
                    break;
                }
                E:;
            }
            upd(dfn[pt],1,0);upd(dfn[pt],1,1);upd(mxdfn[pt]+1,-1,1);
            pt++;
        }
        if(pt==n+1) ra[i]=n+1;
        del(i);
        upd(dfn[i],-1,0);upd(dfn[i],-1,1);upd(mxdfn[i]+1,1,1);
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<(vis[l]&&r==l+1?"No":(r<=ra[l]?"Yes":"No"))<<'\n';
    }
}

D

sol

我们可以对 i 分类讨论。当 i \ge 2 时，所有的情况都相似，仅有一个系数的差别。

因为 v 只有 M! 种取值，所以我们先化简 E \times M!，最后再除掉就行了。也就是，我们要计算：

1. \sum_{k=1}^V\left(\sum_{v \text{ is a permutation of }[M]}\sum_{j=1}^N[v_k(j) = j]\right)
2. \sum_{k=1}^V\left(\sum_{v \text{ is a permutation of }[M]}\sum_{j=1}^N[v_k(j) = 2j]\right)

由期望的线性性，所有合理范围内的 j 贡献都是一样的。因此，第一个式子中，我们只需算出 1 的贡献，乘上 N 即可。第二个式子中，算出 1 的贡献，乘上 \min\left\{N, \frac{M}{2}\right\} 即可。

第一个式子

定义排列 v 上的一个环为由不同数字组成的序列 \{a_1, a_2, \dots, a_m\}，使得 v(a_1) = a_2, v(a_2) = a_3, \dots, v(a_m) = a_1，其中 m 是环长。可以发现，一个排列总能被唯一划分成若干个环。

那么，当 k 确定时，问题可以描述为：“有多少个排列 v，1 所在的环的长度是 k 的因数”。

则，我们可以枚举环长 m，则对于所有的 m 的倍数 k，它的贡献是 A_{M - 1}^{m - 1} \times (M - m)! = (M - 1)!。这个值和 m 无关，所以 m 的贡献是 \lfloor\frac{V}{m}\rfloor \times (M - 1)!。那么，最终和式的值就是 (M - 1)! \times \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor。

除去 M! 之后，E = \frac{N}{M} \times \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor，可以 O(\sqrt{V}) 计算。

第二个式子

我们只需要 1 和 2 在同一个环即可。当 k 和 m 确定的时候，1 和 2 在环内的相对位置是固定的。将 1 设定为 a_1，若 2 位于 a_j，则 j 就必须满足 j - 1 \equiv k \pmod m。这也说明 k 不能是 m 的倍数。

当 k 不为 m 的倍数时，有 A_{M - 2}^{m - 2} \times (M - m)! = (M - 2)! 个这样的排列。这样的 k 一共有 V -\lfloor\frac{V}{m}\rfloor 个，因此，m 的贡献就是 (M - 2)! \times (V - \lfloor\frac{V}{m}\rfloor)。答案即 \frac{\min\{N, \lfloor\frac{M}{2}\rfloor\}}{M(M - 1)} \times \left(MV - \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor\right)。同样可以在 O(\sqrt{V}) 的时间内算完。

当 i \ge 3 时，这个式子就是 \frac{\min\{N, \lfloor\frac{M}{i}\rfloor\}}{M(M - 1)} \times (MV - \sum{M}_{m - 1}\lfloor\frac{V}{m}\rfloor)，后面的一项和 i 无关，前面的同样在 O(\sqrt{M}) 的复杂度内算出来。

std

#include <iostream>
using namespace std;

#define MOD 998244353ll

using ll = long long;

ll pow(ll b, ll p, ll m)
{
    b %= MOD;
    ll r = 1;
    while (p)
    {
        if (p & 1)
        {
            r = r * b % m;
        }
        b = b * b % m;
        p >>= 1;
    }
    return r;
}

ll inv(ll p)
{
    return pow(p, MOD - 2, MOD);
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, m, v;
        cin >> n >> m >> v;
        ll s = 0;
        for (ll l = 1, r; l <= m && l <= v; l = r + 1)
        {
            r = min(m, v / (v / l));
            s = (s + (r - l + 1) % MOD * (v / l % MOD) % MOD) % MOD;
        }
        ll mid = m / n;
        ll res = (mid - 1) % MOD * (n % MOD) % MOD;
        for (ll l = mid + 1, r; l <= m; l = r + 1)
        {
            r = m / (m / l);
            res = (res + (r - l + 1) % MOD * (m / l % MOD) % MOD) % MOD;
        }
        cout << (res * (((m % MOD) * (v % MOD) % MOD - s + MOD) % MOD) % MOD * inv(m % MOD * ((m - 1) % MOD) % MOD) % MOD + n % MOD * inv(m % MOD) % MOD * s % MOD) % MOD << endl;
    }

    return 0;
}

E

sol

我们先转换题意。令 S 表示原始字符串，即 a_i 个 t_i 连起来的结果。令 s_0 = 0，且 \forall i \in [1, n], s_i = s_{i - 1} + a_i。再令高度函数 h：

令 n_0 = s_n，则 |S| = n_0。原题相当于：

给定 l, r，求一组 (l', r') 使得 [l', r'] \sub [l, r] 且 h_{l'} = h_{r'} = \min_{i \in [l', r']}h_i，并且最大化 r' - l'。

性质一：最优解必然有一个端点 \in s。

证明：考虑反证，令最优解为 (l', r')。由合法括号序列性质得字符串 S_{l'} = \text{'('}, S_{r'} = \text{')'}。再由 l' 非端点得出 S_{l' - 1} = S_{l'} = \text{'('} 以及 l' - 1 \ge l。同理 S_{r' + 1} = \text{')'}, r' + 1 \le r，则 (l' - 1, r' + 1) 为更优的解，矛盾。

于是我们可以分类讨论。

如果只有一个端点 \in s，不妨设为右端点 r'（左端点同理）。跟前面类似，S_{l' - 1} = S_{l'} = \text{'('}，即，该合法子串 (l', r') 不可能通过在其左边添加一个合法子串使其变长，这也说明了此时 l' 的唯一性。设 r' = s_j，则我们只需要求 h_{s_{1 \dots j - 1}} 中最后的小于 h_{r'} 的一项，设为 h_{s_i}，则子串 (l', r') 的长度为 r' - s_i - h_{r'} + h_{s_i}，可以贡献给所有 l \le i\land j \le r 的询问。这是一个二维数点问题，可以在 O(n\log n) 复杂度内解决。

考虑两个端点都 \in s 的情况。我们先钦定右端点为 s_j，我们找到最小的 i，使得 (s_i, s_j) 合法。这可以对 l \le i \land j \le r 的询问做贡献。我们再钦定左端点 s_i，找到最大的 j 使得 (s_i, s_j) 合法。这同样可以给 l \le i \land j \le r 的询问做贡献。这仍然是一个二维数点问题，复杂度 O(n\log n)。

这两类并不能涵盖所有两个端点 \in s 的情况。可以证明，唯一可能漏掉的情况是 h_i, h_j 均为 h_{l\dots r} 最小值。这个也好处理，先对每个区间求其最小值，然后离线下求区间当中最小值出现的最左和最右的位置，相减就是其贡献了，复杂度 O(n\log n)。线性 RMQ 的话那就是 O(n) 的。

令 p_j 表示上述过程中最大的 i，q_i 表示最小的 j。则会漏掉的情况，必定是对于某个 i \in [l, r]，有 p_i \lt l, r \lt q_i。显然有 h_{s_i} 为区间最小值。

当然，如果要求在线的话，用主席树一样可以做到 O(n\log n)。

std

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define MAXN 1000006
#define ls (p << 1)
#define rs (p << 1 | 1)

using ll = long long;

int a[MAXN];

ll h[MAXN], s[MAXN], b[MAXN];
int idx;

int n, m;

struct Query
{
    int l, r, i;
} q[MAXN];
ll res[MAXN];

struct Node
{
    int p;
    ll v;
    int u;
} qr[MAXN << 4];
int la[MAXN];
int qid = 0;

void add(int u, int p, ll v)
{
    qr[++qid] = {p, v, la[u]};
    la[u] = qid;
}

vector<int> ps[MAXN];

template <typename Cmp = less<ll>, ll st = 0>
struct SGT
{
    static Cmp cmp;
    struct Tree
    {
        ll m, t;
    } t[MAXN << 2];

    void pushup(int p)
    {
        t[p].m = max(t[ls].m, t[rs].m, cmp);
    }

    void pushdown(int p)
    {
        if (t[p].t != st)
        {
            t[ls].m = max(t[ls].m, t[p].t, cmp);
            t[ls].t = max(t[ls].t, t[p].t, cmp);
            t[rs].m = max(t[rs].m, t[p].t, cmp);
            t[rs].t = max(t[rs].t, t[p].t, cmp);
            t[p].t = st;
        }
    }

    void build(int p, int l, int r)
    {
        t[p] = {st, st};
        if (l == r)
        {
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }

    void modi(int p, int l, int r, int q, ll v)
    {
        if (l == r)
        {
            t[p].m = max(t[p].m, v, cmp);
            t[p].t = max(t[p].t, v, cmp);
            return;
        }
        pushdown(p);
        int mid = (l + r) >> 1;
        if (mid >= q)
        {
            modi(ls, l, mid, q, v);
        }
        else
        {
            modi(rs, mid + 1, r, q, v);
        }
        pushup(p);
    }

    ll query(int p, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return t[p].m;
        }
        pushdown(p);
        int mid = (l + r) >> 1;
        ll res = st;
        if (mid >= ql)
        {
            res = max(res, query(ls, l, mid, ql, qr), cmp);
        }
        if (mid < qr)
        {
            res = max(res, query(rs, mid + 1, r, ql, qr), cmp);
        }
        return res;
    }
};

SGT<> t1;
SGT<greater<ll>, MAXN> t2;

struct Stack
{
    int s[MAXN];
    int h = 0;
    inline void push_back(int v)
    {
        s[++h] = v;
    }
    inline bool empty()
    {
        return !h;
    }
    inline int back()
    {
        return s[h];
    }
    inline void pop_back()
    {
        h--;
    }
    inline void clear()
    {
        h = 0;
    }
} st;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        char ch;
        cin >> ch;
        if (ch == '(')
        {
            h[i] = h[i - 1] + a[i];
        }
        else
        {
            h[i] = h[i - 1] - a[i];
        }
        b[i + 1] = h[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].l--;
        q[i].i = i;
    }
    sort(q + 1, q + m + 1, [](Query a, Query b)
         { return a.r < b.r; });
    // part 1 & 2: 2d counting
    st.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        // h[has] >= h[cur] => pop
        while (!st.empty() && h[st.back()] >= h[i])
        {
            st.pop_back();
        }
        if (!st.empty())
        {
            int cur = st.back();
            add(i, cur, s[i] - s[cur] - h[i] + h[cur]);
        }
        st.push_back(i);
    }
    st.clear();
    st.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        // h[las] > h[cur] => pop
        while (!st.empty() && h[st.back()] > h[i])
        {
            st.pop_back();
        }
        if (!st.empty() && h[st.back()] == h[i])
        {
            int cur = st.back();
            add(i, cur, s[i] - s[cur]);
        }
        else
        {
            st.push_back(i);
        }
    }
    st.clear();
    st.push_back(n);
    for (int i = n - 1; ~i; i--)
    {
        // h[las] > h[cur] => pop
        while (!st.empty() && h[st.back()] >= h[i])
        {
            st.pop_back();
        }
        if (!st.empty())
        {
            int cur = st.back();
            add(cur, i, s[cur] - s[i] - h[i] + h[cur]);
        }
        st.push_back(i);
    }
    st.clear();
    st.push_back(n);
    for (int i = n - 1; ~i; i--)
    {
        // h[las] > h[cur] => pop
        while (!st.empty() && h[st.back()] > h[i])
        {
            st.pop_back();
        }
        if (!st.empty() && h[st.back()] == h[i])
        {
            int cur = st.back();
            add(cur, i, s[cur] - s[i] - h[i] + h[cur]);
        }
        else
        {
            st.push_back(i);
        }
    }
    t1.build(1, 0, n);
    int p = 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = la[i]; j; j = qr[j].u)
        {
            auto [l, v, u] = qr[j];
            t1.modi(1, 0, n, l, v);
        }
        while (p <= m && q[p].r == i)
        {
            res[q[p].i] = max(res[q[p].i], t1.query(1, 0, n, q[p].l, i));
            p++;
        }
    }
    // part 3: bs on vector & sgt
    sort(b + 1, b + n + 2);
    idx = unique(b + 1, b + n + 2) - b - 1;
    t2.build(1, 0, n);
    for (int i = 0; i <= n; i++)
    {
        h[i] = lower_bound(b + 1, b + idx + 1, h[i]) - b;
        ps[h[i]].push_back(i);
        t2.modi(1, 0, n, i, h[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        auto [l, r, j] = q[i];
        int m = t2.query(1, 0, n, l, r);
        int fi = *lower_bound(ps[m].begin(), ps[m].end(), l);
        int la = *lower_bound(ps[m].rbegin(), ps[m].rend(), r, greater<int>());
        res[j] = max(res[j], s[la] - s[fi]);
    }
    // output
    for (int i = 1; i <= m; i++)
    {
        cout << res[i] << '\n';
    }
    return 0;
}

F

sol

先说结论：极差最大只有 3。具体证明较为复杂，放在最后。这里先放一个计算机验证的链接，代码在题面里，保证在数据范围内有解。

令 \Delta 表示极差，v 表示序列中出现的最小数，a, b, c, d 分别表示 v, (v + 1), (v + 2), (v + 3) 的出现次数，令 \text{sum} 表示 \sum_{i=1}^na_i。

由于太多根号了码起来麻烦，为了简写，(x)_1 = \sqrt[3]{x}, (x)_2 = \sqrt{x}, (x)_3 = \sqrt{x^2}。\text{R}(x) 表示值 x 的值域。

下面的方法给出了如何构造一组解。

\Delta \le 1

当 \Delta = 0 时，a = n, \text{lcm} = v, \text{sum} = nv，所以 n = 1，舍。

当 \Delta = 1 时，a, b \ge 1，显然 \text{lcm} = v(v + 1)，有：

如果 b = 0，类似 \Delta = 1 的情况，无解。

因此 a, b, c \ge 1。此时要分两类讨论。

1) v \equiv 0 \pmod 2

此时 \text{lcm} = v \times \frac{(v + 1)(v + 2)}{2}。考虑方程：

此时 \text{lcm} = v \times (v + 1) \times (v + 2)。方程化简之后有：

由 \text{R}(b + 2c) \sub [3, 2n - 1] 且 f_1((n)_2 - 2) \lt 3 \lt 2n - 1 \lt f_1((n)_2)，得 v \in ((n)_2 - 2, (n)_2)。

可以观察到，这两个区间都很小（其中的整点数 \le 2），因此分别带入求解即可。接下来的分讨过程类似，所以就只保留结果了。并且，可以发现，如果 \text{lcm} 的系数是 \frac{1}{k}，则根号 n 前的系数就是 k。这点可以加快求出范围的过程。

\Delta = 3

仅有 v, (v + 1), (v + 3)

此时 \text{lcm} 有四种可能。

仅有 v, (v + 2), (v + 3)

此时 \text{lcm} 有四种可能。

四个数均有

注：后面发现，在数据范围内，前面几种已经完全够了，即不需要这种情况。std 与后面的证明均不会提到此情况。

这个时候就不是 (kn)_2 了，而是 (kn)_3。带入就能发现式子从一个二次的变成了一个三次的。

\Delta = 2

此时有 v(\frac{(v + 1)(v + 2)}{2} - n) \in [3, 2n - 1]。

由 6k((6k + 1)(3k + 1) - n) \ge 3 得：108k^3 + 54k^2 + 6k - 3 \ge 6kn，保守估计，得 n \le 18k^2 + 9k。

由 6k((6k + 1)(3k + 1) - n) \le 2n - 1 得：108k^3 + 54k^2 + 6k + 1 \le (6k + 2)n，保守估计，得 n \ge 18k^2 + 3k + 1。

因此 n \in [18k^2 + 3k + 1, 18k^2 + 9k]。

仅有 v, (v + 1), (v + 3)

此时有 v(\frac{(v + 1)(v + 3)}{3} - n) \in [4, 3n - 7] \cup \{3n - 5\}，将 3n - 5 忽略。

由 6k((6k + 1)(2k + 1) - n) \ge 4 得：72k^3 + 48k^2 + 6k - 4 \ge 6kn，有 n \le 12k^2 + 8k。

由 6k((6k + 1)(2k + 1) - n) \le 3n - 7 得：72k^3 + 48k^2 + 6k + 7 \le (6k + 3)n，有 n \ge 12k^2 + 2k + 1。因此 n \in [12k^2 + 2k + 1, 12k^2 + 8k]。

仅有 v, (v + 2), (v + 3)

此时有 v(\frac{(v + 2)(v + 3)}{6} - n) \in \{5\} \cup [7, 3n - 4]。将 5 忽略。

则有：n \in [6k^2 + 2k + 1, 6k^2 + 5k]。

2) v = 6k + 1