「BZOJ 3337」ORZJRY I-块状链表

题意很清晰，直接给链接。

链接

BZOJ 3337

题解

先 %nzhtl1477 大爷的 ODT，太强辣!!!

然而并不会 ODT，还是写块链吧，~~听说 BZOJ 有 O2，那我们就大胆的用 list 套 vector 写块链吧~~。

首先操作 1, 2 是基础操作，就不多说了。
先看操作 5, 6, 7，我们维护 $\text{delta}, \text{cover}, \text{sum}$ 标记，表示增加值和覆盖值及元素和，对于连续的块打标记，对于零散的元素暴力修改即可，暴力修改的时候不要忘记更新 $\text{sum}$，值得注意的是后出现的覆盖值是可以清除 $\text{delta}$ 标记的。

然后操作 3，我们维护一个 $\text{rev}$ 标记，下传的时候反转，注意标记不要过于频繁地下传，用到的时候在下传，否则可能会 TLE。我们先将区间 $[l, r]$ 从块链中拆分出来，即 split(l - 1), split(r)，然后对于区间 $[l, r]$ 中的每一块都打上反转标记，但我们发现只打标记还不够，区间中的整块也要翻转，这里就用到了 std::list::splice 方法了。

void splice( const_iterator pos, list& other )，把 $\text{other}$ 接在 $\text{pos}$ 前面，并清空 $\text{other}$，时间消耗为常数。
void splice( const_iterator pos, list& other, const_iterator first, const_iterator last)，把 $\text{other}$ 中的 $[first, last)$ 接在 $\text{pos}$ 前面并清空对应区间，时间消耗对应区间长度。

所以我们可以先开一个临时的 list，然后将 $[l, r]$ splice 进去，调用 std::list::reverse 即完成了翻转，然后再用第一种 splice 接回去。

对于操作 5，我们同样使用 splice~~（list 的 splice 真好用）~~，先提取区间 $[l, r]$，然后 splice 出 $(r - k, r]$，再 splice 接回去。

对于操作 8, 9，由于还要查 rank，我们显然还维护了一个排序后的数组，有了这个数组，这两个操作就很容易了，注意一下 $\text{delta}$ 和 $\text{cover}$ 标记的处理就可以了。

对于操作 11，先暴力统计零散元素中 $< \text{val}$ 的个数，然后对于整块的元素，先判断是否存在 $\text{cover}$ 标记，看其是否会产生整块的贡献，同时也避免了标记下传的巨大常数，若不存在 $\text{cover}$ 标记，我们在考虑 $\text{delta}$ 标记，由于是整块增加了 $\text{delta}$，我们完全可以看做是 $\text{val} - \text{delta}$，而块内元素不变，所以我们在这块所维护的排序数组中二分就可以快速统计出当前块 $< \text{val} - \text{delta}$ 的个数，累加即可。

对于操作 10，二分第 $k$ 小的元素，我们先求出所有元素最大值作为上界，然后统计 $\leq \text{mid}$ 元素的个数，判断是否 $\geq k$，对于统计，同操作 11，我们还是先判断是否有 $\text{cover}$，然后二分 $mid - delta$

最终的结果也证明了 STL 写法的块状链表确实不慢，虽然快不过 ODT，但目前应该是块链中最快的，~~想一想 vector 暴力能过普通平衡树~~，所以 std::list 套 std::vector 可能也是一种优越的实现方法。

代码

~~我真的不是把每个操作都复制了一遍（雾）~~

/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「BZOJ 3337」ORZJRY I 30-09-2017
 * 块状链表
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}  // end IO

namespace {

#define long long long
const int MAXN = 100000;
int blockCount;
int blockSize;

typedef std::vector<int> Vector;

struct Block {
    Vector num, sorted;
    int delta, cover;
    bool rev;
    long sum;

    Block() : delta(0), cover(0), rev(false), sum(0) {}

    inline void pushDown() {
        if (rev) std::reverse(num.begin(), num.end()), rev = false;
        if (delta) {
            for (register int i = 0; i < num.size(); i++)
                num[i] += delta, sorted[i] += delta;
            sum += (long)delta * num.size();
            delta = 0;
        }
        if (cover) {
            for (register int i = 0; i < num.size(); i++)
                num[i] = sorted[i] = cover;
            sum = (long)cover * num.size();
            cover = 0;
        }
    }

    inline long getSum() {
        return cover ? (long)cover * num.size()
                     : sum + (long)delta * num.size();
    }

    inline long getMax() { return cover ? cover : sorted.back() + (long)delta; }

