题解 - [Ynoi2007] rgxsxrs - 浴谷

Macesuted QWQ LV 7 SU @ 2022-3-22 7:38:21

Statement

给定一个长为 $n$ 的序列 $a$ ，需要实现 $m$ 次操作：

1 l r x：表示将区间 $[l,~r]$ 中所有 $>x$ 的元素减去 $x$ 。
2 l r：表示询问区间 $[l,~r]$ 的和，最小值，最大值。

强制在线， $n,~m \le 5 \times 10^5,~a_i \le 10^9$ 。

Solution

考虑以 $2$ 进制进行值域分块，第 $i$ 块开动态开点线段树存储所有满足 $a_i \in [2^i,~2^{i+1})$ 的位置的信息。

考虑对于 $1$ 操作，我们枚举每一个值域块，将该块内下标在 $[l,~r]$ 之间的元素拿出，进行判断：

若该块所有元素值均 $>x$ ：对这些元素打上 $-x$ 标记即可。
若该块所有元素值均 $\le x$ ：不进行任何操作。
若不满足上述两个条件：在线段树上向子树递归进行修改操作。

考虑分析此处暴力递归的时间复杂度，容易发现在某块内每次成功的修改都会让被修改元素减少至少一半。显然单个元素最多被修改 $\log_2 a_i$ 次，因此全局总共花在暴力递归上的复杂度为 $O(n \log_2 a_i)$ 。

在每次修改后，一些 $a_i$ 值减小后可能会因为过小而需要被分配到编号更小的块中，我们可以在线段树每个节点上维护子树最小值，每次修改完成后暴力二分找出过小的位置，将其从当前块线段树上暴力拆出，插入到更小编号的块的线段树内。考虑此操作总时间复杂度，因为一共只有 $\log_2 a_i$ 个块而每次结点只会从当前块到编号更小的块，因此每个元素最多只会在块间移动 $\log_2 a_i$ 次，所以花在此操作上的全局总时间复杂度为 $O(n \log_2 a_i \log_2 n)$ 。

对于 2 操作，我们只要将每块内的 $[l,~r]$ 部分答案取出合并起来就可以了。

此时总时间复杂度 $O(n \log_2 n \log_2 a_i)$ ，空间复杂度 $O(n \log_2 a_i)$ 。

我们发现这样的空间复杂度不足以通过此题，我们考虑线段树底层以 $\log_2 a_i$ 块长分块，则每棵线段树叶子节点数量为 $\frac {n} {\log_2 a_i}$ ，空间复杂度降为 $O(n)$ ，可以通过此题。

由于此题较卡常，可以考虑根据代码运行情况调整分块的进制和线段树底层分块块长。

Code

本人代码使用指针版动态开点线段树，线段树底层块内使用链表储存，14 进制值域分块，线段树底层块长 500（由于常数比较大，小块长一直 TLE 一个点，但是这个接近 $\sqrt n$ 的块长出乎意料地跑得飞快）。

View On Github

