2022 CCPC 广州站 个人题解 B. Ayano and sequences

Analysis

传送门：https://codeforces.com/gym/104053/problem/B

首先考虑区间赋值的影响：

• 如果是离散区间合并为一个区间，那么区间总数减少；
• 如果是大区间包含分割区间，那么每次操作至多产生$2$个新区间。

由于是区间赋值，因此我们考虑用一个类似珂朵莉树的思想来维护每条连续线段，然后发现如果某条线段在一段连续的时间内没有被改变，那么它会在时间-坐标平面上扫出一个矩形，那么考虑用线段树扫描线解决。

首先考虑扫描线框架：

初始时，我们向set中插入$n$个单点区间$a[i]$，然后对于操作$1$，从set中逐个取出区间然后删除，然后插入新区间，需要讨论端点位于区间内的情况(需要把误删的部分插入回去)；对于操作$2$，直接在扫描线上更新即可。

接下来考虑扫描线：

我们发现结合区间加的操作后，这个问题变成了二维扫描线求三维体积问题，因此我们不能单纯的维护区间和来解决，还要按时间戳维护一个负贡献，如图：

我们如果直接把区间和乘时间跨度，那么上图的红色部分就无法计数，因此单独维护一个负贡献，在统计答案时把负贡献累加进来就好了。

Code

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define endl '\n'
using namespace std;const int N = 5e5 + 10;
ull a[N], ans[N], pre[N], timer = 0;
int n = 0, q = 0;namespace SegTree{#define ls rt << 1#define rs rt << 1 | 1#define lson ls, l, mid#define rson rs, mid + 1, rull sumw[N << 2], sumdt[N << 2], ww[N << 2], dt[N << 2];inline void push_up(int rt, ull len) { sumw[rt] = sumw[ls] + sumw[rs] + len * ww[rt];sumdt[rt] = sumdt[ls] + sumdt[rs] + len * dt[rt];}void update(int rt, int l, int r, int L, int R, ull k, ull b) {if (R < l || r < L || L > R)  return;if (L <= l && r <= R) {sumw[rt] += k * (r - l + 1);sumdt[rt] += b * (r - l + 1);ww[rt] += k, dt[rt] += b;return;}int mid = (l + r) >> 1;update(lson, L, R, k, b), update(rson, L, R, k, b);push_up(rt, r - l + 1);}ull query(int rt, int l, int r, int L, int R, ull h) {if (R < l || r < L || L > R) return 0;if (L <= l && r <= R) return sumw[rt] * h + sumdt[rt];int mid = (l + r) >> 1;ull len = min(r, R) - max(l, L) + 1, res = (ww[rt] * h + dt[rt]) * len;return query(lson, L, R, h) + query(rson, L, R, h) + res;}}#define pii pair<int, int>
set<pii> st;void del(int l, int r) {st.erase({r, l});ans[a[l]] += SegTree::query(1, 1, n, l, r, timer - 1) - pre[l];
}void add(int l, int r, int x) {st.insert({r, l});a[l] = x;pre[l] = SegTree::query(1, 1, n, l, r, timer - 1);
}inline void solve() {cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) add(i, i, a[i]);while(q--) {timer++;int op, l, r; ull w; cin >> op >> l >> r >> w;if(op == 1) {while(1) {auto now = st.lower_bound({l, -1});if(now == st.end() || now -> second > r) break;int oldl = now -> second, oldr = now -> first;int oldv = a[oldl];del(oldl, oldr);if(l > oldl) add(oldl, l - 1, oldv);if(r < oldr) add(r + 1, oldr, oldv);}add(l, r, w);} else {SegTree::update(1, 1, n, l, r, w, (1 - timer) * w);}}timer += 1;while(st.size()) {auto it = st.begin();del(it -> second, it -> first);}for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}signed main() {ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; // cin >> t;while(t--) solve();return 0;
}