    inline long getMin() { return cover ? cover : sorted[0] + (long)delta; }
};

typedef std::list<Block> List;
typedef List::iterator Iterator;
List d;

inline void build(const int *a, const int n) {
    blockSize = std::max((sqrt(n) + 1) * 4 / 3, 1.0);
    blockCount = ceil((double)n / blockSize);
    d.resize(blockCount);
    register Iterator it = d.begin();
    for (register int i = 0, j = 0; i < blockCount; i++, it++) {
        j += blockSize;
        it->num.assign(a + j - blockSize, a + std::min(j, n));
        it->sorted.assign(a + j - blockSize, a + std::min(j, n));
        for (Vector::iterator v = it->num.begin(); v != it->num.end(); v++)
            it->sum += *v;
        std::sort(it->sorted.begin(), it->sorted.end());
    }
}

using IO::io;

inline void find(int cur, Iterator &it, int &pos) {
    for (it = d.begin(); (int)(cur - it->num.size()) >= 0 && it != d.end();)
        cur -= it->num.size(), it++;
    pos = cur;
    it->pushDown();
}

inline void split(Iterator cur, int pos) {
    if (pos == cur->num.size()) return;
    Iterator it = cur;
    it = d.insert(++it, Block());
    cur->pushDown();
    it->num.assign(cur->num.begin() + pos, cur->num.end());
    cur->num.erase(cur->num.begin() + pos, cur->num.end());
    cur->sorted.erase(cur->sorted.begin() + pos, cur->sorted.end());
    it->sorted.assign(it->num.begin(), it->num.end());
    for (Vector::iterator v = it->num.begin(); v != it->num.end(); v++)
        it->sum += *v;
    cur->sum -= it->sum;
    cur->sorted.assign(cur->num.begin(), cur->num.end());
    std::sort(it->sorted.begin(), it->sorted.end());
    std::sort(cur->sorted.begin(), cur->sorted.end());
}

inline void merge(Iterator cur, Iterator suc) {
    cur->pushDown();
    suc->pushDown();
    cur->num.insert(cur->num.end(), suc->num.begin(), suc->num.end());
    cur->sorted.insert(cur->sorted.end(), suc->sorted.begin(),
                       suc->sorted.end());
    cur->sum += suc->sum;
    std::sort(cur->sorted.begin(), cur->sorted.end());
    d.erase(suc);
}

inline void maintain(Iterator cur) {
    for (register Iterator tmp; cur != d.end(); cur++) {
        if (cur->num.size() > blockSize * 2) {
            split(cur, cur->num.size() / 2);
        } else if (cur->num.size() < blockSize / 2) {
            tmp = cur, tmp++;
            if (tmp == d.end())
                break;
            else if (tmp->num.size() + cur->num.size() <= blockSize * 2)
                merge(cur, tmp);
        }
    }
}

inline void insert(int x, int v) {
    register Iterator cur;
    register int pos;
    find(--x, cur, pos);
    cur->num.insert(cur->num.begin() + pos + 1, v);
    cur->sorted.insert(
        std::lower_bound(cur->sorted.begin(), cur->sorted.end(), v), v);
    cur->sum += v;
    maintain(cur);
}

inline void erase(int x) {
    register Iterator cur;
    register int pos, v;
    find(--x, cur, pos);
    cur->sum -= cur->num[pos];
    cur->sorted.erase(std::lower_bound(cur->sorted.begin(), cur->sorted.end(),
                                       cur->num[pos]));
    cur->num.erase(cur->num.begin() + pos);
    maintain(cur);
}

inline void reverse(int l, int r) {
    l--, r--;
    std::list<Block> tmp;
    Iterator L, R, p;
    register int posL, posR;
    find(l - 1, L, posL);
    if (posL + 1 > 0) split(L, posL + 1), L++;
    find(r, R, posR);
    split(R, posR + 1);
    tmp.splice(tmp.begin(), d, L, ++R);
    for (Iterator v = tmp.begin(); v != tmp.end(); v++) v->rev ^= 1;
    tmp.reverse();
    L = R;
    if (L != d.begin()) L--;
    d.splice(R, tmp);
    maintain(L);
}

inline void revolve(int l, int r, int k) {
    l--, r--;
    std::list<Block> tmp;
    Iterator L, R, p, K;
    register int posL, posR, posK;
    find(l - 1, L, posL);
    if (posL + 1 > 0) split(L, posL + 1), L++;
    find(r - k, K, posK);
    if (posK + 1 > 0) split(K, posK + 1), K++;
    find(r, R, posR);
    split(R, posR + 1);
    tmp.splice(tmp.begin(), d, K, ++R);
    p = L;
    if (p != d.begin())
        p--;
    else
        p = d.end();
    d.splice(L, tmp);
    maintain(p == d.end() ? d.begin() : p);
}

inline void add(int l, int r, int v) {
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++) L->num[i] += v;
        L->sum += (posR - posL + 1ll) * v;
        L->sorted.assign(L->num.begin(), L->num.end());
        std::sort(L->sorted.begin(), L->sorted.end());
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++) L->num[i] += v;
            L->sum += (L->num.size() - posL) * (long)v;
            L->sorted.assign(L->num.begin(), L->num.end());
            std::sort(L->sorted.begin(), L->sorted.end());
            L++;
        }
        for (; L != R; L++) {
            if (L->cover)
                L->cover += v;
            else
                L->delta += v;
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++) R->num[i] += v;
        R->sum += (posR + 1) * v;
        R->sorted.assign(R->num.begin(), R->num.end());
        std::sort(R->sorted.begin(), R->sorted.end());
    }
}

