标签：pre int lim mi res LittleElephantAndRGB mx

计数

枚举第一个区间的右端点，第二个区间的左端点，然后记录每个点前面第一个连续的 \(lim\) 个的位置，这个点往前连续的 \(g\) 的个数，对称在记录一遍

然后直接统计答案，

• 如果两个拼起来一段是可行的
  • 考虑前面选的不够，后面去到一整段之后
  • 前面和后面拼起来够，等差数列
  • 前面足够长
• 否则
  • 考虑前面的整段和后面的整段的位置

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int n;
string s;
int lim;
int pre[N], suf[N], mx[N], mi[N];

void solve()
{
    cin >> n;
    s = " ";
    rep(i, 1, n)
    {
        string tmp;
        cin >> tmp;
        s += tmp;
    }
    cin >> lim;
    n = s.size() - 1;
    debug(n);
    mx[0] = mi[n + 1] = -1;
    mms(pre, 0);
    mms(suf, 0);
    rep(i, 1, n)
    {
        if (s[i] == 'G')
        {
            pre[i] = pre[i - 1] + 1;
        }
        if (pre[i] >= lim)
            mx[i] = i - lim + 1;
        else
            mx[i] = mx[i - 1];
    }
    per(i, n, 1)
    {
        if (s[i] == 'G')
        {
            suf[i] = suf[i + 1] + 1;
        }
        if (suf[i] >= lim)
            mi[i] = i + lim - 1;
        else
            mi[i] = mi[i + 1];
    }
    // rep(i, 1, n) debug(i, mx[i], mi[i], pre[i], suf[i]);
    int res = 0;
    rep(i, 1, n)
    {
        rep(j, i + 1, n)
        {
            if (pre[i] + suf[j] >= lim && s[i] == 'G' && s[j] == 'G')
            {
                int l = max(1ll, lim - suf[j]);
                int r = min(pre[i], lim - 1ll);
                debug(l, r, res);
                if (l != 1)
                {
                    if (mi[j] >= 0)
                        res += (l - 1) * (n - mi[j] + 1);
                }
                if (r != lim - 1)
                {
                    if (mx[i] >= 0)
                        res += (lim - 1 - r) * mx[i];
                }
                res += (n - j + 1 - (lim - l) + 1 + n - j + 1 - (lim - r) + 1) * (r - l + 1ll) / 2ll;
                // debug(l, r, res);
                res += (i - r) * (n - (j + (lim - r) - 1) + 1);
                // debug(i, j, l, r, res);
            }
            else
            {
                if (mx[i] < 0)
                {
                    if (mi[j] >= 0)
                        res += (n - mi[j] + 1) * i;
                }
                else
                {
                    // debug(i, j, res);
                    if (mi[j] >= 0)
                        res += (n - mi[j] + 1) * (i - mx[i]);
                    // debug(i, j, res);
                    res += mx[i] * (n - j + 1);
                }
            }
            debug(i, j, res);
        }
    }
    cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：pre,int,lim,mi,res,LittleElephantAndRGB,mx
From： https://www.cnblogs.com/xiaruize/p/18119841