Code

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 * @brief
 *      My solution: https://www.macesuted.cn/article/lg7447/
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (register int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
inline T read() {
    register T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
inline void write(const T& t) {
    register T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 500005
#define blockLen 500

typedef pair<int, int> pii;

vector<pii> empty;

class SegmentTree {
   public:
    struct AnsType {
        long long sum;
        int minVal, maxVal;
        AnsType(void) { sum = 0, minVal = 0x3f3f3f3f, maxVal = 0; }
        AnsType(long long _sum, int _minVal, int _maxVal) { sum = _sum, minVal = _minVal, maxVal = _maxVal; }
        inline AnsType operator+(const AnsType& oth) const {
            return (AnsType){sum + oth.sum, min(minVal, oth.minVal), max(maxVal, oth.maxVal)};
        }
    };

   private:
    struct Node {
        int minVal, maxVal, size;
        long long sum, lazy;
        Node *l, *r;
        vector<pii> rec;
        Node(void) { l = r = NULL, minVal = 0x3f3f3f3f, maxVal = sum = lazy = size = 0; }
    };

    Node* root;
    int n;

    void update(Node* p, int l, int r, long long delta) {
        if (r - l + 1 <= blockLen) {
            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) i->second -= delta;
            return recalc(p, l, r);
        }
        p->lazy += delta, p->minVal -= delta, p->maxVal -= delta, p->sum -= p->size * delta;
        return;
    }
    void recalc(Node* p, int l, int r) {
        p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = p->rec.size();
        for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
            p->sum += i->second, p->minVal = min(p->minVal, i->second), p->maxVal = max(p->maxVal, i->second);
        return;
    }
    void pushDown(Node* p, int l, int r) {
        if (p == NULL) return;
        if (!p->lazy) return;
        int mid = (l + r) >> 1;
        if (p->l != NULL) update(p->l, l, mid, p->lazy);
        if (p->r != NULL) update(p->r, mid + 1, r, p->lazy);
        p->lazy = 0;
        return;
    }
    inline void pushUp(Node* p) {
        p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = 0;
        if (p->l != NULL)
            p->minVal = min(p->minVal, p->l->minVal), p->maxVal = max(p->maxVal, p->l->maxVal),
            p->sum += p->l->sum, p->size += p->l->size;
        if (p->r != NULL)
            p->minVal = min(p->minVal, p->r->minVal), p->maxVal = max(p->maxVal, p->r->maxVal),
            p->sum += p->r->sum, p->size += p->r->size;
        return;
    }
    void insert(Node*& p, int l, int r, int qp, int val) {
        if (p == NULL) p = new Node();
        if (r - l + 1 <= blockLen) {
            bool find = false;
            for (vector<pii>::iterator i = p->rec.begin(); !find && i != p->rec.end(); i++)
                if (i->first == qp) i->second = val, find = true;
            if (!find) p->rec.push_back((pii){qp, val});
            return recalc(p, l, r);
        }
        pushDown(p, l, r);
        int mid = (l + r) >> 1;
        qp <= mid ? insert(p->l, l, mid, qp, val) : insert(p->r, mid + 1, r, qp, val);
        return pushUp(p);
    }
    void update(Node* p, int l, int r, int ql, int qr, long long val) {
        if (p == NULL) return;
        if (p->maxVal <= val) return;
        if (ql <= l && r <= qr && p->minVal > val) return update(p, l, r, val);
        if (r - l + 1 <= blockLen) {
            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                if (ql <= i->first && i->first <= qr && i->second > val) i->second -= val;
            return recalc(p, l, r);
        }
        pushDown(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(p->l, l, mid, ql, qr, val);
        if (qr > mid) update(p->r, mid + 1, r, ql, qr, val);
        return pushUp(p);
    }
    AnsType getAns(Node* p, int l, int r, int ql, int qr) {
        if (p == NULL) return (AnsType){};
        if (ql <= l && r <= qr) return (AnsType){p->sum, p->minVal, p->maxVal};
        if (r - l + 1 <= blockLen) {
            AnsType ans = (AnsType){0, 0x3f3f3f3f, 0};
            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                if (ql <= i->first && i->first <= qr)
                    ans.sum += i->second, ans.minVal = min(ans.minVal, i->second), ans.maxVal = max(ans.maxVal, i->second);
            return ans;
        }
        pushDown(p, l, r);
        int mid = (l + r) >> 1;
        AnsType answer;
        if (ql <= mid) answer = answer + getAns(p->l, l, mid, ql, qr);
        if (qr > mid) answer = answer + getAns(p->r, mid + 1, r, ql, qr);
        return answer;
    }
    void findEmpty(Node*& p, int l, int r, int limit) {
        if (p == NULL) return;
        if (p->minVal >= limit) return;
        if (r - l + 1 <= blockLen) {
            static vector<pii> cache;
            cache.clear();
            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                (i->second < limit ? empty : cache).push_back(*i);
            p->rec = cache;
            recalc(p, l, r);
            if (p->size == 0) delete p, p = NULL;
            return;
        }
        pushDown(p, l, r);
        int mid = (l + r) >> 1;
        findEmpty(p->l, l, mid, limit), findEmpty(p->r, mid + 1, r, limit);
        pushUp(p);
        if (p->size == 0) delete p, p = NULL;
        return;
    }

   public:
    SegmentTree(void) { root = NULL; }
    inline void resize(int _n) { return n = _n, void(); }
    inline void insert(int p, int val) { return insert(root, 1, n, p, val); }
    inline void update(int l, int r, long long delta) { return update(root, 1, n, l, r, delta); }
    inline AnsType getAns(int l, int r) { return getAns(root, 1, n, l, r); }
    inline void findEmpty(int limit) { return findEmpty(root, 1, n, limit); }
};

SegmentTree tree[8];
long long pow14[8];

int log14(int x) {
    int t = 0;
    while (t < 7 && pow14[t + 1] <= x) t++;
    return t;
}

int main() {
    pow14[0] = 1;
    for (register int i = 1; i < 8; i++) pow14[i] = pow14[i - 1] * 14;
    int n = read<int>(), m = read<int>();
    for (register int i = 0; i < 8; i++) tree[i].resize(n);
    for (register int i = 1, t; i <= n; i++) {
        t = read<int>();
        tree[log14(t)].insert(i, t);
    }
    int lastans = 0;
    while (m--) {
        if (read<int>() == 1) {
            int l = read<int>(), r = read<int>(), x = read<int>();
            l ^= lastans, r ^= lastans, x ^= lastans;
            for (register int i = 0; i < 8; i++) tree[i].update(l, r, x), tree[i].findEmpty(1 << (2 * i));
            for (vector<pii>::iterator i = empty.begin(); i != empty.end(); i++)
                tree[log14(i->second)].insert(i->first, i->second);
            empty.clear();
        } else {
            int l = read<int>(), r = read<int>();
            l ^= lastans, r ^= lastans;
            SegmentTree::AnsType answer;
            for (register int i = 0; i < 8; i++) answer = answer + tree[i].getAns(l, r);
            write(answer.sum), putch(' '), write(answer.minVal), putch(' '), write(answer.maxVal), putch('\n');
            lastans = answer.sum & ((1 << 20) - 1);
        }
    }
    return 0;
}

ID

6340

时间

3000~6000ms

内存

64MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

Statement

Solution

Code

[Ynoi2007] rgxsxrs

信息

状态

开发

支持

1 条题解

Statement

Solution

Code

[Ynoi2007] rgxsxrs

信息

状态

开发

支持

还没有账户？

登录