2016集训测试赛（二十六）Problem A: bar

Solution

首先审清题意, 这里要求的是子串而不是子序列...

我们考虑用1表示p, -1表示j. 用sum[i]表示字符串前(i)的前缀和. 则我们考虑一个字符串([L, R])有什么要求: (forall x in [L, R])满足(sum[x] ge sum[L - 1]).

我们分别从前往后和从后往前求出以每个位置为开头的最长合法子串, 然后扔进树状数组里面查询即可.

至于怎么求以每个位置为开头最长合法子串, 我们考虑用一个单调栈来维护: 从前往后扫每个位置, 假如当前位置的(sum)小于栈顶的(sum)则弹栈, 并把以栈顶为开头的最长合法子串的末尾设为当前位置的前一位. 弹栈结束后, 插入当前位置即可.

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = (int)1e6, INF = (int)2e9;
int n;
struct record
{
    int L, R;
    inline int operator <(const record &a) const {return R < a.R;}
}rec[N + 1];
struct segmentTree
{
    int mn[N << 2];
    inline segmentTree() {memset(mn, 127 ,sizeof(mn));}
    void insert(int u, int L, int R, int pos)
    {
        mn[u] = min(mn[u], pos);
        if(L == R) return;
        if(pos <= L + R >> 1) insert(u << 1, L, L + R >> 1, pos);
        else insert(u << 1 | 1, (L + R >> 1) + 1, R, pos);
    }
    inline void insert(int pos) {insert(1, 1, n, pos);}
    int query(int u, int L, int R, int pos)
    {
        if(L >= pos) return mn[u];
        int mid = L + R >> 1;
        if(pos <= mid) return min(query(u << 1, L, L + R >> 1, pos), query(u << 1 | 1, (L + R >> 1) + 1, R, pos));
        else return query(u << 1 | 1, (L + R >> 1) + 1, R, pos);
    }
    inline int query(int pos) {return query(1, 1, n, pos);}
}seg;
struct binaryIndexedTree
{
    int mx[N + 1];
    inline binaryIndexedTree() {memset(mx, -1, sizeof(mx));}
    inline void insert(int pos, int x)
    {
        for(int i = pos; i <= n; i += i & - i)
            mx[i] = max(mx[i], x);
    }
    inline int query(int pos)
    {
        int res = -1;
        for(int i = pos; i; i -= i & - i) res = max(res, mx[i]);
        return res;
    }
}BIT;
int main()
{

#ifndef ONLINE_JUDGE

    freopen("bar.in", "r", stdin);
    freopen("bar.out", "w", stdout);

#endif

    scanf("%d
", &n);
    static int a[N + 1];
    for (int i = 1; i <= n;  ++ i) a[i] = getchar() == 'p' ? 1 : -1;
    static int stk[N + 1], sum[N + 2];
    int tp = 0; stk[tp ++] = 0;
    sum[0] = 0; for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + a[i]; sum[n + 1] = - INF;
    static int f[N + 1];
    for (int i = 1; i <= n + 1; ++ i)
    {
        while (tp && sum[i] < sum[stk[tp - 1]]) f[stk[tp - 1] + 1] = i - 1, -- tp;
        stk[tp ++] = i;
    }
    for(int i = 1; i <= n; ++ i) rec[i].L = i, rec[i].R = f[i];
    tp = 0; stk[tp ++] = n + 1;
    sum[n + 1] = 0; for(int i = n; i; -- i) sum[i] = sum[i + 1] + a[i]; sum[0] = - INF;
    for(int i = n; ~ i; -- i)
    {
        while(tp && sum[i] < sum[stk[tp - 1]]) f[stk[tp - 1] - 1] = i + 1, -- tp;
        stk[tp ++] = i;
    }
    sort(rec, rec + n + 1);
    int ans = 0;
/*    for(int i = 1, p = 1; i <= n; ++ i)
    {
        for(; rec[p].R <= i; ++ p) seg.insert(rec[p].L);
        int cur = seg.query(f[i]);
        if(cur > i) continue;
        else ans = max(ans, i - cur + 1);
    } */
    for(int i = 1, p = 1; i <= n; ++ i)
    {
        for(; p <= rec[i].R; ++ p) BIT.insert(f[p], p);
        int cur = BIT.query(rec[i].L);
        if(cur >= rec[i].L) ans = max(ans, cur - rec[i].L + 1);
    }
    printf("%d
", ans);
}