题目描述

对于平面直角坐标系上的坐标$(x , y)$，小 P 定义了如下两种操作：

• 拉伸 $k$ 倍：横坐标$x$ 变为$kx$，纵坐标$y$ 变为$ky$；

• 旋转 $θ$：将坐标 $(x , y)$绕坐标原点$(0 , 0)$ 逆时针旋转$θ$ 弧度 $(0 \le θ \lt 2\pi)$。易知旋转后的横坐标为$xcosθ - ysinθ $，纵坐标为$xsinθ + ycosθ $。

设定好了包含 $n$个操作的序列$(t_1,t_2,t_3,…,t_n)$ 后，小 P 又定义了如下查询：
$i j x y$：坐标$(x , y)$ 经过操作$t_i , … , t_j $后的新坐标。
对于给定的操作序列，试计算$m$ 个查询的结果。

输入格式

从标准输入读入数据。

输入共$n + m + 1$ 行。

输入的第一行包含空格分隔的两个正整数 $n$ 和 $m$，分别表示操作和查询个数。

接下来 $n$ 行依次输入$n$ 个操作，每行包含空格分隔的一个整数（操作类型）和一个实数（$k$ 或$θ$），形如$1 k$（表示拉伸$k$ 倍）或$2 θ$（表示旋转$θ$）。

接下来$m$ 行依次输入$m$ 个查询，每行包含空格分隔的四个整数$i、j、x$ 和$y$ ，含义如前文所述。

输出格式

输出到标准输出中。

输出共 $m$ 行，每行包含空格分隔的两个实数，表示对应查询的结果。

样例输入

10 5
2 0.59
2 4.956
1 0.997
1 1.364
1 1.242
1 0.82
2 2.824
1 0.716
2 0.178
2 4.094
1 6 -953188 -946637
1 9 969538 848081
4 7 -114758 522223
1 9 -535079 601597
8 8 159430 -511187

样例输出

-1858706.758 -83259.993
-1261428.46 201113.678
-75099.123 -738950.159
-119179.897 -789457.532
114151.88 -366009.892

题目分析

一眼感觉就是对操作进行并行处理，初始想法很简单，暴力 $O(n*m)$ ， 80%能过
于是就得合并操作呗
看到这种区间询问就想到了线段树(好像前缀和就能写，还更简单)
然后就写了个板子，想看板子可以借鉴 AcWing 245. 你能回答这些问题吗
总的来说 ， 前缀和、树状数组、线段树应该都能过，还是简单的，就算暴力也能过80%，还是简单的

C++代码 线段树 $O(mlogn)$

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

const int N = 100010;
typedef pair<int, double> PII;

PII w[N];
int n, m;
struct Node
{
    int l, r;
    double k, angle;
} tr[N * 4];

void pushup(int u)
{
    tr[u].k = tr[u << 1].k * tr[u << 1 | 1].k;
    tr[u].angle = tr[u << 1].angle + tr[u << 1 | 1].angle;
}

void pushup(Node &u, Node &l, Node &r)
{
    u.k = l.k * r.k;
    u.angle = l.angle + r.angle;
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        if (w[l].first == 1)
            tr[u] = {l, r, w[l].second, 0};
        else
            tr[u] = {l, r, 1, w[l].second};
    }
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid)
            return query(u << 1, l, r);
        else if (l > mid)
            return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i].first >> w[i].second;
    }

    build(1, 1, n);

    while (m--)
    {
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        auto t = query(1, l, r);
        double k = t.k, angle = t.angle;
        printf("%Lf %Lf\n", k * (x * cos(angle) - y * sin(angle)), k * (x * sin(angle) + y * cos(angle)));
    }

    // system("pause");
    return 0;
}

C++ 代码 前缀和 $O(m)$

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 1000010;

int n, m;
double k[N], angle[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int op;
        double x;
        cin >> op >> x;
        if (op == 1)
            k[i] = x;
        else
            angle[i] = x, k[i] = 1;
    }
    k[0] = 1;
    for (int i = 1; i <= n; i++)
        k[i] *= k[i - 1], angle[i] += angle[i - 1];

    while (m--)
    {
        double x, y;
        int i, j;
        cin >> i >> j >> x >> y;
        double K = k[j] / k[i - 1], Angle = angle[j] - angle[i - 1];
        printf("%Lf %Lf\n", K * (x * cos(Angle) - y * sin(Angle)), K * (x * sin(Angle) + y * cos(Angle)));
    }
    return 0;
}

为什么后面我有写了一个前缀和呢，因为这个测评线段树只给了我80，我以为可能是时间上的常数过大，但是用前缀和写还是一样的80分，时间更长，只能说挺奇怪的，难道正解是有高精？还是用树状数组？

求有知道的大神能够解答

找到正解了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;
int flag[N];
double k[N];
double q[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        //scanf("%d%lf", &flag[i], &conf[i][0]);
        double w;
        scanf("%d%lf", &flag[i], &w);
        k[0] = 1;
        q[0] = 0;
        if(flag[i] == 1) {
            k[i] = k[i - 1] * w;
            q[i] = q[i - 1];
        }
        else {
            k[i] = k[i - 1];
            q[i] = q[i - 1] + w;
        }
    }
    for (int i = 1; i <= m; i ++ ){
        int a, b;
        double x, y;
        scanf("%d%d%lf%lf", &a, &b, &x, &y);


                x *= k[b]/k[a - 1];
                y *= k[b]/k[a - 1];
                double dx = x*cos(q[b] - q[a - 1]) -y*sin(q[b] - q[a - 1]);
                double dy = x*sin(q[b] - q[a - 1]) +y*cos(q[b] - q[a - 1]);
            x = dx;
            y = dy;


        printf("%lf %lf\n", x, y);
    }

    return 0;
}

根本没那么难，就是要数学推导