E - 11/22 Subsequence题解

大致思路

1. 预处理:

   • 用pos1, pos2, posls 分别记录 $1$, $2$ ,$/$ 在字符串中的『位置』

   • 用cum1 和 cum2 分别存储了 $1$ 和 $2$ 的前缀和，这样可以快速获取任意区间内的 $1$ 和 $2$ 的『数量』

2. 查询处理:

   • 对于每个查询，使用**『前缀和』**来快速获取指定区间内的 $1$ 和 $2$ 的数量

   • 然后使用 lower_bound 和 upper_bound 查找指定区间内的 $/$ 的位置

   • 我们对于每个 / 的位置，需要计算左侧的 $1$ 的数量和右侧的 $2$ 的数量，取小的那个值乘以 $2$ 再加 $1$，接着就可以可以形成的最长的 $11/22$ 字符串部分序列的『长度』啦

   • 最后输出答案就可以了

代码

#include <iostream>		// 基本输入输出流
#include <algorithm>	// 通用算法（排序、查找、去重、二分查找等）
#include <vector>		// 动态数组（空间不够会自动扩容）
#include <queue>		// 队列（先进先出）
#include <stack>		// 栈（先进后出）
#include <set>			// 集合（有序不重复）
#include <map>			// 键值对容器（映射）
#include <list>			// 双向链表
#include <math.h>		// 数学函数
#include <functional>	// 通用的函数绑定和调用机制#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;void solve(){int n, q;cin >> n >> q;string s;cin >> s;// 前処理: 1, /, 2 の位置を記録vector<int> pos1, pos2, posls;for (int i = 0; i < n; i++) {if (s[i] == '1') pos1.push_back(i);else if (s[i] == '2') pos2.push_back(i);else if (s[i] == '/') posls.push_back(i);}// 1, 2 の累積和を計算vector<int> cum1(n + 1, 0), cum2(n + 1, 0);for (int i = 0; i < n; i++) {cum1[i + 1] = cum1[i] + (s[i] == '1');cum2[i + 1] = cum2[i] + (s[i] == '2');}while (q--) {int l, r;cin >> l >> r;--l; // 0-indexed に変換// 指定範囲内の 1, 2 の数を取得int count1 = cum1[r] - cum1[l];int count2 = cum2[r] - cum2[l];// 指定範囲内の / の位置を取得auto it1 = lower_bound(posls.begin(), posls.end(), l);auto it2 = upper_bound(posls.begin(), posls.end(), r - 1);vector<int> sah(it1, it2);int maxlen = 0;for (int mid : sah) {if (mid < l || mid >= r) continue;// 左側の 1 の数int l1 = cum1[mid] - cum1[l];// 右側の 2 の数int r2 = cum2[r] - cum2[mid + 1];// 11/22 文字列の部分列の長さを計算int len = min(l1, r2) * 2 + 1;maxlen = max(maxlen, len);}cout << maxlen << endl;}
}signed main(){//重定向输入输出
//    freopen("pow.in", "r", stdin);
//    freopen("pow.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int _ = 1;
//	cin >> _;	// 非多组测试数据请注释该行while(_--) solve();return 0;
}