计蒜客【NOIP2017模拟2】银河战舰 <线段树+矩阵>

Posted on Symbols count in article: 1.4k Reading time ≈ 5 mins.

Problem

【NOIP2017模拟2】银河战舰

Time  Limit:  1000  ms\mathrm{Time\;Limit:\;1000\;ms}
Memory  Limit:  262144  K\mathrm{Memory\;Limit:\;262144\;K}

Description

瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，每个战舰都可以看做一个点，在空间站中一共分布着 NN 艘银河战舰。
玛德利德：“你说这些都是你的，那你让他们动一动啊”。
瑞奥：“诶你看,那艘动了！”。
玛德利德：“操作指令由我来发，一共有 55 种动的方法…”。
瑞奥：“我觉得这样有失公正…”。

Input

第一行一个正整数 NN，表示战舰的数量。
接下来 NN 行，每行两个实数，代表第 ii 个战舰的 x,yx,y 坐标。
然后一个正整数 MM，代表调度的次数。
接下来 MM 行操作，每个操作都是如下类型的一种：

  • M,l,r,p,qM,l,r,p,q：把编号在 [l,r][l,r] 区间内的战舰 xx 坐标加上 pp，yy 坐标加上 qq。
  • X,l,rX,l,r：把编号在 [l,r][l,r] 区间内的战舰沿 xx 轴翻转。
  • Y,l,rY,l,r：把编号在 [l,r][l,r] 区间内的战舰沿 yy 轴翻转。
  • O,l,rO,l,r：把编号在 [l,r][l,r] 区间内的战舰沿直线 y=xy=x 翻转。
  • R,l,r,aR,l,r,a：把编号在 [l,r][l,r] 区间内的战舰绕原点逆时针旋转 a∘a^\circ。

Output

输出包括 NN 行，代表着 NN 艘战舰经过 MM 次调度之后的坐标（保留两位小数）。

Sample Input

1
2
3
4
5
6
7
8
3
1 2
-2 2.5
0 -3
3
X 1 3
M 1 3 3 6
R 1 3 90

Sample Output

1
2
3
-4.00 4.00
-3.50 1.00
-9.00 3.00

Constraint

特殊性质 1：对于所有调度，保证 l=1l=1,r=nr=n。
特殊性质 2：不存在形如 O,l,rO,l,r 的操作。
特殊性质 3：不存在形如 R,l,r,aR,l,r,a 的操作。
对于所有测试数据，保证输入的 x,yx,y 坐标以及 p,q,ap,q,a 都最多保留两位小数，0≤a<3600\le a<360，任何时刻任何战舰的横纵坐标绝对值都不会超过 10510^5。

Source

2017 NOIP 提高组模拟赛（二）Day2

标签：线段树 矩阵

Solution

用线段树维护二维平面坐标变换。

对于点(x,y)(x,y)，对其维护一个矩阵：

(xy1)\begin{pmatrix} x\\y\\1 \end{pmatrix}

（下面的11是留给常数的）
那么对于五种变换，都对应着这个矩阵乘一个转移矩阵。
例如对于MM变换，其对应的转移矩阵为

M=(10p01q001)M= \begin{pmatrix} 1&0&p\\ 0&1&q\\ 0&0&1\\ \end{pmatrix}

若有(x,y)→(x′,y′)(x,y)\to (x',y')，则对应

(10p01q001)×(xy1)=(x′y′1)\begin{pmatrix} 1&0&p\\ 0&1&q\\ 0&0&1\\ \end{pmatrix} \times \begin{pmatrix} x\\y\\1\\ \end{pmatrix} = \begin{pmatrix} x'\\y'\\1\\ \end{pmatrix}

类似地，另外四种变换分别对应四个转移矩阵：

