Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <array>
- #include <iostream>
- using namespace std;
- #define int long long
- const int INF = 1e18 + 7;
- const int MAXN = 1e5;
- array<int, 4 * MAXN> tree;
- array<int, 4 * MAXN> upd;
- void push(int x, int lx, int rx) {
- if (upd[x] == INF) {
- return;
- }
- if (lx + 1 != rx) {
- upd[2 * x + 1] = upd[x];
- upd[2 * x + 2] = upd[x];
- }
- tree[x] = upd[x] * (rx - lx);
- upd[x] = INF;
- }
- void update(int x, int lx, int rx, int l, int r, int v) {
- push(x, lx, rx);
- if (rx <= l || lx >= r) {
- return;
- }
- if (lx >= l && rx <= r) {
- upd[x] = v;
- push(x, lx, rx);
- return;
- }
- int mid = (lx + rx) / 2;
- update(x * 2 + 1, lx, mid, l, r, v);
- update(x * 2 + 2, mid, rx, l, r, v);
- tree[x] = tree[x * 2 + 1] + tree[x * 2 + 2];
- }
- int sum(int x, int lx, int rx, int l, int r) {
- push(x, lx, rx);
- if (rx <= l || lx >= r) {
- return 0;
- }
- if (lx >= l && rx <= r) {
- return tree[x];
- }
- int mid = (lx + rx) / 2;
- return sum(x * 2 + 1, lx, mid, l, r) + sum(x * 2 + 2, mid, rx, l, r);
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m;
- cin >> n >> m;
- fill(upd.begin(), upd.end(), INF);
- for (int i = 0; i < m; ++i) {
- int t, l, r;
- cin >> t >> l >> r;
- if (t == 1) {
- int v;
- cin >> v;
- update(0, 0, n, l, r, v);
- } else {
- cout << sum(0, 0, n, l, r) << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment