可爱萌新刚学OI,求助简单分块 TLEon#29
查看原帖
可爱萌新刚学OI,求助简单分块 TLEon#29
852144
Loser_Syx楼主2024/7/12 11:28
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = long long>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 1e5 + 19, sq = 350, M = sq + 10;
int q[N], id[N], sum[N], tag[N], col[N], more[N], w[N];
void rebuild(int l, int r, int c) {
	int L = id[l];
	if (tag[L]) {
		for (int i = q[L]; i < q[L + 1]; ++i) {
			if (i < l || i > r) col[i] = tag[L];
			else {
				sum[L] += abs(tag[L] - c);
				w[i] += abs(tag[L] - c);
				col[i] = c;
			}
		}
	} else {
		for (int i = l; i <= r; ++i) {
			sum[L] += abs(col[i] - c);
			w[i] += abs(col[i] - c);
			col[i] = c;
		}
	} tag[L] = 0;
}
int query(int l, int r) {
	int ans = 0, L = id[l - 1] + 1, R = id[r + 1] - 1;
	if (id[l] == id[r]) {
		for (int i = l; i <= r; ++i) ans += more[id[l]] + w[i];
		return ans;
	}
	for (int i = l; i < q[L]; ++i) ans += more[L - 1] + w[i];
	for (int i = q[R + 1]; i <= r; ++i) ans += more[R + 1] + w[i];
	for (int i = L; i <= R; ++i) ans += sum[i];
	return ans;
}
void modify(int l, int r, int c) {
	int L = id[l - 1] + 1, R = id[r + 1] - 1;
	if (id[l] == id[r]) return rebuild(l, r, c), void();
	if (id[l] != L) rebuild(l, q[L] - 1, c);
	if (id[r] != R) rebuild(q[R + 1], r, c);
	for (int i = L; i <= R; ++i) {
		if (tag[i]) {
			more[i] += abs(c - tag[i]);
			sum[i] += abs(c - tag[i]) * (q[i + 1] - q[i]);
			tag[i] = c;
		} else {
			rebuild(q[i], q[i + 1] - 1, c);
			tag[i] = c;
		}
	}
}
signed main() {
	int n, m; read(n, m);
	int len = 0;
	for (int i = 1; i <= n; ++i) {
		col[i] = i;
		if ((i - 1) % sq == 0) {
			q[len] = sq;
			++len;
		}
	}
	q[0] = 0; id[n + 1] = len + 1;
	q[len] = n % sq ? n % sq : sq;
	q[len + 1] = n + 1;
	for (int i = 1; i <= len; ++i) q[i] += q[i-1];
	while (m--) {
		int op, l, r;
		read(op, l, r);
		if (op == 1) modify(l, r, read());
		else write(query(l, r), '\n');
	}
	return 0;
} 
2024/7/12 11:28
加载中...