题解 [牛客IOI周赛16-提高组 B] 小L扔垃圾

• 小L扔垃圾

题目描述

给定一个序列，每次在其左端点或者右端点加入一个元素。

求这个序列的最长子段满足这个子段的 'W' 元素的个数等于 'D' 元素的个数。

正解

把 'W' 看成 1，把 'D' 看成 -1，若一个子段满足条件，则这个子段的和为 0。

记录前缀和，然后 要满足条件的话，。

离线预处理出前缀和数组，用哈希表维护一个前缀和的出现位置就行。

时间复杂度 。

（貌似在线也能做

代码

#include <bits/stdc++.h>
#define N 2000005

using namespace std;

int n;
int arr[N + N], ltax[N + N], rtax[N + N], dir[N];
char s[N];

unordered_map<int, int> l, r;


int get(char ch = 0) {
    while(ch != 'R' && ch != 'W' && ch != 'D') ch = getchar();
    if(ch == 'R') return 0;
    return ch == 'W' ? -1 : 1;
}

int main() {
    int *f = arr + N, *psl = ltax + N, *psr = rtax + N;
    int lp = 1, rp = 0, ans = 0;
    int lsum = 0, rsum = 0;

    scanf("%d", &n);
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for(int i = 1; i <= len; ++i)
        f[++rp] = get(s[i]);

    for(int i = 1; i <= n; ++i) {
        scanf("%d", &dir[i]);
        if(dir[i] == 1) {
            f[--lp] = get();
        } else {
            f[++rp] = get();
        }
    }

    for(int i = lp; i <= rp; ++i) psr[i] = psr[i - 1] + f[i];
    for(int i = rp; i >= lp; --i) psl[i] = psl[i + 1] + f[i];

    lp = 1, rp = 0;
    r[psr[rp]] = rp;
    for(int i = 1; i <= len; ++i) {
        ++rp;
        if(!r.count(psr[rp])) {
            r[psr[rp]] = rp;
        } else {
            ans = max(ans, rp - r[psr[rp]]);
        }
    }
    for(int i = 1; i <= len; ++i) l[psl[i]] = i;
    l[psl[len + 1]] = len + 1;
    printf("%d\n", ans);

    for(int i = 1; i <= n; ++i) {
        if(dir[i] == 1) {
            --lp, r[psr[lp - 1]] = lp - 1;
            if(!l.count(psl[lp])) {
                l[psl[lp]] = lp;
            } else {
                ans = max(ans, l[psl[lp]] - lp);
            }
        } else {
            ++rp, l[psl[rp + 1]] = rp + 1;
            if(!r.count(psr[rp])) {
                r[psr[rp]] = rp;
            } else {
                ans = max(ans, rp - r[psr[rp]]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}