来源：2024牛客暑期多校训练营7

做题时间：2024_08_06

D Interval Selection

标签：线段树、[[扫描线]]、枚举

题意

区间的每个数字的数量是 \(k\) 的定义为好区间

比如 \(k=2\)，数组为 \({1,1,2,3,2,3,1}\) 对于\([3,6]\)和\([1,6]\) 等都符合要求（下标从1开始）

求所有好区间的数量，比如案例中有4个好区间

思路

考虑[[枚举]] \(i\) 点为好区间的左端点，数有多少个右区间是符合要求的

比较好想到的是考虑相同的数字存在数组里

根据k每次可以找到当前i往右的第 \(k\) 个与 \(a_i\) 相同的数的位置

一开始我想过每次到i，然后找区间内其他数的对应位置

比如 \({1,1,2,3,2,3,1}\) ，i为2，那么从i开始，后一个数是2,对于2，其合法区间是 \([5,7]\)，因为 \(a_5\) 是2往右的第k个2，并且后续没有2了，所以从5到最后都是2的合法区间

那么 \(a_2,a_3\) 的合法区间的交集是\([7]\)

继续考虑 \(a_4\) 合法区间是\([6,7]\) ，交集同样是 \([7]\)

这就是以 \(a_2\) 为左端点的好区间的选择范围，只有1个

但是枚举肯定是不行，让我们思考，如果以 \(a_i\) 为左端点，现在需要找范围内跟其他所有其他数字的合法区间的交集的长度

其实想到区间就可以尝试用[[线段树]]了

但是用线段树前还需要明确怎么计算好区间

比如 \({1,1,2,3,2,3,1}\)，\(i=2\) ，现在只需要找 \(a_3,a_4\) 的往右的第k个相同的数的位置，而不需要考虑 \(a_5,a_6\)

所以i更新后，需要撤销之前的 \(a_i\) 的合法区间的处理，就像i=2处理后，i=1时撤销i=2的操作

以上就是看题解和讲解后的逆推思考，当时想用差分或者线段树但是没想出来，扫描线的套路

代码

具体实施流程

将合法区间置 \(0\)，不合法区间 \(+1\)，每次处理完i的合法区间后，数 \([i,n]\) 有多少\(0\)，就是当前 \(i\) 的贡献

线段树维护区间min，如果区间min为0向下查询，反之结束这层查询

AC代码

#include <bits/stdc++.h>
using namespace std;

#define YES "Yes"
#define NO "No"
#define F first
#define S second
#define int long long
#define ull unsigned long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i, j, k) for (i = (j); i < (k); i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
typedef pair<int, int> pii;

const int MOD = 1000000007;
const int N = 2e5 + 10;
int ii, jj, kk;

int n, k, t;
int mi[N << 2] = {0};
int add[N << 2] = {0};
int cnt[N << 2] = {0}; // 存储区间内0的个数

int a[N];
map<int, vector<int>> mp;

void up(int i) {
    mi[i] = min(mi[i << 1], mi[(i << 1) | 1]);
    cnt[i] = 0;
    if (mi[i] == mi[i << 1]) cnt[i] += cnt[i << 1];
    if (mi[i] == mi[(i << 1) | 1]) cnt[i] += cnt[(i << 1) | 1];
}

void lazy(int i, int jobv) {
    add[i] += jobv;
    mi[i] += jobv;
}

void down(int i) {
    lazy(i << 1, add[i]);
    lazy((i << 1) | 1, add[i]);
    add[i] = 0;
}

void build(int l, int r, int i) {
    if (l == r) {
        mi[i] = 0;
        add[i] = 0;
        cnt[i] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, i << 1);
    build(mid + 1, r, (i << 1) | 1);
    up(i);
    add[i] = 0;
}

void func_add(int jobl, int jobr, int jobv, int l, int r, int i) {
    if (jobl > jobr) return;
    if (jobl <= l && r <= jobr) {
        lazy(i, jobv);
        return;
    }

    down(i);
    int mid = r + l >> 1;
    if (jobl <= mid) func_add(jobl, jobr, jobv, l, mid, i << 1);
    if (jobr >= mid + 1) func_add(jobl, jobr, jobv, mid + 1, r, (i << 1) | 1);
    up(i);
}

int query(int jobl, int jobr, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        if (mi[i] == 0)
            return cnt[i];
        else
            return 0;
    }
    int mid = r + l >> 1;
    down(i);
    int ans = 0;
    if (jobl <= mid) ans += query(jobl, jobr, l, mid, i << 1);
    if (jobr >= mid + 1) ans += query(jobl, jobr, mid + 1, r, (i << 1) | 1);
    up(i);
    return ans;
}

void solve() {
    mp.clear();
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]].push_back(i);
    }
    build(1, n, 1);

    int ans = 0;
    map<int, vector<pii>> mp_op; // 用于存储对应数字的操作
    for (int i = n; i >= 1; i--) {
        // 撤回
        auto &v = mp_op[a[i]];
        for (auto &[l, r] : v) {
            func_add(l, r, -1, 1, n, 1);
        }
        v.clear();

        auto &it = mp[a[i]];

        int ki = lower_bound(all(it), i) - it.begin() + k - 1; // i往右的第k个相同数在map中的下标
        // 说明 第k个数不存在
        if (ki >= it.size()) {
            func_add(i, n, 1, 1, n, 1);
            mp_op[a[i]].push_back({i, n});
        } else {
            // 往右第k个数存在
            if (i <= it[ki] - 1) {
                func_add(i, it[ki] - 1, 1, 1, n, 1);
                mp_op[a[i]].push_back({i, it[ki] - 1});
            }
            // 现在处理往右第k+1个数
            if (ki + 1 < it.size() && it[ki + 1] <= n) {
                func_add(it[ki + 1], n, 1, 1, n, 1);
                mp_op[a[i]].push_back({it[ki + 1], n});
            }
        }
        int q = query(i, n, 1, n, 1);
        ans += q;
    }
    cout << ans << endl;
}

signed main() {
    IOS;
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

K Strings, Subsequences,Reversed Subsequences,Prefixes

标签：字符串

题意

给 \(S\) 和 \(T\) 串，在 \(S\) 串中找到一个子序列，使这个序列的前缀为 \(T\) 逆转后的前缀也为 \(T\)

数一共有几个子序列

题目案例：

input:
7 2
abababaab
ab

output:
8

explain:
"aba","abba","ababa","abbba","abaaba","ababba","abbaba","abababa"

思路

首先，我们先在S串中取最前的T串，再取最后的T串

例如 \(S=abegfhbca\), \(T=ab\)，此时贪心取到的最短前缀为 \(ab\)，最短后缀为 \(bca\)

那么现在只需要对中间的 \(egfh\) 取本质不同的子序列就可以，也就是[[动态规划]]

还需注意对于特殊情况，也就是 \(aba\) 这种前缀和后缀相交的情况

可知这种都是回文[[字符串]]

比如 \(efabab\) ，最后一个a和最后一个b都可以作为回文中心

那么就去找 \(babafe\) 的后缀是否能接在 \(efabab\) 后面形成回文串，就是找位置

代码