inline void cover(int l, int r, int v) {
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++)
            L->sum += v - L->num[i], L->num[i] = v;
        L->sorted.assign(L->num.begin(), L->num.end());
        std::sort(L->sorted.begin(), L->sorted.end());
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++)
                L->sum += v - L->num[i], L->num[i] = v;
            L->sorted.assign(L->num.begin(), L->num.end());
            std::sort(L->sorted.begin(), L->sorted.end());
            L++;
        }
        for (; L != R; L++) {
            if (L->delta) L->delta = 0;
            L->cover = v;
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++)
            R->sum += v - R->num[i], R->num[i] = v;
        R->sorted.assign(R->num.begin(), R->num.end());
        std::sort(R->sorted.begin(), R->sorted.end());
    }
}

inline long querySum(int l, int r) {
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    register long ret = 0;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++) ret += L->num[i];
        return ret;
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++)
                ret += L->num[i];
            L++;
        }
        for (; L != R; L++) {
            ret += L->getSum();
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++) ret += R->num[i];
        return ret;
    }
}

inline long queryDiff(int l, int r) {
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    register long min = LLONG_MAX, max = LLONG_MIN;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++) {
            min = std::min(min, (long)L->num[i]);
            max = std::max(max, (long)L->num[i]);
        }
        return max - min;
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++) {
                min = std::min(min, (long)L->num[i]);
                max = std::max(max, (long)L->num[i]);
            }
            L++;
        }
        for (; L != R; L++) {
            min = std::min(min, L->getMin());
            max = std::max(max, L->getMax());
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++) {
            min = std::min(min, (long)L->num[i]);
            max = std::max(max, (long)L->num[i]);
        }
        return max - min;
    }
}

inline long queryAbs(int l, int r, int v) {
    register long ret = LLONG_MAX;
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++)
            ret = std::min(ret, llabs(L->num[i] - v));
        return ret;
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++)
                ret = std::min(ret, llabs(L->num[i] - v));
            L++;
        }
        register int tmp, pos;
        for (; L != R; L++) {
            if (L->cover) {
                ret = std::min(ret, llabs(L->cover - v));
                continue;
            }
            tmp = v - L->delta;
            pos = std::lower_bound(L->sorted.begin(), L->sorted.end(), tmp) -
                  L->sorted.begin();
            if (pos < L->sorted.size())
                ret = std::min(ret, (long)L->sorted[pos] - tmp);
            if (pos) ret = std::min(ret, (long)tmp - L->sorted[pos - 1]);
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++)
            ret = std::min(ret, llabs(R->num[i] - v));
        return ret;
    }
}

inline long queryRank(int l, int r, int v) {
    l--, r--;
    Iterator L, R;
    register int posL, posR;
    register int ret = 0;
    find(l, L, posL), find(r, R, posR);
    if (L == R) {
        L->pushDown();
        for (register int i = posL; i <= posR; i++) ret += (L->num[i] < v);
        return ret;
    } else {
        if (posL > 0) {
            L->pushDown();
            for (register int i = posL; i < L->num.size(); i++)
                ret += (L->num[i] < v);
            L++;
        }
        register int tmp;
        for (; L != R; L++) {
            if (L->cover) {
                if (L->cover < v) ret += L->num.size();
                continue;
            }
            tmp = v - L->delta;
            ret += std::lower_bound(L->sorted.begin(), L->sorted.end(), tmp) -
                   L->sorted.begin();
        }
        R->pushDown();
        for (register int i = 0; i <= posR; i++) ret += (R->num[i] < v);
        return ret;
    }
}

inline int divide(std::vector<int> &val, int l, int r, int x) {
    l--;
    for (register int mid; r - l > 1;) {
        mid = l + r >> 1;
        if (val[mid] <= x)
            l = mid;
        else
            r = mid;
    }
    return l;
}

