目录
D. 1122 Substring
E. 11/22 Subsequence
D. 1122 Substring
既然题中要求是两个一组，那就让双指针每次加 2，分成从第一个和第二个开始两种情况。r代表每一组的第一个数组，以组为单位。
因为要记录区间内的数字是否出现，所以碰到不符合的情况不能让 l 直接移到 r，l 要一组一组加过去同时从 vis 里面删数。
判断的是当前是否符合条件，条件有三个：（1）该组两个相等（2）该组数字没出现过（3）第二个数字在序列内不超过 n
当前符合条件就动 r，直到不能动为止，在 l 追上 r 之前，r 都不会再动。一旦 l 追上 r，就算不满足条件也会强行推进，因为接下来 l 也会动。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, cnt, ans, a[N], vis[N];
string s;int f(int hd)
{int res = 0;for (int l = hd, r = hd; l < n; l += 2){while (a[r] == a[r + 1] && vis[a[r]] == 0 && r + 1 <= n){vis[a[r]] = 1;r += 2;}res = max(res, r - l);if (l == r)r += 2;elsevis[a[l]] = 0;}return res;
}signed main()
{cin >> n;for (int i = 1; i <= n; i ++)cin >> a[i];ans = max(f(1), f(2));cout << ans;return 0;
}E. 11/22 Subsequence
对每个区间内的 ‘ / ’ 枚举会超时，但是对于所有 ‘ / ’，从前往后前面的 ‘ 1 ’ 越来越多，后面的 ‘ 2 ’ 越来越少，答案一定是先增后降，因此可以二分。找到给定区间内第一个前面 ‘ 1 ’ 的个数大于等于 ‘ 2 ’ 的个数的 ‘ / ’。
在二分查找里面要有两次判断，第一次判断是否在给定区间内，第二次是找到最靠前满足上文条件的 ' / '。
c 数组存的是每一个 ' / ' 的下标，二分查找的是当前 ' / ' 是 c 数组中的第几个，c [ mid ] 才是当前 ' / ' 在整个字符串中的下标。这里是不能直接去二分在整个字符串中的下标，因为我二分的对象是存 ' / ' 的集合，也就是 c 数组，所以只能去二分是 c 数组中的第几个。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;int T, n, q, pos, ans, a[N], b[N];
vector<int> c;
string s;int get1(int l, int r)
{return a[r] - a[l - 1];
}int get2(int l, int r)
{return b[r] - b[l - 1];
}int get(int x, int l, int r)
{// 二分出来的 pos 是有可能不在给定区间内的 if (x < l || x > r)return 0;int cnt1 = get1(l, x - 1), cnt2 = get2(x + 1, r);return min(cnt1, cnt2) * 2 + 1;
}signed main()
{cin >> n >> q >> s;s = ' ' + s;for (int i = 1; i <= n; i ++){a[i] = a[i - 1] + (s[i] == '1');b[i] = b[i - 1] + (s[i] == '2');if (s[i] == '/')c.push_back(i);}for (int i = 1; i <= q; i ++){int ql, qr, l = 0, r = c.size() - 1, pos = n + 1;cin >> ql >> qr;if (c.empty()){cout << 0 << '\n';continue;}while (l + 1 < r){int mid = l + (r - l) / 2;int cpos = c[mid] ;// 判是否在给定区间内 if (cpos < ql){l = mid;continue;}if (cpos > qr){r = mid;continue;}// 接下来二分第一个满足条件的 ' / ' int cnt1 = get1(ql, cpos - 1);int cnt2 = get2(cpos + 1, qr);if (cnt1 >= cnt2)r = mid, pos = mid;elsel = mid;}// 如果在给定区间内没有前面 1 的数量大于后面 2 的数量的 ' / ' if (pos == n + 1){// 找到给定区间右边的第一个 ' / ', 这个斜杠并没有用，真正有用的是这个的前一个 auto it = upper_bound(c.begin(), c.end(), qr);if (it != c.end())pos = it - c.begin();elsepos = c.size() - 1;} // 看到 pos - 1 要警惕 pos 可能为 0 ans = max(get(c[pos], ql, qr), pos == 0 ? 0 : get(c[pos - 1], ql, qr));cout << ans << '\n';}return 0;
}