X=(1000−10001)Y=(−100010001)O=(010100001)R=(cos⁡a−sin⁡a0sin⁡acos⁡a0001)X= \begin{pmatrix} 1&0&0\\ 0&-1&0\\ 0&0&1\\ \end{pmatrix} \\ Y= \begin{pmatrix} -1&0&0\\ 0&1&0\\ 0&0&1\\ \end{pmatrix} \\ O= \begin{pmatrix} 0&1&0\\ 1&0&0\\ 0&0&1\\ \end{pmatrix} \\ R= \begin{pmatrix} \cos{a}&-\sin{a}&0\\ \sin{a}&\cos{a}&0\\ 0&0&1\\ \end{pmatrix}

显然区间修改相当于区间乘一个矩阵，可以用线段树维护。

时间复杂度O(27⋅nlog⁡n)\mathcal{O}(27\cdot n\log n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define MAX_N 100000
#define PI acos(-1.0)
#define mid ((s+t)>>1)
using namespace std;
typedef double dnt;
int n, m; dnt x[MAX_N+5], y[MAX_N+5];
struct Matrix {
    dnt ele[3][3];
    Matrix () {memset(ele, 0, sizeof ele);}
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++) ret.ele[i][j] += ele[i][k]*x.ele[k][j];
        return ret;
    }
    inline bool operator == (const Matrix &x) const {
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
            if (ele[i][j] != x.ele[i][j]) return false;
        return true;
    }
} e, M, X, Y, O, R, tr[MAX_N<<2];
void build(int v, int s, int t) {
    if (s == t) {
        tr[v].ele[0][0] = x[s];
        tr[v].ele[1][0] = y[s];
        tr[v].ele[2][0] = 1;
        return;
    }
    tr[v] = e;
    build(v<<1, s, mid);
    build(v<<1|1, mid+1, t);
}
void downtag(int v) {
    if (tr[v] == e) return;
    tr[v<<1] = tr[v]*tr[v<<1];
    tr[v<<1|1] = tr[v]*tr[v<<1|1];
    tr[v] = e;
}
void modify(int v, int s, int t, int l, int r, Matrix x) {
    if (s >= l && t <= r)
        {tr[v] = x*tr[v]; return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
}
void print(int v, int s, int t) {
    if (s == t) {
        printf("%.2lf ", tr[v].ele[0][0]);
        printf("%.2lf\n", tr[v].ele[1][0]);
        return;
    }
    downtag(v);
    print(v<<1, s, mid);
    print(v<<1|1, mid+1, t);
}
int main() {
    scanf("%d", &n), R.ele[2][2] = 1;
    e.ele[0][0] = e.ele[1][1] = e.ele[2][2] = 1;
    M.ele[0][0] = M.ele[1][1] = M.ele[2][2] = 1;
    O.ele[0][1] = O.ele[1][0] = O.ele[2][2] = 1;
    X.ele[0][0] = X.ele[2][2] = 1, X.ele[1][1] = -1;
    Y.ele[0][0] = -1, Y.ele[1][1] = Y.ele[2][2] = 1;
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", x+i, y+i);
    build(1, 1, n), scanf("%d", &m);
    while (m--) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'M') {
            int l, r; dnt p, q;
            scanf("%d%d%lf%lf", &l, &r, &p, &q);
            M.ele[0][2] = p, M.ele[1][2] = q;
            modify(1, 1, n, l, r, M);
        }
        if (opt[0] == 'X') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, X);
        }
        if (opt[0] == 'Y') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, Y);
        }
        if (opt[0] == 'O') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, O);
        }
        if (opt[0] == 'R') {
            int l, r; dnt a;
            scanf("%d%d%lf", &l, &r, &a);
            R.ele[0][0] = cos(a*PI/180.0);
            R.ele[0][1] = -sin(a*PI/180.0);
            R.ele[1][0] = sin(a*PI/180.0);
            R.ele[1][1] = cos(a*PI/180.0);
            modify(1, 1, n, l, r, R);
        }
    }
    return print(1, 1, n), 0;
}