inline int check(Iterator L, Iterator R, int val) {
    Iterator ptr = L;
    register int cnt = 0, pos, tmp;
    if (R != d.end()) R++;
    do {
        if (ptr->cover) {
            if (ptr->cover <= val) cnt += ptr->sorted.size();
            ptr++;
            continue;
        }
        tmp = val - ptr->delta;
        pos = divide(ptr->sorted, 0, ptr->sorted.size(), tmp);
        cnt += pos + 1;
        ptr++;
    } while (ptr != R);
    return cnt;
}

inline long getGlobalMax() {
    register long max = LLONG_MIN;
    for (Iterator p = d.begin(); p != d.end(); p++)
        max = std::max(max, p->getMax());
    return max;
}

inline long querySelect(int left, int right, int k) {
    left--, right--;
    Iterator L, R, ptr;
    register int posL, posR, pos;
    register long l, r, mid;
    find(left - 1, L, posL);
    if (posL + 1 > 0) split(L, posL + 1), L++;
    find(right, R, posR);
    split(R, posR + 1);
    l = 0;
    r = getGlobalMax();
    while (l != r) {
        mid = (l + r) >> 1;
        if (check(L, R, mid) >= k)
            r = mid;
        else
            l = mid + 1;
    }
    maintain(L);
    return l;
}

#ifdef DBG
// for gdb
void debugPrint(const int x) { std::cerr << x << ' '; }

void showNum(Iterator it) {
    it->pushDown();
    std::for_each(it->num.begin(), it->num.end(), debugPrint);
    std::endl(std::cerr);
}

void showSorted(Iterator it) {
    it->pushDown();
    std::for_each(it->sorted.begin(), it->sorted.end(), debugPrint);
    std::endl(std::cerr);
}

void showAll(Iterator it) { showNum(it), showSorted(it); }

void showBlockListNum() {
    std::cerr << "showBlockListNum begin" << std::endl;
    for (Iterator it = d.begin(); it != d.end(); it++) showNum(it);
    std::cerr << "showBlockListNum done" << std::endl << std::endl;
}

void showBlockListSorted() {
    std::cerr << "showBlockListSorted begin" << std::endl;
    for (Iterator it = d.begin(); it != d.end(); it++) showSorted(it);
    std::cerr << "showBlockListSorted done" << std::endl << std::endl;
}

void showBlockListAll() {
    std::cerr << "showBlockListAll begin" << std::endl;
    for (Iterator it = d.begin(); it != d.end(); it++) showAll(it);
    std::cerr << "showBlockListAll done" << std::endl << std::endl;
}

Iterator getBlock(int k) {
    Iterator it = d.begin();
    for (register int i = 0; i < k; i++) it->pushDown(), it++;
    return it;
}
#endif

inline void solve() {
    register int n, m;
    io >> n;
    static int a[MAXN];
    for (register int i = 0; i < n; i++) io >> a[i];
    build(a, n);
    io >> m;
    for (register int cmd, x, y, v, k; m--;) {
        io >> cmd;
        switch (cmd) {
            case 1: {
                io >> x >> v;
                insert(x, v);
                break;
            }
            case 2: {
                io >> x;
                erase(x);
                break;
            }
            case 3: {
                io >> x >> y;
                reverse(x, y);
                break;
            }
            case 4: {
                io >> x >> y >> k;
                revolve(x, y, k);
                break;
            }
            case 5: {
                io >> x >> y >> v;
                add(x, y, v);
                break;
            }
            case 6: {
                io >> x >> y >> v;
                cover(x, y, v);
                break;
            }
            case 7: {
                io >> x >> y;
                io << querySum(x, y) << '\n';
                break;
            }
            case 8: {
                io >> x >> y;
                io << queryDiff(x, y) << '\n';
                break;
            }
            case 9: {
                io >> x >> y >> v;
                io << queryAbs(x, y, v) << '\n';
                break;
            }
            case 10: {
                io >> x >> y >> k;
                io << querySelect(x, y, k) << '\n';
                break;
            }
            case 11: {
                io >> x >> y >> v;
                io << queryRank(x, y, v) << '\n';
                break;
            }
        }
    }
}

#undef long
}

int main() {
#ifdef DBG
    freopen("sample/1.in", "r", stdin);
#endif
    solve();
    return 0;
}

# Data Structure

「BZOJ 3337」ORZJRY I-块状链表

链接

题解

代码

Comments

Tag Cloud

Recent

Categories

Tags

Links

Recent

Categories

Tags

Links

Your browser is out-of-date!