30pts线段树+离散化WA on3~9 玄关求调

#include <bits/stdc++.h>
typedef unsigned long long ll;

using namespace std;

const int N = 110000;
int n, test, to[N * 2];
vector<int> v;
map<int, int> mp;

struct Query {
	int op, l, r, k;
} q[N];
struct SegmentTree {
	int sz;
	ll sum;
	ll tag;
};
struct Work {
	SegmentTree seg[N * 8];
	
	inline void settag(int id, int val) {
		seg[id].sum += 1LL * seg[id].sz * val;
		seg[id].tag += 0LL + val;
	}
	
	inline void update(int id) {
		seg[id].sum = seg[id * 2].sum + seg[id * 2 + 1].sum;
	}
	
	inline void pushdown(int id) {
		ll tag = seg[id].tag;
		if (tag) {
			settag(id * 2, tag);
			settag(id * 2 + 1, tag);
			seg[id].tag = 0;
		}
	}
	
	inline void build(int id, int l, int r) {
		seg[id].sz = to[r] - to[l] + 1;
		if (l == r)
			return;
		int m = (l + r) / 2;
		build(id * 2, l, m);
		build(id * 2 + 1, m + 1, r);
	}
	
	inline void modify(int id, int l, int r, int ql, int qr, int val) {
		if (l >= ql && r <= qr) 
			return settag(id, val), void();
		pushdown(id);
		int m = (l + r) / 2;
		if (ql <= m)
			modify(id * 2, l, m, ql, qr, val);
		if (qr > m)
			modify(id * 2 + 1, m + 1, r, ql, qr, val);
		update(id);
	}
	
	inline void modify(int l, int r, int k) {
		modify(1, 1, n, mp[l], mp[r], k);
	}
	
	inline ll query(int id, int l, int r, int ql, int qr) {
		if (l >= ql && r <= qr)
			return seg[id].sum;
		pushdown(id);
		int m = (l + r) / 2;
		ll tot = 0;
		if (ql <= m)
			tot += query(id * 2, l, m, ql, qr);
		if (qr > m)
			tot += query(id * 2 + 1, m + 1, r, ql, qr);
		return tot;
	}
	
	inline ll query(int l, int r) {
		return query(1, 1, n, mp[l], mp[r]);
	}
} sg;

int main() {
	scanf("%d%d", &test, &test);
	for (int i = 1; i <= test; i++) {
		scanf("%d%d%d", &q[i].op, &q[i].l, &q[i].r);
		if (q[i].op == 1)
			scanf("%d", &q[i].k);
		v.push_back(q[i].l), v.push_back(q[i].r);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	n = v.size();
	for (int i = 0; i < n; i++)
		to[i + 1] = v[i], mp[v[i]] = i + 1;
		
	sg.build(1, 1, n);
	for (int i = 1; i <= test; i++) {
		int op = q[i].op, l = q[i].l, r = q[i].r, k = q[i].k;
		if (op == 1) 
			sg.modify(l, r, k);
		else
			printf("%llu\n", 1ull * (l + r) * (r - l + 1) / 2 + sg.query(l, r));
	}
	return 0;
}