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';
    }
}