P7497 四方喝彩 Solution

Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ ，有 $m$ 个操作，分四种：

$\operatorname{add}(l,r,v)$ ：对于所有 $\in [l,r]$ 执行 $a_i \gets a_i+v$ .
$\operatorname{mul}(l,r,v)$ ：对于所有 $\in [l,r]$ 执行 $a_i \gets a_i\times v$ .
$\operatorname{freeze}(l,r,x)$ ：区间 $[l, r]$ 在接下来的 $x$ 次操作中被冻结，不会受修改操作影响，已有的冻结效果不会被替换.
$\operatorname{query}(l,r)$ ：求 $(\sum\limits_{i=l}^r a_i) \bmod (10^9+7)$ .

Limitations

$\le n,m \le 2\times 10^5$
$\le a_i,v \le 10^9+7$
设当前为第 $t$ 次操作，则 $\le x \le m-k$
$1\text{s},512\text{MB}$

Solution

将 $\operatorname{freeze}$ 操作拆成冻结和解冻两个操作，将解冻操作按解冻时间记在邻接表上.
考虑 $\operatorname{add}$ ，由于区间可能部分冻结，故乘的长度不是 $(r - l + 1)$ 而是未封锁元素个数，需要维护.
考虑 $\operatorname{mul}$ ，同样由于区间可能部分冻结，不能直接 $\times v$ ，而是将未冻结部分 $\times v$ ，所以需要分开维护未冻结部分和冻结部分的和.
考虑多个冻结操作重叠，由于合并它们很麻烦，所以直接叠加，等到完全解冻才继续 pushdown，所以维护的是冻结次数而不是是否冻结。
写的时候注意细节，具体可以看代码。

Code

$8.06\text{KB},1.12\text{s},31.29\text{MB}\;\texttt{(in total, C++20 with O2)}$

// Problem: P7497 四方喝彩
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7497
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

template <int MOD>
struct modint {
    int val;
    static int norm(const int& x) { return x < 0 ? x + MOD : x; }
    modint inv() const {
        int a = val, b = MOD, u = 1, v = 0, t;
        while (b > 0) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int& m) : val(norm(m % MOD)) {}
    modint(const long long& m) : val(norm(m % MOD)) {}
    modint operator-() const { return modint(norm(-val)); }
    bool operator==(const modint& o) { return val == o.val; }
    bool operator!=(const modint &o) { return val != o.val; }
    bool operator<(const modint& o) { return val < o.val; }
    bool operator>(const modint& o) { return val > o.val; }
    bool operator<=(const modint& o) { return val <= o.val; }
    bool operator>=(const modint& o) { return val >= o.val; }
    modint& operator++() { return *this += 1; }
    modint operator++(int) { modint temp = *this; ++(*this); return temp; }
    modint& operator--() { return *this -= 1; }
    modint operator--(int) { modint temp = *this; --(*this); return temp; }
    modint& operator+=(const modint& o) { return val = (1ll * val + o.val) % MOD, *this; }
    modint& operator-=(const modint& o) { return val = norm(1ll * val - o.val), *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % MOD), *this; }
    modint& operator/=(const modint& o) { return *this *= o.inv(); }
    modint& operator^=(const modint& o) { return val ^= o.val, *this; }
    modint& operator>>=(const modint& o) { return val >>= o.val, *this; }
    modint& operator<<=(const modint& o) { return val <<= o.val, *this; }
    modint operator-(const modint& o) const { return modint(*this) -= o; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
    modint operator/(const modint& o) const { return modint(*this) /= o; }
    modint operator^(const modint& o) const { return modint(*this) ^= o; }
    modint operator>>(const modint& o) const { return modint(*this) >>= o; }
    modint operator<<(const modint& o) const { return modint(*this) <<= o; }
    friend std::istream& operator>>(std::istream& is, modint& a) {
        long long v;
        return is >> v, a.val = norm(v % MOD), is;
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }
    friend std::string tostring(const modint& a) { return std::to_string(a.val); }
    template <class T>
    friend modint qpow(const modint& a, const T& b) {
        modint x = a, res = 1;
        for (T p = b; p; x *= x, p >>= 1)
            if (p & 1) res *= x;
        return res;
    }
};

using Z = modint<1000000007>;

struct Node {
    int l, r, size, blocks;
    Z suma, sumb, add, mul;
};

using Tree = vector<Node>;

int ls(int u) { return u * 2 + 1; }
int rs(int u) { return u * 2 + 2; }

