来源：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\) 后面形成回文串，就是找位置

代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int n, m;
string s, t;
vector<int> index[2]; // index[i][j] i表示从前往后或者从后往前，j表示t[j]  整体表示在s串中的最左位置或最右位置

//传入s和s的开始和结束位置，计算本质不同的子序列个数
// 详情参考:https://www.cnblogs.com/ptno/p/16541669.html
int getDifStrNum(string &s, int be, int en) {
    if (be > en) return 1;// 此处表示如果出现 s=gggg t=gg这类，中间只有空串
    vector<int> last(26, -1); // 上一个对应字符的位置
    vector<int> dp(en - be + 2, 0);
    for (int i = be; i <= en; i++) {
        dp[i - be + 1] = dp[i - be] * 2 + 1;
        if (last[s[i] - 'a'] != -1) dp[i - be + 1] -= dp[last[s[i] - 'a'] - be] + 1;
        last[s[i] - 'a'] = i;

        dp[i - be + 1] = (dp[i - be + 1] + MOD) % MOD;
    }
    return dp[en - be + 1] + 1;// 返回时加1，表示空字符串
}

// 马拉车处理
string deal(string &t) {
    string str = "#";
    for (auto &i : t) (str += i) += '#';
    return str;
}

int solve() {
    cin >> n >> m;
    cin >> s >> t;
    index[0].resize(m, 0);
    index[1].resize(m, 0);

    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s[i] == t[j]) {
            index[0][j] = i;
            i++, j++;
        } else
            i++;
    }
    if (j != t.length()) return 0;

    i = n - 1, j = 0;
    while (i >= 0 && j < t.length()) {
        if (s[i] == t[j]) {
            index[1][j] = i;
            i--, j++;
        } else
            i--;
    }
    if (j != t.length()) return 0;

    int ans = 0;
    if (index[0][m - 1] < index[1][m - 1]) ans += getDifStrNum(s, index[0][m - 1] + 1, index[1][m - 1] - 1);

	//马拉车算法处理中心
    string newt = deal(t);
    int len = newt.length(), c = 0;
    vector<int> r(len, 0);
    for (int i = 1; i < len; i++) {
        if (c + r[c] >= i) r[i] = min(r[2 * c - i], c + r[c] - i);
        while (i - r[i] >= 0 && newt[i - r[i]] == newt[i + r[i]]) r[i]++;
        r[i]--;
        if (c + r[c] < i + r[i]) c = i;
    }
	
    for (int i = 0; i < len - 1; i++) {
		if (i + r[i] == len - 1)
            if (i - m == 0 || index[1][i - m - 1] > index[0][m - 1])
                ans++;
    }

    return ans;
}

signed main() {
    cout << solve();
    return 0;
}