社区讨论
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 年前
目前加了快读,展开循环之后还是 了。可能是矩阵运算常熟太大了,有没有路过的老哥帮忙卡一下常?
或者提点优化建议也行/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 条回复,欢迎继续交流。
正在加载回复...