General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
233908238 Practice:
jeefy
444C - 26 C++14 (GCC 6-32) Accepted 296 ms 13484 KB 2023-11-23 14:46:50 2023-11-23 14:46:50
→ Source
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define all(x) begin(x), end(x)

using namespace std;
using lint = long long;
const int N = 1e5 + 7;

int n;
lint siz[N << 2], sum[N << 2], laz[N << 2];

#define lc(p) ((p) << 1)
#define rc(p) (lc(p) | 1)

void update(int p) {
	sum[p] = sum[lc(p)] + sum[rc(p)];
}

void make(int p, lint v) {
	sum[p] += siz[p] * v;
	laz[p] += v;
}

void sync(int p) {
	if (laz[p]) {
		make(lc(p), laz[p]), make(rc(p), laz[p]);
	} laz[p] = 0;
}

void build(int p = 1, int l = 1, int r = n) {
	if (l == r) return (void)(siz[p] = 1);
	int mid = (l + r) >> 1;
	build(lc(p), l, mid), build(rc(p), mid + 1, r);
	siz[p] = siz[lc(p)] + siz[rc(p)];
}

void add(int L, int R, lint v, int p = 1, int l = 1, int r = n) {
	if (L <= l && r <= R) {
		return make(p, v);
	} int mid = (l + r) >> 1; sync(p);
	if (L <= mid) add(L, R, v, lc(p), l, mid);
	if (R > mid) add(L, R, v, rc(p), mid + 1, r);
	update(p);
}

lint query(int L, int R, int p = 1, int l = 1, int r = n) {
	if (L <= l && r <= R) {
		return sum[p];
	} lint mid = (l + r) >> 1, res = 0; sync(p);
	if (L <= mid) res += query(L, R, lc(p), l, mid);
	if (R > mid) res += query(L, R, rc(p), mid + 1, r);
	return update(p), res;
}

struct Interval {
	int l, r; lint v;
	bool operator < (const Interval &it) const {
		return r < it.r;
	}
}; set<Interval> odt;

auto split(int z) {
	auto it = odt.lower_bound({0, z, 0});
	if (it->l == z) return it;
	Interval tmp = *it;
	odt.erase(it), odt.insert({tmp.l, z - 1, tmp.v});
	return odt.insert({z, tmp.r, tmp.v}).first;
}

void assign(int l, int r, lint x) {
	auto itr = split(r + 1), it = split(l);
	for (; it != itr; it = odt.erase(it)) {
		lint v = it->v - x;
		if (v < 0) v = -v;
		// cerr << "Add " << it->l << ' ' << it->r << ' ' << v << '\n';
		add(it->l, it->r, v);
	} odt.insert({l, r, x});
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int q; cin >> n >> q;

	for (int i = 0; i <= n + 1; ++i)
		odt.insert({i, i, i});
	build();

	lint x;
	for (int op, l, r, i = 1; i <= q; ++i) {
		cin >> op >> l >> r;
		if (op == 1) {
			cin >> x; assign(l, r, x);
		} else {
			cout << query(l, r, 1, 1, n) << '\n';
		}
	}
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details