育华周赛 第二十七期

T5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, q;
ll a[1000010];
ll b[1000010];
ll c[1000010];

ll pre[1000010]; // c[i] == 1, pre[i]连接的最左边的1的位置
ll nxt[1000010]; // c[i] == 1, nxt[i]连接的最右边的1的位置

ll lz[1000010]; // lz[i]表示i左边的0 的最大位置包括i
ll rz[1000010]; // rz[i]表示i右边的0 的最小位置包括i

ll g[1000010]; // g[i]表示以c[i]改为1增加的贡献
ll s[1000010]; // s[i]表示以g[i]的贡献次数  (可以完整贡献的次数)
ll gg[1000010]; // gg[i]第i个位置被修改的贡献 (会被左右切割的情况)
ll sum[1000010];;
ll ansi, ansv;
ll ans[1000010];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        c[i] = a[i] >= b[i];
    }

    for (int i = 1; i <= n; i++) {
        pre[i] = c[i] == 0 ? 0 : pre[i - 1] ? pre[i - 1] : i;
        lz[i] = c[i] ? lz[i - 1] : i;
        sum[i] = c[i] ? sum[i - 1] + i - pre[i] + 1 : sum[i - 1];
    }
  rz[n + 1] = n+1;
    for (int i = n; i >= 1; i--) {
        nxt[i] = c[i] == 0 ? 0 : nxt[i + 1] ? nxt[i + 1] : i;
        rz[i] = c[i] ? rz[i + 1] : i;
    }

    for (int i = 1; i <= n; i++) {
        if (!c[i]) {
            ll left = pre[i-1]? i-pre[i - 1] + 1:1;
            ll right = nxt[i + 1]? nxt[i + 1] - i + 1:1;
            g[i] = left * right;
        }
    }

    for (int i = 1; i <= q; i++) {
        ll l, r;
        cin >> l >> r;

        ll pll = rz[l];    // 区间里最左边的0
        ll prr = lz[r];    // 区间里最后边的0

        // 说明区间没有0
        if (pll > prr) {
            // 直接计算区间的贡献
            ansv += (r - l + 1) * (r - l + 2) / 2;
            continue;
        }
        // 右半部分通过前缀和求得
        ansv += sum[r] - sum[pll];
        // 看看左边有多少个1  计算贡献度
        ansv += (pll - l) * (pll - l + 1) / 2;

        // 1111011111   这种形态 那么这个0 变成1 的贡献度 记录下来
        if (pll == prr) {
            gg[pll] += (pll - l + 1) * (r - pll + 1);
        }
        else {
            // 11110.........0111111   这种形态   把这两个0变1 的贡献度记录下来
            gg[pll] += (pll - l + 1) * (c[pll + 1] ? (nxt[pll + 1] - pll + 1) : 1);
            gg[prr] += (r - prr + 1) * (c[prr - 1] ? (prr - pre[prr - 1] + 1) : 1);

            // 两个0之间的0 的贡献  只记录次数  因为他们的贡献度是g[i]
            // 这是差分  用前缀和求某个位置的值
            s[pll + 1]++;
            s[prr]--;
        }
    }
    for (int i = 1; i <= n; i++) {
        s[i] += s[i - 1];
        if (!c[i]) {
            // 修改i这个位置的贡献度
            ans[i] = g[i] * s[i] + gg[i];
            if (ans[i] > ans[ansi]) {
                ansi = i;
            }
        }
    }
    cout << ansi << " " << ans[ansi] + ansv << "\n";
    return 0;
}