思路:

线段树每个节点维护第一条线段起点指向最后一条线段终点的向量,于是每一个操作都是一次区间更新。使用成段更新的线段树即可。
实现:

 #include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> using namespace std; const int MAXN = ;
const double PI = acos(-1.0); int a[MAXN], d[MAXN], n, c;
struct node
{
double x, y;
int lazy;
};
node tree[MAXN << ];
double trans(int d) { return (double)d * PI / 180.0; }
void rotate(double & x, double & y, int dx)
{
double tx = x * cos(trans(dx)) - y * sin(trans(dx));
double ty = y * cos(trans(dx)) + x * sin(trans(dx));
x = tx; y = ty;
}
void pushdown(int num)
{
if (!tree[num].lazy) return;
int tmp = tree[num].lazy;
rotate(tree[num << ].x, tree[num << ].y, tmp);
rotate(tree[num << | ].x, tree[num << | ].y, tmp);
tree[num << ].lazy += tmp;
tree[num << | ].lazy += tmp;
tree[num].lazy = ;
}
void pushup(int num)
{
tree[num].x = tree[num << ].x + tree[num << | ].x;
tree[num].y = tree[num << ].y + tree[num << | ].y;
}
void build(int num, int l, int r)
{
if (l == r) { tree[num].y = a[r]; return; }
int m = l + r >> ;
build(num << , l, m);
build(num << | , m + , r);
pushup(num);
}
void update(int num, int l, int r, int x, int y, int dx)
{
if (x <= l && y >= r)
{
rotate(tree[num].x, tree[num].y, dx);
tree[num].lazy += dx;
return;
}
int m = l + r >> ;
pushdown(num);
if (x <= m) update(num << , l, m, x, y, dx);
if (y >= m + ) update(num << | , m + , r, x, y, dx);
pushup(num);
} int main()
{
while (scanf("%d %d", &n, &c) != EOF)
{
for (int i = ; i <= n * ; i++) { tree[i].x = tree[i].y = ; tree[i].lazy = ; }
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i < n; i++) d[i] = ;
build(, , n);
int x, y;
for (int i = ; i < c; i++)
{
scanf("%d %d", &x, &y);
int dx = y - d[x];
d[x] = y;
update(, , n, x + , n, dx);
printf("%.2f %.2f\n", tree[].x, tree[].y);
}
puts("");
}
return ;
}

最新文章

  1. 1.javascript篇(基础)
  2. coffeeScript中类的继承[学习篇]
  3. C++之再续前缘(二)——类和对象(上)
  4. 华为OJ题目:刷题
  5. WTF,这到底是在做什么?
  6. phpcms 02
  7. 错误:Error:未定义标识符&quot;_TCHAR&quot;
  8. 安装eclipse for JavaEE 后的一些设置
  9. qemu kvm 虚拟化
  10. ACM比赛技巧
  11. redis来共享各个服务器的session,并同时通过redis来缓存一些常用的资源,加快用户获得请求资源的速度(转)
  12. bdev文件系统
  13. 第三章 PL/SQL编程
  14. UWP 手绘视频创作工具技术分享系列 - SVG 的解析和绘制
  15. java基础部分的简单应用
  16. JToken和BsonValue对象的相互转换
  17. springcloud灰度发布实现方案
  18. [转]SQL server2008 导入超大SQL脚本文件(超过10M)
  19. 骚年,看我如何把 PhantomJS 图片的 XSS 升级成 SSRF/LFR
  20. vscode 集成 cygwin 的注意事项

热门文章

  1. QtQuick桌面应用开发指导 1)关于教程 2)原型和设计 3)实现UI和功能_A
  2. php 文件压缩zip扩展
  3. ImageLoader实现图片异步载入
  4. 关于 equals()与hashcode()方法
  5. 【iOS系列】-使用CAGradientLayer设置渐变色
  6. java语法基础(一)
  7. __setup 在内核中的作用【转】
  8. 软件开发-MSF方法(《构建之法》读书笔记2)
  9. Python基础第七天
  10. html/html5中的download属性