MENU

洛谷P4119/BZOJ5145/HDU6079 [Ynoi2018]未来日记/Yuno And Claris

洛谷P4119

BZOJ5145

HDU6079

先考虑如何求区间第k小值。对序列和权值都进行分块,设$b_{i,j}$表示前$j$块中权值在$i$块内的数字个数,$c_{i,j}$表示前$j$块中数字$i$的出现次数。那么对于一个询问$[l,r]$,首先将零碎部分的贡献加入到临时数组$tb$和$tc$中,然后枚举答案位于哪一块,确定位于哪一块之后再暴力枚举答案即可在$O(\sqrt{n})$的时间内求出区间第$k$小值。
接着考虑如何实现区间$[l,r]$内$x$变成$y$的功能。显然对于零碎的两块,可以直接暴力重构整块。对于中间的每个整块,如果某一块不含$x$,那么无视这一块;否则如果这一块不含$y$,那么只需要将$x$映射成$y$;否则这一块既有$x$又有$y$,这意味着$x$与$y$之间发生了合并,不妨直接暴力重构整块。因为有$c$数组,我们可以在$O(1)$的时间内知道某一块是否有某个数。
考虑什么情况下会发生重构,也就是一个块内发生了一次合并的时候。一开始长度为$n$的序列会提供$O(n)$次合并的机会,而每次修改会对零碎的两块各提供一次机会,故总合并次数不超过$O(n+m)$,因此当发生合并时直接重构并不会影响复杂度。
那么现在每块中的转换情况只可能是一条条互不相交的链,只需要记录每个初值转换后是什么,以及每个现值对应哪个初值即可。遇到查询的时候,我们需要知道零碎部分每个位置的值,不妨直接重构那两块,然后遍历一遍原数组$a$即可得到每个位置的值。
在修改的时候,还需要同步维护$b$和$c$数组,因为只涉及两个权值,因此暴力修改$j$这一维也是可以承受的。
总时间复杂度$O((n+m)\sqrt{n})$。

2017 Multi-University Training Contest 4 solutions BY 陈松杨

