题解：P13983 数列分块入门 8

· · 题解

思路分析

其实这道题可能用 ODT 会是更好的选择，不过尊重分块。

我们考虑一下分块的惯用套路：序列分段，暴力边角，高速整块。

我们思考一种疑似可行的策略：

如果一个整块内的元素是同一个，那么可以 O(1) 统计这 \sqrt n 个元素的贡献。如果是边角料，或者块内元素不是同一个，则暴力统计贡献。

随后，我们仍然暴力修改边角，中间的部分我们标记为同一个元素。

为什么说是疑似可行呢？单次显然可以卡到 O(n)。下面证明总时间复杂度是 O(n\sqrt n)。

我们选择费用预支分析。要想让一个块被暴力处理，要么是散块，要么是不一致的整块。

不一致的整块只能由散块修改贡献出来。因此我们考虑在修改散块时直接将时间复杂度乘二，后面直接将中间的整块视为元素一致，可以视为 O(1)。

那显然每一步的时间复杂度都是严格的 O(\sqrt n) 了。代码如下：

#include<bits/stdc++.h>
using namespace std;
struct IO {
#define mxsz (1 << 20)
    char buf[mxsz], * p1, * p2;
    char pbuf[mxsz], * pp;
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, mxsz, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
#ifndef sipt
    inline int read() {
        int r = 0; char c = gc(); while (c < '0' || c>'9') c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return r;
    }
#else
    inline int read() {
        int r = 0; char c = gc(); bool rev = 0;
        while (c < '0' || c>'9') rev |= (c == '-'), c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return rev ? ~r + 1 : r;
    }
#endif
    inline void push(const char& c) {
        if (pp - pbuf == mxsz) fwrite(pbuf, 1, mxsz, stdout), pp = pbuf;
        *pp++ = c;
    }
    inline void write(int x) {
        static char sta[22]; int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) push(sta[--top] ^ 48);
    }
    inline void write(int x, char opc) {
#ifdef sopt
        if (x < 0) push('-'), x = ~x + 1;
#endif
        write(x), push(opc);
    }
} io;
int n, a[300005], sz, tv[300005];
#define blk(i) (i / sz)
inline void pia(int p) {
    if (tv[p] == -1) return;
    for (int i = p * sz; i != (p + 1) * sz; ++i)
        a[i] = tv[p];
    tv[p] = -1;
}
signed main() {
    ios::sync_with_stdio(0);
    sz = sqrt(n = io.read()) * 0.5; memset(tv, -1, sizeof tv);
    for (int i = 0; i != n; ++i) a[i] = io.read();
    for (int i = 1, l, r, c; i <= n; ++i) {
        l = io.read() - 1, r = io.read() - 1, c = io.read();
        int bl = blk(l), br = blk(r), ans = 0;
        if (bl == br) {
            pia(bl);
            for (int i = l; i <= r; ++i)
                a[i] != c ? a[i] = c : ans++;
            io.write(ans, '\n');
            continue;
        }
        pia(bl); pia(br);
        for (int i = l; i != (bl + 1) * sz; ++i)
            a[i] != c ? a[i] = c : ans++;
        for (int i = br * sz; i <= r; ++i)
            a[i] != c ? a[i] = c : ans++;
        for (int i = bl + 1; i < br; ++i)
            if (tv[i] != -1)
                if (tv[i] != c) tv[i] = c;
                else ans += sz;
            else {
                for (int j = i * sz; j != (i + 1) * sz; ++j)
                    a[j] != c ? a[j] = c : ans++;
                tv[i] = c;
            }
        io.write(ans, '\n');
    }
}