P6578 [Ynoi2019] 魔法少女网站

· · 题解

比较简单的题目，操作分块做法，并不很卡常。

考虑不带修，这是个经典问题。将小于等于 x 的位置标为 1，其余位置标为 0，答案就是全为 1 的区间数量。区间查询，则用分块维护，单点修改 \mathcal O(1)，区间查询 \mathcal O(\sqrt n)。这里给出此问题的最优维护方式：

维护 to 数组。该数组只对每段连续 1 的两个端点有定义。在每个 1 连续段的最左端，其值是右端的位置；右端同理。注意 to 数组不跨越块，也就是说每段 1 的左右最多延伸到所在块的左右端。

对于每个块，维护 sum_i 表示该块的答案。

那么区间查询时，散块暴力，跨越块时继承之前的最长连续 1，并配合 sum 数组可以快速计算。

这样写的常数非常小，并且由于维护的信息少，在后续的回滚过程中也有显著常数优势。

有单点修改，那么操作分块。每一块重构 a 数组，对询问按照 x 排序，先只插入不会受修改影响的位置，再单独做块内修改即可。需要使用类似回滚莫队的方式撤销贡献。

序列分块两边常数差不多，块长直接取 \sqrt n，询问分块取 B，则时间复杂度为 \mathcal O(m\sqrt n + n\cdot\frac{m}{B} + mB)。理论上 B=\sqrt n 时复杂度为 \mathcal O(m\sqrt n)，不过没什么实际意义。是不是把 n 开到 10^6 就有点意义了？

注意不要使用任何 vector。用如上方法维护的操作分块做法并不很卡常，块长也可以随便调，码量也较小，轻松跑到了最优解前两页。

AC record

int n, m, a[MAXN], idx[MAXN], len, bcnt, L[BLEN], R[BLEN], chg[MAXN];
int to[MAXN]; ll sum[BLEN], ans[MAXN], prec[MAXN];

struct node {
    int op, x, y, k, id;

    il bool operator < (const node &p) const {
        return k < p.k;
    }
} q[MAXN], q1[MAXN], q2[MAXN];

struct rck {
    int x; ll s;
    int p1, q1, p2, q2;
} cgk[MAXN]; int lcg;

il ll getans(int l, int r) {
    int p = idx[l], q = idx[r];
    if (q - p < 2) {
        ll ans = 0; int cnt = 0;
        rep1(i, l, r) to[i] ? ans += ++cnt : cnt = 0;
        return ans;
    } ll ans = 0; int cnt = 0;
    rep1(i, l, R[p]) to[i] ? ans += ++cnt : cnt = 0;
    rep1(i, p + 1, q - 1) {
        int _l = L[i], _r = R[i];
        if (to[_l] == _r) {
            int len = _r - _l + 1;
            ans += ll(cnt + 1 + cnt + len) * len / 2;
            cnt += len;
            continue;
        }
        if (to[_l]) {
            int len = to[_l] - _l + 1;
            ans -= prec[len];
            ans += ll(cnt + 1 + cnt + len) * len / 2;
        } ans += sum[i];
        if (to[_r]) cnt = _r - to[_r] + 1;
        else cnt = 0;
    }
    rep1(i, L[q], r) to[i] ? ans += ++cnt : cnt = 0;
    return ans;
}

il void insert(int x, int o = 1) {
    int id = idx[x]; rck g; ll &sn = g.s = 0; g.p1 = g.p2 = 0; g.x = x;
    bool flg1 = x != L[id] && to[x - 1], flg2 = x != R[id] && to[x + 1];
    if (flg1 && flg2) {
        to[x] = 1;
        int p = to[x - 1], q = to[x + 1], len = q - p + 1;
        g.q1 = to[g.p1 = p]; to[p] = q;
        g.q2 = to[g.p2 = q]; to[q] = p;
        sn = prec[len] - prec[x - p] - prec[q - x];
    } else if (flg1) {
        int p = to[x - 1], len = x - p + 1;
        g.q1 = to[g.p1 = p];
        to[p] = x; to[x] = p; sn = len;
    } else if (flg2) {
        int p = to[x + 1], len = p - x + 1;
        g.q1 = to[g.p1 = p];
        to[p] = x; to[x] = p; sn = len;
    } else to[x] = x, sn = 1;
    o && (cgk[++lcg] = g, 1); sum[id] += sn;
}

il void rollback() {
    while (lcg) {
        auto [x, s, p1, q1, p2, q2] = cgk[lcg--];
        sum[idx[x]] -= s; to[x] = 0;
        p1 && (to[p1] = q1); p2 && (to[p2] = q2);
    }
}

int tot, pnt[MAXN];
struct edge {
    int to, nxt;
} G[MAXN];

il void add(const int &x, const int &y) {
    G[++tot] = {y, pnt[x]}; pnt[x] = tot;
}

int main() {
    read(n, m); rer(i, 1, n, a);
    rep1(i, 1, n) prec[i] = prec[i - 1] + i;
    rep1(i, 1, m) {
        read(q[i].op, q[i].x, q[i].y); q[i].id = i;
        if (q[i].op == 2) read(q[i].k);
    } len = sqrt(n); bcnt = (n - 1) / len + 1;
    rep1(i, 1, n) idx[i] = (i - 1) / len + 1;
    rep1(i, 1, bcnt) L[i] = R[i - 1] + 1, R[i] = L[i] + len - 1;
    R[bcnt] = n; int qlen = sqrt(11 * m);
    rep1(bid, 1, (m - 1) / qlen + 1) {
        int L = (bid - 1) * qlen + 1, R = min(L + qlen - 1, m), len1 = 0, len2 = 0;
        memset(to, 0, sizeof(int) * (n + 5)); memset(chg, 0, sizeof(int) * (n + 5));
        memset(sum, 0, sizeof sum); memset(pnt, 0, sizeof pnt); tot = 0;
        rep1(i, L, R) if (q[i].op == 2) q2[++len2] = q[i]; else q1[++len1] = q[i];
        sort(q2 + 1, q2 + 1 + len2); int val = 0;
        rep1(i, 1, n) add(a[i], i);
        rep1(i, 1, len2)  {
            auto [op, l, r, x, id] = q2[i];
            rep1(i, 1, len1) chg[q1[i].x] = 1;
            while (val < x) {
                ++val;
                for (int i = pnt[val]; i; i = G[i].nxt) if (!chg[G[i].to]) insert(G[i].to, 0);
            }
            rep2(i, len1, 1) if (q1[i].id < id && chg[q1[i].x]) q1[i].y <= x && (insert(q1[i].x), 1), chg[q1[i].x] = 0;
            rep1(i, 1, len1) if (chg[q1[i].x]) a[q1[i].x] <= x && (insert(q1[i].x), 1), chg[q1[i].x] = 0;
            ans[id] = getans(l, r); rollback();
        }
        rep1(i, L, R) q[i].op == 1 ? a[q[i].x] = q[i].y : (write(ans[i]), putchar('\n'), 1);
    }
    return 0;
}