社区讨论

sub2, 4, 6, 8 TLE,求卡常

P8105 「LCOI2022」 Cow Dance参与者 3已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lo3g7lyr
此快照首次捕获于
2023/10/24 06:07
2 年前
此快照最后确认于
2023/10/24 06:07
2 年前
查看原帖
目前加了快读,展开循环之后还是 TT 了。可能是矩阵运算常熟太大了,有没有路过的老哥帮忙卡一下常?
或者提点优化建议也行/kk
CPP
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )
#define x first
#define y second

using namespace std;

namespace FastIO {
	char buf[1 << 20], *_now = buf, *_end = buf;
	#define getchar() (_now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 10, stdin), _now == _end) ? EOF : *_now ++  )
	void read() { return; }
	template <typename T, typename ...T2>
	void read(T &s, T2 &...oth) {
		s = 0; int f = 1; char ch = getchar();
		for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = ~f + 1;
		for (; ch >= '0' && ch <= '9'; ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
		s *= f; read(oth...); return;
	}
	void write() { return; }
	template <typename T, typename ...T2>
	void write(T s, T2 ...oth) {
		int stk[100], top = 0;
		if (s < 0) putchar('-'), s = ~s + 1;
		while (s) stk[ ++ top] = s % 10, s /= 10;
		do putchar(stk[top -- ] + (1 << 4) + (1 << 5)); while (top);
		putchar('\n'); write(oth...); return;
	}
}
#define read FastIO::read
#define write FastIO::write
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

const int N = 300010;
const double pi = acos(-1);
int n, m;
PII p[N];

struct Matrix
{
	double a[2][2];
	void clear(double x) {a[0][0] = a[0][1] = a[1][0] = a[1][1] = x; }
	void makeI() { a[0][0] = 1; a[0][1] = 0; a[1][0] = 0; a[1][1] = 1; }
	bool notI() { return ((a[0][0] != 1) or (a[0][1] != 0) or (a[1][0] != 0) or (a[1][1] != 1)); }
	bool empty() { return ((a[0][0] == 0) and (a[0][1] == 0) and (a[1][0] == 0) and (a[1][1] == 0)); }
	void init(double _00, double _01, double _10, double _11) {
		a[0][0] = _00, a[0][1] = _01;
		a[1][0] = _10, a[1][1] = _11;
	}
}Turn, st;

Matrix operator + (const Matrix& A, const Matrix& B) {
	Matrix res; res.clear(0);
//	res.a[0][0] = A.a[0][0] + B.a[0][0];
//	res.a[0][1] = A.a[0][1] + B.a[0][1];
	res.a[1][0] = A.a[1][0] + B.a[1][0];
	res.a[1][1] = A.a[1][1] + B.a[1][1];
	return res;
}
Matrix operator * (const Matrix& A, const Matrix& B) {
	Matrix res; res.clear(0);
	res.a[0][0] += A.a[0][0] * B.a[0][0];
	res.a[0][0] += A.a[0][1] * B.a[1][0];
	res.a[0][1] += A.a[0][0] * B.a[0][1];
	res.a[0][1] += A.a[0][1] * B.a[1][1];
	res.a[1][0] += A.a[1][0] * B.a[0][0];
	res.a[1][0] += A.a[1][1] * B.a[1][0];
	res.a[1][1] += A.a[1][0] * B.a[0][1];
	res.a[1][1] += A.a[1][1] * B.a[1][1];
	return res;
}
Matrix operator * (const Matrix& A, const double& B) {
	Matrix res; res.clear(0);
//	res.a[0][0] = A.a[0][0] * B;
//	res.a[0][1] = A.a[0][1] * B;
	res.a[1][0] = A.a[1][0] * B;
	res.a[1][1] = A.a[1][1] * B;
	return res;
}

namespace Segment_Tree {
	struct Tree {
		int l, r;
		Matrix sum;
		Matrix add, mul;
		int len() { return r - l + 1; }
	}tr[N << 2];
	#define ls u << 1
	#define rs u << 1 | 1
	
