CF618E 题解

ShuYuMo

2021-03-24 18:15:09

Solution

~~这个题是线段树模板题吧~~ 可以考虑把问题形式化一下: - 求从原点出发,沿着每一条手臂移动,移动到最后一个点的坐标。 - 支持修改 向量是可以用来描述一种移动的,这就和题目中要求做的对应起来了。 把每一条手臂看成一个向量,那么最后要求的就是这些向量的和。 那么对手臂的修改就可以转化为对手臂对应向量做修改。 考虑两种修改: - 对于伸长操作,显然就是把对应向量伸长,这个很简单 - 对于旋转操作,不难发现其实是把这个向量及其后面的所有向量都旋转相同的一个角度。 众所周知,可以用矩阵来描述对向量的旋转操作,而且矩阵满足结合律和分配律,这样就可以线段树维护了。 所以可以考虑线段树每个结点维护向量和,lazy 标记(对向量的修改)就可以使用矩阵表示。 考虑旋转一个向量的矩阵,若旋转 $\alpha$ 度,可以构造为: $$ \begin{bmatrix} \cos\alpha &-\sin\alpha\\ \sin\alpha &\cos\alpha \end{bmatrix} $$ 推法可以参考[这里](https://oi-wiki.org/math/vector/#_24) 其实可以考虑把向量放到复平面里面,然后这个式子就很显然了,个人感觉比三角恒等变换的推法要优美。 线段树维护向量和即可。 好像有很多人懒标记是旋转角度,其实如果操作只有旋转的话,都是可以的,我只是觉得这样想起来更自然。如果维护旋转角度,每次下放标记都要三角函数算一算,会比维护矩阵慢很多,写出来也没有卡常数…~~然后就最优解了~~。 /CY ```cpp #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; #define db double const db PI = acos(-1.); namespace SegmentTree{ int n; const int _ = 2e6 + 100; db squ(db x) { return x * x; } struct Vector{ db x, y; Vector(){} Vector(db a, db b) { x = a; y = b; } db Length() { return sqrt(squ(x) + squ(y)); } void pull(db len) { db tmp = this->Length(); x *= (len + tmp) / tmp; y *= (len + tmp) / tmp; } }; Vector operator + (const Vector & A, const Vector & B) { return Vector(A.x + B.x, A.y + B.y); } /** | a b | | c d | */ struct Matrix{ db a, b, c, d; Matrix() { a = d = 1; c = b = 0; } Matrix(db $1, db $2, db $3, db $4) { a = $1; b = $2; c = $3; d = $4; } Matrix(db alpha){ // 逆时针 alpha 度。 db $1 = cos(alpha), $2 = sin(alpha); a = $1; b = -$2; c = $2; d = $1; } }; #define EPS (1e-9) inline int sign(db x) { return x < -EPS ? -1 : (x > EPS); } inline int cmp(db x, db y) { return sign(x - y); } inline bool operator == (const Matrix & A, const Matrix & B) { return cmp(A.a, B.a) == 0 && cmp(A.b, B.b) == 0 && cmp(A.c, B.c) == 0 && cmp(A.d, B.d) == 0; } Matrix operator * (const Matrix & A, const Matrix & B) { Matrix ret; ret.a = A.a * B.a + A.b * B.c; ret.b = A.a * B.b + A.b * B.d; ret.c = A.c * B.a + A.d * B.c; ret.d = A.c * B.b + A.d * B.d; return ret; } Vector operator * (const Matrix & A, const Vector & B) { return Vector(A.a * B.x + A.b * B.y, A.c * B.x + A.d * B.y); } Vector v[_]; Matrix tag[_]; #define ls(o) (o << 1) #define rs(o) ((o << 1) | 1) #define maintain(o) (v[o] = v[ls(o)] + v[rs(o)]) void tar(int o, Matrix V){ tag[o] = V * tag[o]; v[o] = V * v[o]; } void push(int o) { if(tag[o] == tag[0]) return ; tar(ls(o), tag[o]); tar(rs(o), tag[o]); tag[o] = tag[0]; } void build(int o, int L, int R) { if(L == R) return v[o] = Vector(1, 0), void(); int mid = (L + R) >> 1; build(ls(o), L, mid); build(rs(o), mid + 1, R); maintain(o); } void build(int __) { n = __; return build(1, 1, n); } void update_pull(int o, int nowl, int nowr, int p, db L){ if(nowl == nowr) return v[o].pull(L), void(); int mid = (nowl + nowr) >> 1; push(o); if(p <= mid) update_pull(ls(o), nowl, mid, p, L); if(p > mid) update_pull(rs(o), mid + 1, nowr, p, L); maintain(o); } void update_pull(int p, db L) { return update_pull(1, 1, n, p, L); } void update_rotate(int o, int nowl, int nowr, int L, int R, Matrix x) { if(L <= nowl && nowr <= R) return tar(o, x); int mid = (nowl + nowr) >> 1; push(o); if(L <= mid) update_rotate(ls(o), nowl, mid, L, R, x); if(R > mid) update_rotate(rs(o), mid + 1, nowr, L, R, x); maintain(o); } void update_rotate(int p, db alpha){ alpha = 360 - alpha; alpha = (alpha / 180.) * PI; update_rotate(1, 1, n, p, n, Matrix(alpha)); } Vector query() { push(1); return v[1]; } } using SegmentTree::update_pull; using SegmentTree::update_rotate; using SegmentTree::query; using SegmentTree::build; using SegmentTree::Vector; int n, m; int main(){ scanf("%d%d", &n, &m); build(n); while(m--){ int opt, x; scanf("%d%d", &opt, &x); if(opt == 1){ db L; scanf("%lf", &L); update_pull(x, L); } else { db alpha; scanf("%lf", &alpha); update_rotate(x, alpha); } Vector ret = query(); printf("%.5lf %.5lf\n", ret.x, ret.y); } return 0; } ```