void pushup(Tree& tr, int u) {
    if (tr[u].blocks == 0) {
        tr[u].suma = tr[ls(u)].suma + tr[rs(u)].suma;
        tr[u].sumb = tr[ls(u)].sumb + tr[rs(u)].sumb;
        tr[u].size = tr[ls(u)].size + tr[rs(u)].size;
    }
}

void apply(Node& rt, Node& son) {
    if (son.blocks == 0) {
        son.suma = son.suma * rt.mul + rt.add * son.size;
        son.add = son.add * rt.mul + rt.add;
        son.mul *= rt.mul;
    }
}

void pushdown(Tree& tr, int u) {
    apply(tr[u], tr[ls(u)]);
    apply(tr[u], tr[rs(u)]);
    tr[u].add = 0;
    tr[u].mul = 1;
}

void build(Tree& tr, int u, int l, int r, vector<int>& a) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].mul = 1;
    tr[u].add = 0;
    
    if (l == r) {
        tr[u].suma = a[l];
        tr[u].size = 1;
        return;
    }
    
    int mid = (l + r) >> 1;
    build(tr, ls(u), l, mid, a);
    build(tr, rs(u), mid + 1, r, a);
    pushup(tr, u);
}

void add(Tree& tr, int u, int l, int r, Z val) {
    if (tr[u].l > r || tr[u].r < l || tr[u].blocks > 0) {
        return;
    }
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].suma += val * tr[u].size;
        tr[u].add += val;
        return;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) {
        add(tr, ls(u), l, r, val);
    }
    if (r > mid) {
        add(tr, rs(u), l, r, val);
    }
    pushup(tr, u);
}

void mul(Tree& tr, int u, int l, int r, Z val) {
    if (tr[u].l > r || tr[u].r < l || tr[u].blocks > 0) {
        return;
    }
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].suma *= val;
        tr[u].add *= val;
        tr[u].mul *= val;
        return;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) {
        mul(tr, ls(u), l, r, val);
    }
    if (r > mid) {
        mul(tr, rs(u), l, r, val);
    }
    pushup(tr, u);
}

void block(Tree& tr, int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) {
        return;
    }
    if (l <= tr[u].l && tr[u].r <= r) {
        if (tr[u].l < tr[u].r) {
            pushdown(tr, u);
        }
        if (tr[u].blocks == 0) {
            tr[u].sumb += tr[u].suma;
            tr[u].suma = 0;
            tr[u].size = 0;
        }
        tr[u].blocks++;
        return;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) {
        block(tr, ls(u), l, r);
    }
    if (r > mid) {
        block(tr, rs(u), l, r);
    }
    pushup(tr, u);
}

void unblock(Tree& tr, int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) {
        return;
    }
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].blocks--;
        if (tr[u].blocks == 0) {
            if (tr[u].l == tr[u].r) {
                tr[u].suma += tr[u].sumb;
                tr[u].sumb = 0;
                tr[u].size = 1;
            }
            else {
                pushup(tr, u);
            }
        }
        return;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) {
        unblock(tr, ls(u), l, r);
    }
    if (r > mid) {
        unblock(tr, rs(u), l, r);
    }
    pushup(tr, u);
}

Z query(Tree& tr, int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) {
        return 0;
    }
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].suma + tr[u].sumb;
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    Z ans = 0;
    pushdown(tr, u);
    if (l <= mid) {
        ans += query(tr, ls(u), l, r);
    }
    if (r > mid) {
        ans += query(tr, rs(u), l, r);
    }
    return ans;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	scanf("%d%d", &n, &m);
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
	    scanf("%d", &a[i]);
	}
	
	Tree seg(n << 2);
	vector<vector<pair<int, int>>> blocks(m);
	build(seg, 0, 0, n - 1, a);
	
	for (int i = 0, op, l, r, v; i < m; i++) {
	    scanf("%d%d%d", &op, &l, &r);
	    l--, r--;
	    if (op == 1) {
	        scanf("%d", &v);
	        add(seg, 0, l, r, Z(v));
	    }
	    if (op == 2) {
	        scanf("%d", &v);
	        mul(seg, 0, l, r, Z(v));
	    }
	    if (op == 3) {
	        scanf("%d", &v);
	        block(seg, 0, l, r);
	        blocks[i + v].emplace_back(l, r);
	    }
	    if (op == 4) {
	        printf("%d\n", query(seg, 0, l, r).val);
	    }
	    
	    for (auto [le, ri] : blocks[i]) {
	        unblock(seg, 0, le, ri);
	    }
	}
	
	return 0;
}