最开始TLE随便卡卡常居然BZOJ rk2了。。。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
struct io {
#define _L ((1<<21)+1)
    char ibuf[_L], *iS, *iT, obuf[_L], *oS, *oT, c, st[20], tp;
    void flush() {
        fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)flush();
    }
    char gc() {
        return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, _L, stdin), (iS == iT ? EOF : *iS++)) : *iS++;
    }
    template<class T>T rd() {
        register T x = 0;
        while (!isdigit(c = gc()));
        for (; isdigit(c); c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(register T x, char y) {
        print(x), putc(y);
    }
    template<class T>void print(register T x) {
        if (!x) {
            putc('0');
            return;
        }
        for (tp = 0; x; st[tp++] = x % 10 + 48, x /= 10);
        for (tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + _L - 1) {}
    ~io() {
        fwrite(obuf, 1, oS - obuf, stdout);
    }

} ip;
int n = ip.rd<int>(), m = ip.rd<int>(), lim = n >> 9, a[100001], end[200], f[200][100001], g[200][100001], tb[200], tc[100001], b[200][200], c[100001][200], q[2000];
bool flag[200];
__attribute__((always_inline))void rebuild(int x) {
    if (!flag[x])return;
    flag[x] = 0;
    int r = end[x];
    for (register int i = x << 9; i <= r; ++i)f[x][a[i]] = 0, a[i] = g[x][a[i]];
    for (register int i = x << 9; i <= r; ++i)f[x][a[i]] = g[x][a[i]] = a[i];
}
__attribute__((always_inline))void find(int l, int r, int k) {
    int L = l >> 9, R = r >> 9, t;
    register int i;
    rebuild(L);
    if (L != R)rebuild(R);
    if (L + 1 >= R) {
        int len = r - l + 1;
        memcpy(q, a + l, 4 * len), std::nth_element(q, q + k - 1, q + len), ip.print(q[k - 1], '\n');
        return;
    }
    memset(tb, 0, sizeof tb);
    for (i = l; i >> 9 == L; ++i)++tb[a[i] >> 9], ++tc[a[i]];
    for (i = r; i >> 9 == R; --i)++tb[a[i] >> 9], ++tc[a[i]];
    for (i = 0;; ++i) {
        t = b[i][R - 1] - b[i][L] + tb[i];
        if (k > t)k -= t;
        else break;
    }
    for (i <<= 9;; ++i) {
        t = c[i][R - 1] - c[i][L] + tc[i];
        if (k > t)k -= t;
        else {
            ip.print(i, '\n');
            break;
        }
    }
    for (i = l; i >> 9 == L; ++i)--tc[a[i]];
    for (i = r; i >> 9 == R; --i)--tc[a[i]];
}
__attribute__((always_inline))void replace(int l, int r, int x, int y) {
    if (x == y)return;
    int L = l >> 9, R = r >> 9, X = x >> 9, Y = y >> 9, t, tL = 0, tR = 0;
    register int i;
    if (L == R) {
        if (!f[L][x])return;
        rebuild(L);
        for (i = l, t = 0; i <= r; ++i)if (a[i] == x)a[i] = y, ++t;
        if (t) {
            f[L][y] = g[L][y] = y;
            if (X == Y)for (i = L; i <= lim; ++i)c[x][i] -= t, c[y][i] += t;
            else for (i = L; i <= lim; ++i)b[X][i] -= t, b[Y][i] += t, c[x][i] -= t, c[y][i] += t;
        }
        t = c[x][L];
        if (L)t -= c[x][L - 1];
        if (!t)f[L][x] = 0;
        return;
    }
    if (f[L][x]) {
        rebuild(L);
        for (i = l, t = 0; i >> 9 == L; ++i)if (a[i] == x)a[i] = y, ++t;
        tL = t;
        if (t)f[L][y] = g[L][y] = y, b[X][L] -= t, b[Y][L] += t, c[x][L] -= t, c[y][L] += t;;
        t = c[x][L];
        if (L)t -= c[x][L - 1];
        if (!t)f[L][x] = 0;
    }
    if (f[R][x]) {
        rebuild(R);
        for (i = r, t = 0; i >> 9 == R; --i)if (a[i] == x)a[i] = y, ++t;
        tR = t;
        if (t)f[R][y] = g[R][y] = y;
        if (c[x][R] - t == c[x][R - 1])f[R][x] = 0;
    }
    for (i = L + 1; i < R; ++i)if (f[i][x]) {
        if (f[i][y]) {
            rebuild(i);
            for (register int j = i << 9, k = i + 1 << 9; j < k; ++j)if (a[j] == x)a[j] = y;
            f[i][x] = 0;
            continue;
        }
        g[i][f[i][y] = f[i][x]] = y, f[i][x] = 0, flag[i] = 1;
    }
    if (L + 1 == R) {
        if (!(t = tL + tR))return;
        if (X == Y) {
            for (i = R; i <= lim; ++i)c[x][i] -= t, c[y][i] += t;
            return;
        }
        for (i = R; i <= lim; ++i)b[X][i] -= t, b[Y][i] += t, c[x][i] -= t, c[y][i] += t;
        return;
    }
    int o = c[x][L];
    if (X == Y) {
        for (i = L + 1; i < R; ++i)t = c[x][i] - o, c[x][i] -= t, c[y][i] += t;
        t += tR;
        if (!t)return;
        for (; i <= lim; ++i)c[x][i] -= t, c[y][i] += t;
        return;
    }
    for (i = L + 1; i < R; ++i)t = c[x][i] - o, b[X][i] -= t, b[Y][i] += t, c[x][i] -= t, c[y][i] += t;
    t += tR;
    if (!t)return;
    for (; i <= lim; ++i)b[X][i] -= t, b[Y][i] += t, c[x][i] -= t, c[y][i] += t;
}
main() {
    for (register int i = 1, j; i <= n; ++i)a[i] = ip.rd<int>(), end[i >> 9] = i, j = i >> 9, f[j][a[i]] = g[j][a[i]] = a[i], ++b[a[i] >> 9][j], ++c[a[i]][j];
    for (register int i = 0; i <= lim; ++i)for (register int j = 1; j <= lim; ++j)b[i][j] += b[i][j - 1];
    for (register int i = 1; i <= n; ++i)for (register int j = 1; j <= lim; ++j)c[i][j] += c[i][j - 1];
    char opt;
    int l, r, x;
    while (m--) {
        opt = ip.rd<char>(), l = ip.rd<int>(), r = ip.rd<int>(), x = ip.rd<int>();
        switch (opt) {
            case 1:
                replace(l, r, x, ip.rd<int>());
                break;
            default:
                find(l, r, x);
        }
    }
}
Leave a Comment

captcha
请输入验证码