P3564 [POI2014]BAR-Salad Bar

給定一個長度為$n$的數組，里面元素只有$1$跟$?1$，問選出一個長度為$len$的區間使得，這個區間的前綴和時刻大于零，后綴和時刻大于零，輸出最大長度$len$，

考慮枚舉$l$端點，我們可以二分出最大的$r$，滿足$pre\_sum$時刻大于等于零，設為$[l,r]$，

考慮枚舉$R$端點，我們可以二分出最小的$L$，滿足$suc\_sum$時刻大于等于零，設為$[L,R]$，

則答案一定是在所有上述點對中的$l,R$中的一個，且有$l\le R\le r$，$L\le l\le R$，

假設我們已經把上述滿足要求的兩種點對都算出來了，考慮新開一個線段樹，

我們把第二種點對$[L,R]$，放進線段樹上維護，在$R$點記錄符合要求的最小的$L$，

考慮枚舉$[l,r]$點對，在區間$[l,r]$中尋找一個最大的$R$，使得于$R$相對應的$L$，滿足$L\le l$，這個時候我們的答案就是$R?l+1$的最大值了。

上述操作都利用$ST$表，然后二分一下即可，整體復雜度$O(n\log n)$。

#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10, logn = 20;int a[N], sum[N], b[N], Log[N], f[N][logn + 1], n;char str[N];vector<pair<int, int>> vt, v;void init() {Log[1] = 0, Log[2] = 1;for (int i = 3; i < N; i++) {Log[i] = Log[i / 2] + 1;} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);init();scanf("%d %s", &n, str + 1);for (int i = 1; i <= n; i++) {a[i] = str[i] == 'p' ? 1 : -1;}for (int i = 1; i <= n; i++) {sum[i] = a[i] + sum[i - 1], f[i][0] = sum[i];}for (int j = 1; j <= logn; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}for (int i = 1; i <= n; i++) {if (a[i] == -1) {continue;}int l = i, r = n;while (l < r) {int mid = l + r + 1 >> 1, s = Log[mid - i + 1];if (min(f[i][s], f[mid - (1 << s) + 1][s]) >= sum[i - 1]) {l = mid;}else {r = mid - 1;}}// printf("%d %d\n", i, l);vt.push_back({i, l});}for (int i = 1; i <= n; i++) {sum[i] = a[n - i + 1] + sum[i - 1], f[i][0] = sum[i];}for (int j = 1; j <= logn; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}memset(b, 0x3f, sizeof b);for (int i = 1; i <= n; i++) {if (a[n - i + 1] == -1) {continue;}int l = i, r = n;while (l < r) {int mid = l + r + 1 >> 1, s = Log[mid - i + 1];if (min(f[i][s], f[mid - (1 << s) + 1][s]) >= sum[i - 1]) {l = mid;}else {r = mid - 1;}}b[n - i + 1] = n - l + 1;// printf("%d %d\n", n - l + 1, n - i + 1);}for (int i = 1; i <= n; i++) {f[i][0] = b[i];}for (int j = 1; j <= logn; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}int ans = 0;for (auto it : vt) {int L = it.first, R = it.second;int l = it.first, r = it.second;while (L < R) {// [mid + 1, r]int mid = L + R >> 1, s = Log[r - mid];if (min(f[mid + 1][s], f[r - (1 << s) + 1][s]) <= l) {L = mid + 1;}else {R = mid;}}ans = max(ans, L - l + 1);}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的P3564 [POI2014]BAR-Salad Bar（ST表 + 二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。