E - 11/22 Subsequence题解
文章目录
- 大致思路
- 代码
大致思路
-
预处理:
-
用
pos1
,pos2
,posls
分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』 -
用
cum1
和cum2
分别存储了 1 1 1 和 2 2 2 的前缀和,这样可以快速获取任意区间内的 1 1 1 和 2 2 2 的『数量』
-
-
查询处理:
-
对于每个查询,使用**『前缀和』**来快速获取指定区间内的 1 1 1 和 2 2 2 的数量
-
然后使用
lower_bound
和upper_bound
查找指定区间内的 / / / 的位置 -
我们对于每个
/
的位置,需要计算左侧的 1 1 1 的数量和右侧的 2 2 2 的数量,取小的那个值乘以 2 2 2 再加 1 1 1,接着就可以可以形成的最长的 11 / 22 11/22 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;
}