洛谷P3564 [POI2014]BAR-Salad Bar
? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 树状数组 ?    2018-10-10 07:51:50    462    0    0

题目描述

有一个长度为n的字符串,每一位只会是p或j。求一个最长子串,使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。(1n1 000 000)

输入输出样例

输入样例#1: 复制
6
jpjppj
输出样例#1: 复制
4​​

 

 遇到个数有关的问题首先把j看做-1,p看做1。这样就是要从左往右从右往左每个位置的前缀和都非负,处理原数组[前/后]缀和为pre[i]、suf[i]。

 考虑对于位置i,先分别处理i向右最长能延伸到的地方和向左最长能延伸到的地方,记为R[i]和L[i]。这就相当于找到pre[i]右边/suf[i]左边第一个比他小的数。我们使用单调栈。

现在我们把所有位置按照L[i]从大到小排序。每一次维护加入当前L[i]以右的所有点。

考虑一个合法区间,一定是左端点R[i]在右端点或以后,右端点L[i]在左端点或以前,这样我们用一个线段树维护R[i]在[L,R]之间的点中,i的最小值是多少就可以了。因为我们每一次做后缀查询,可以使用树状数组。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
char s[maxn];
int pre[maxn], suf[maxn], a[maxn];
int L[maxn], R[maxn], len, ans;
typedef pair<int, int > pii;
pii Qs[maxn];
stack<int > stk, id;

namespace BIT {
    #define lowbit(x) ((x) & (-(x)))
    int t[maxn];
    void init() {memset(t, 0x3f, sizeof(t));}
    int query(int x) {
        int ans = inf;
        while(x) ans = min(ans, t[x]), x -= lowbit(x);
        return ans;
    }
    void edit(int x, int w) {
        while(x <= len) 
            t[x] = min(t[x], w), x += lowbit(x);
    }
}

void push(int * ans, int x, int pos, int p) {
    while(!stk.empty() && stk.top() > x) {
        ans[id.top()] = pos, stk.pop(), id.pop();
    }
    stk.push(x), id.push(p);
}

void clear(int * ans, int lim) {
    while(!stk.empty()) {
        ans[id.top()] = lim, stk.pop(), id.pop();
    }
}

int main() {
    scanf("%d", &len);
    scanf("%s", s + 1);
    BIT::init();
    for(register int i = 1; i <= len; ++i)
        a[i] = s[i] == 'p' ? 1 : -1;
    for(register int i = 1; i <= len; ++i)
        pre[i] = pre[i - 1] + a[i];
    for(register int i = len; i >= 1; --i)
        suf[i] = suf[i + 1] + a[i];
    push(R, 0, 0, 1); 
    for(register int i = 1; i < len; ++i) push(R, pre[i], i, i + 1);
    clear(R, len);
    push(L, 0, len + 1, len); 
    for(register int i = len; i > 1; --i) push(L, suf[i], i, i - 1);
    clear(L, 1);
    for(register int i = 1; i <= len; ++i)
        Qs[i] = make_pair(L[i], i);
    sort(Qs + 1, Qs + len + 1);
    int tp = len + 1;
    for(register int i = len; i >= 1; --i) {
        while(tp > Qs[i].first) 
            --tp, BIT::edit(len - R[tp] + 1, tp);
        int best = BIT::query(len - Qs[i].second + 1);
        ans = max(ans, max(Qs[i].second - best + 1, 0));
    }
    printf("%d", ans);
    return 0;
}


上一篇: 洛谷P4283 [AHOI2008]Y型项链

下一篇: 洛谷P1600 天天爱跑步

462 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航