Educational Codeforces Round 131 D-F

D. Permutation Restoration

题意：原先有一个排列 \(a(1...n)\)，令 \(b_i=\lfloor i/a_i \rfloor\)。现在给出序列 \(b\)，要恢复排列 \(a\)

首先可以根据 \(b_i\) 得出 \(a_i\) 的范围是 \((i/(b_i+1), i/b_i]\)，由此得到了每个 \(a_i\) 的取值区间，接下来要将 \(1-n\) 分配给他们。

可以先按照区间的右端排序，按右端从小到大依次去取尽可能小的数，正确性显然。

取尽可能小的数可以用并查集。

int n, m, f[maxn], ans[maxn];
int find(int x) {
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
struct node {
    int l, r, id;
}a[maxn];

void solve() {
    cin >> n;
    for(int i = 1;i <= n;i++) {
        int x; cin >> x;
        if(x == 0) {
            a[i] = {i + 1, n, i};
        } else {
            a[i] = {i / (x + 1) + 1, i / x, i};
        }
    }
    sort(a + 1, a + n + 1, [](node i, node j) {return i.r < j.r;});
    for(int i = 1;i <= n;i++) f[i] = i;
    for(int i = 1;i <= n;i++) {
        int t = find(a[i].l);
        ans[a[i].id] = t;
        f[t] = t + 1;
    }
    for(int i = 1;i <= n;i++) cout << ans[i] << " \n"[i == n];
}

E. Text Editor

题意：给出字符串 \(s_1\) 和 \(s_2\)，初始光标在 \(s_1\) 最后一个字符的右边，每次操作可以：

• 将光标左移或右移一位
• 删除光标左侧字符
• 将光标移动到最前面（第一个字符左边）或最后面

问最少多少次操作可以使 \(s_1\) 变成 \(s_2\)

要将 \(s_1\) 变成 \(s_2\) 只需要将多余字符删去即可，不难发现，从右往左边移动光标的同时可以顺带删除，而从左往右移动时，删除字符需要额外的一步操作。

显然我们不会反复进行操作3，可以将操作分为两段：先向左移删除一些字符，再跳到最前面向右移删除一些字符。

缩减操作次数主要靠两部分：尽量在左移时删除，和在中间保留一段无需访问的已经匹配上的子串。

解法：枚举从左向右移动的终点 \(i\)，同时维护前 \(i\) 个字符能匹配的最大长度 \(j\)，那么前 \(i\) 个字符可以任意选择匹配 \(s_2\) 的前 \(1...j\) 个字符。

假设选择匹配了前 \(x\) 个，那么从 \(s_2[x+1]\) 和 \(s_1[i+1]\) 开始如果能匹配若干个字符，这些字符是无需访问的；剩下的就都是从右向左移动的部分了。

用 \(i + i - k + n - (i + f_{i+1, k+1}) + 1\) 更新答案，其中 \(f_{i, j}\) 表示 \(s_1[i..]\) 和 \(s_2[j..]\) 的最长公共前缀。

提前 \(dp\) 预处理 \(f_{i,j}\) 即可。

int n, m;
string s1, s2;
int f[5003][5003];
 
void solve() {
    cin >> n >> m;
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    
    for(int i = 1, j = 1;i <= n;i++) {
        if(s1[i] == s2[j]) j++;
        if(i == n && j <= m) {
            cout << "-1\n";
            return;
        }
    }
 
 
    for(int i = 0;i <= max(n, m) + 1;i++) f[i][m + 1] = f[n + 1][i] = 0;
    for(int i = n;i > 0;i--) {
        for(int j = m;j > 0;j--) {
            if(s1[i] == s2[j]) f[i][j] = f[i + 1][j + 1] + 1;
            else f[i][j] = 0;
        }
    }
    int ans = n - f[1][1];
    for(int i = 1, j = 0;i <= n;i++) {
        if(s1[i] == s2[j + 1]) j++;
        for(int k = 0;k <= j;k++) {
            ans = min(ans, i + i - k + n - (i + f[i + 1][k + 1]) + 1);
        }
    }
    cout << ans << '\n';
}

F. Points

题意：\(x\) 轴上有若干个点，任意三个点若满足 \(i<j<k\) 且 \(k-i\le d\)，则它是一个优美的元组。

接下来将在空数轴上进行若干次操作，每次选取一个整数位置 \(x\)，若上面有点则将其删去，否则在此处添加点。

每次操作完成后要输出优美元组的总数，点的位置 \(\le2\times 10^5\)

学习了t宝的神奇线段树。

不难想的部分：

每当在 \(x\) 这个位置上操作，就查找区间 \([x-d, x-1]\) 和 \([x+1, x+d]\) 上点的个数，分别计算以 \(x\) 为左、右端点的元组个数。

比较麻烦的是 \(x\) 作为中间的元组数。

t宝的线段树维护了区间的这些内容：

• 区间点个数（设为 \(cr\)）
• 向左移 \(d\) 的区间中点的个数（设为 \(cl\)）
• 跨这两段区间，距离在 \(d\) 以内的点对个数（设为 \(sp\)）。

第三个即我们需要的信息，维护它：

对单个点来说 \(sp=cl\times cr\)

合并 \(a,b\) 两个区间（\(a\) 在左）时，\(sp=sp_a+sp_b+cr_a\times cl_b\)

画图看一下就明白了：合并的时候新产生的 \(sp\) 只能是右边的左块和左边的右块之间的点对，其他的距离都在 \(d\) 以上。

int n, d;
struct node {
    ll cr, cl, sp;
    node merge(node x) {
        return {cr + x.cr, cl + x.cl, sp + x.sp + cr * x.cl};
    }
};
struct segTree {
    node t[maxn << 4];
    void push_up(int p) {
        t[p] = t[p * 2].merge(t[p * 2 + 1]);
    }
    void modify(int p, int l, int r, int pos, int adl, int adr) {
        if(l == r) {
            t[p].cl += adl;
            t[p].cr += adr;
            t[p].sp = t[p].cl * t[p].cr;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) modify(p * 2, l, mid, pos, adl, adr);
        else modify(p * 2 + 1, mid + 1, r, pos, adl, adr);
        push_up(p);
    }
    node query(int p, int l, int r, int L, int R) {
        if(l > R || L > r) return {0, 0, 0};
        if(L <= l && r <= R) return t[p];
        int mid = (l + r) / 2;
        node res = query(p * 2, l, mid, L, R);
        res = res.merge(query(p * 2 + 1, mid + 1, r, L, R));
        return res;
    }    
}segt;
 
int st[maxn];
void solve() {
    cin >> n >> d;
    ll ans = 0, mx = 400000;
    for(int i = 1;i <= n;i++) {
        int x; cin >> x;
        int f = st[x] ? -1 : 1;
        st[x] ^= 1;
        ll r = segt.query(1, 1, mx, x + 1, x + d).cr;
        ll l = segt.query(1, 1, mx, x - d, x - 1).cr;
        ans += (r * (r - 1) / 2 + l * (l - 1) / 2) * f;
        if(d > 1) ans += segt.query(1, 1, mx, x + 1, x + d - 1).sp * f;
        segt.modify(1, 1, mx, x, 0, f);
        segt.modify(1, 1, mx, x + d, f, 0);
        cout << ans << '\n';
    }
}