	void pushup(int u) {
		tr[u].sum = tr[ls].sum + tr[rs].sum;
	}
	void push_add(int u, Matrix add) {
		tr[u].add = tr[u].add + add;
		tr[u].sum = tr[u].sum + (add * tr[u].len());
	}
	void push_mul(int u, Matrix mul) {
		tr[u].mul = tr[u].mul * mul;
		tr[u].sum = tr[u].sum * mul;
		tr[u].add = tr[u].add * mul;
	}
	void pushdown(int u) {
		if (tr[u].mul.notI()) {
			push_mul(ls, tr[u].mul);
			push_mul(rs, tr[u].mul);
			tr[u].mul.makeI();
		}
		if (!tr[u].add.empty()) {
			push_add(ls, tr[u].add);
			push_add(rs, tr[u].add);
			tr[u].add.clear(0);
		}
	}
	void build(int u, int l, int r) {
		tr[u] = {l, r}, tr[u].mul.makeI();
		if (l == r) {
			tr[u].sum.a[1][0] = p[r].x;
			tr[u].sum.a[1][1] = p[r].y;
			tr[u].mul.makeI(); tr[u].add.clear(0);
			return;
		}
		int mid = l + r >> 1;
		build(ls, l, mid), build(rs, mid + 1, r);
		pushup(u);
	}
	void Multiply(int u, int l, int r, Matrix k) {
		if (tr[u].l >= l && tr[u].r <= r) {
			push_mul(u, k); return;
		}
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid) Multiply(ls, l, r, k);
		if (r > mid) Multiply(rs, l, r, k);
		pushup(u);
	}
	void Add(int u, int l, int r, Matrix k) {
		if (tr[u].l >= l && tr[u].r <= r) {
			push_add(u, k); return;
		}
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid) Add(ls, l, r, k);
		if (r > mid) Add(rs, l, r, k);
		pushup(u);
	}
	Matrix query(int u, int l, int r) {
		if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
		pushdown(u); Matrix sum; sum.clear(0);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid) sum = sum + query(ls, l, r);
		if (r > mid) sum = sum + query(rs, l, r);
		return sum;
	}
} using namespace Segment_Tree;

void modify1(int l, int r, int a, int b) {
	Matrix Addition; Addition.init(0, 0, a, b);
	Add(1, l, r, Addition);
}
void modify2(int l, int r, int a, int b, double alpha) {
	Matrix turn; turn.init(cos(alpha), -sin(alpha), sin(alpha), cos(alpha));
	Matrix Minus; Minus.init(0, 0, -a, -b);
	Matrix Addition; Addition.init(0, 0, a, b);
	Add(1, l, r, Minus), Multiply(1, l, r, turn), Add(1, l, r, Addition);
}
void modify3(int l, int r, int a, int b, double k) {
	Matrix turn; turn.init(k, 0, 0, k);
	Matrix Minus; Minus.init(0, 0, -a, -b);
	Matrix Addition; Addition.init(0, 0, a, b);
	Add(1, l, r, Minus), Multiply(1, l, r, turn), Add(1, l, r, Addition);
}

int main() {
	read(n, m);
	for (int i = 1; i <= n; i ++ )
		read(p[i].x, p[i].y);
	build(1, 1, n);
	
	while (m -- ) {
		int op, l, r, a, b;
		int g, p, q;
		read(op, l, r);
		if (op == 1) read(a, b), modify1(l, r, a, b);
		if (op == 2) read(a, b, g), modify2(l, r, a, b, (double)g * pi / 180.0);
		if (op == 3) read(a, b, p, q), modify3(l, r, a, b, (double)p / q);
		if (op == 4) { Matrix ans = query(1, l, r); printf("%.10lf %.10lf\n", (double)ans.a[1][0] / (r - l + 1), (double)ans.a[1][1] / (r - l + 1)); }
	}
	return 0;
}

回复

11 条回复,欢迎继续交流。

正在加载回复...