P7497 四方喝彩 Solution

Description

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

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

Limitations

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

Solution

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

Code

$8.06\text{KB},1.12\text{s},31.29\text{MB}\text{(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;
}