https://ac.nowcoder.com/acm/contest/5389

B

参考大佬题解 https://ac.nowcoder.com/acm/problem/blogs/201976
题目：给定一个序列，每次在其左端点或者右端点加入一个元素。
每次加入都求一次这个序列的最长子区间---满足这个子区间的 'W' 元素的个数等于 'D' 元素的个数

比赛时考虑把W看成1 R看成0 然后看个数是否相等----考虑复杂了，不过也想到了用区间和来表示
把 'W' 看成 1，把 'D' 看成 -1，若一个子区间满足条件，则这个子区间的和为 0。
所以先用一个表示前缀和；若满足条件则。
但是这个题是动态在左右增加数的，且每次都要查询；考虑维护一个前缀和第一次和最后一次出现的位置 ,即
比如在r处前缀和为5，找map[5]（存的是前面出现过的前缀和），如果map[5]存在则pre[r]=pre[map[5]] 也就是这个子区间的和为0。
前面添加数不影响前缀和之间的差（虽然影响了整个前缀和数组），所以可以离线处理前缀和数组。
这个题难点在于前面加数怎么求---转换思维，把数组倒过来看就是和上面一样的"前缀和"

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

using namespace std;
unordered_map<int, int> l, r;
int n;
char s[N]; int num[N<<1];
int opr[N],presum[N<<1],sufsum[N<<1];
int get(char ch=0) {
    while(ch != 'R' && ch != 'W' && ch != 'D') ch = getchar();
    if(ch == 'R') return 0;
    return ch == 'D' ? 1 : -1;
}
int main() {

    int ans = 0;
    int lsum = 0, rsum = 0;
    int lp=N+1,rp=N;
    scanf("%d", &n);
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for(int i = 1; i <= len; ++i)
        num[++rp] = get(s[i]);

    //记录左右增加
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &opr[i]);
        if(opr[i] == 1) {
            num[--lp] = get();
        } else {
            num[++rp] = get();
        }
    }

    for(int i = lp; i <= rp; ++i) presum[i] = presum[i - 1] + num[i];
    for(int i = rp; i >= lp; --i) sufsum[i] = sufsum[i + 1] + num[i];

    lp = N+1, rp = N;
    r[presum[rp]] = rp;
    for(int i = 1; i <= len; ++i) {//起初的序列
        ++rp;
        if(!r.count(presum[rp])) {
            r[presum[rp]] = rp;
        } else {
            ans = max(ans, rp - r[presum[rp]]);
        }
    }
    for(int i = N+1; i <= N+len; ++i) l[sufsum[i]] = i;
    l[sufsum[N+len + 1]] = N+len + 1;
    printf("%d\n", ans);

    for(int i = 1; i <= n; ++i) {
        if(opr[i] == 1) {
            --lp, r[presum[lp - 1]] = lp - 1;//更新前缀和出现的位置
            if(!l.count(sufsum[lp])) {
                l[sufsum[lp]] = lp;
            } else {
                ans = max(ans, l[sufsum[lp]] - lp);
            }
        } else {
            ++rp, l[sufsum[rp + 1]] = rp + 1;//更新前缀和出现的位置
            if(!r.count(presum[rp])) {
                r[presum[rp]] = rp;
            } else {
                ans = max(ans, rp - r[presum[rp]]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C

对于每次查询暴力+各种剪枝可过，代码有注释。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int

const int N = 600005;
int a[N];
int n, m;

int solve(int x)
{
    int mmax = 0, orv = 0, len = 1e9;
    for (rint i = x; i >= 1; i--) {
        mmax = max(mmax, a[i]);
        orv |= a[i];
        if (orv > mmax) {
            len = min(len, x - i + 1);
            break;
        }
    }
    mmax = 0, orv = 0;
    for (rint i = x; i <= n; i++) {
        mmax = max(mmax, a[i]);
        orv |= a[i];
        if (orv > mmax) {
            len = min(len, i - x + 1);
            break;
        }
    }
    mmax = a[x], orv = a[x];
    for (rint i = x - 1; i >= 1; i--) {
        mmax = max(mmax, a[i]);
        orv |= a[i];
        if (x - i + 1 >= len) {
            break; //剪枝
        }
        if (orv > mmax) {
            len = x - i + 1;
            break; //剪枝
        }
        int Max2 = mmax, Or2 = orv;
        for (rint j = x + 1; j <= n; j++) {
            Max2 = max(Max2, a[j]);
            Or2 |= a[j];
            if (j - i + 1 >= len) {
                break;
            }
            if (Or2 > Max2) {
                len = j - i + 1;
                break;
            }
        }
    }
    return len;
}
int main()
{
    cin>>n>>m;
    for (rint i = 1; i <= n; i++) {
        cin>>a[i];
    }
    while (m--) {
        int x;cin>>x;
        int ans = solve(x);//对于每次查询
        if (ans == 1e9)
            ans = -1;
        cout<<ans<<endl;
    }
    return 0;
}