维护一个线段树和一个相对变化角度的数组，每个线段树节点表示从左子树到右子树的向量，每条线段（叶子节点）一经初始化后就不改变vx, vy，只需更新父节点即可。
#include <cstdio> #include <cmath> const double pi = acos(-1.0); const int st_size = (1 << 15) - 1; const int maxn = 10000 + 10; const int maxc = 10000 + 10; int L[maxn]; int S[maxc], A[maxn]; //线段树所维护的数据 double vx[st_size], vy[st_size]; //各节点的向量 double ang[st_size]; //各节点的角度 //为了查询角度的变化而保存的当前角度的数组 double prv[maxn]; //初始化线段树 //k是节点的编号，l, r表示当前节点对应的是[l, r)区间 void init(int k, int l, int r) { ang[k] = vx[k] = 0.0; if (r - l == 1) { //叶子节点 vy[k] = L[l]; } else { //非叶子节点 int chl = k * 2 + 1; int chr = k * 2 + 2; init(chl, l, (l + r) / 2); init(chr, (l + r) / 2, r); //初始时线段按竖直排列，vx为0，只将vy相加即可 vy[k] = vy[chl] + vy[chr]; } } //把s和s+1的角度变为a //v是节点的编号，l, r表示当前节点对应的是[l, r)区间 void change(int s, double a, int v, int l, int r) { if (s <= l) { return; } else if (s < r) { int chl = v * 2 + 1; int chr = v * 2 + 2; int m = (l + r) / 2; change(s, a, chl, l, m); change(s, a, chr, m, r); if (s <= m) { ang[v] += a; } double s = sin(ang[v]), c = cos(ang[v]); vx[v] = vx[chl] + (c * vx[chr] - s * vy[chr]); vy[v] = vy[chl] + (s * vx[chr] + c * vy[chr]); } } int main(int argc, char const *argv[]) { int n, c; while (scanf("%d%d", &n, &c) == 2) { for (int i = 0; i < n; i++) { scanf("%d", &L[i]); } for (int i = 0; i < c; i++) { scanf("%d%d", &S[i], &A[i]); } //初始化 init(0, 0, n); for (int i = 1; i < n; i++) { prv[i] = pi; } //处理操作 for (int i = 0; i < c; i++) { int s = S[i]; double a = A[i] / 360.0 * 2 * pi; change(s, a - prv[s], 0, 0, n); prv[s] = a; printf("%.2f %.2f\n", vx[0], vy[0]); } putchar('\n'); } return 0; }