http://www.tsinsen.com/ViewGProblem.html?gpid=-1000001307
【题意】
有一些编号为1..n的点，每个都有其初始坐标，有六类操作
Move i j a b 编号i到编号j的点移动一个(a,b)的向量
Patrol i j a 编号i到编号j的点绕原点逆时针旋转a（弧度制）
Lurk i j 编号i到编号j的点全部坐标变为(0,0)
Cancel a 撤销最后a次操作
Redo a 重做最后a次操作
Ask i 询问第i个点的坐标
数据不会进行不合法的操作，比如
Cancel 3
Move 1 1 1 1
Redo 2
【输入】
第一行一个n
接下来n行每行一个点的初始坐标
之后一行是个q，表示操作数
接下来每行一个操作
【输出】
对于Ask 操作，输出答案，误差小于0.0001即视为正确，有check。
这个询问只询问一个点……记录下对于每个点的操作就可以知道这个点的坐标了……
不过这个也询问不了一段区间……问区间问什么啊
对于Move操作，还是很好想到如何处理的吧
关键在于Patrol操作了
假设旋转角度为a，当前与x正半轴的夹角为b，距原点的距离为r=sqrt(x^2+y^2)
旋转前坐标为(r cos(b),r sin (b))
旋转后坐标为(r cos(a+b),r sin(a+b))
作为一个高中生，自然可以将其展开
旋转后坐标即为(r(cos(a)cos(b)-sin(a)sin(b)),r(sin(a)cos(b)+cos(a)sin(b)))=(cos(a)x-sin(a)y,sin(a)x+cos(a)y)
这么一来，就比较容易想到矩阵乘法了
假设不考虑Cancel和Redo的操作
用一个线段树来描述对于每个点的操作就好了，每个节点记录一个矩阵，询问一个节点的时候，只要把访问过的矩阵乘起来就好了
不过矩阵具有结合律，不具有交换律，所以维护矩阵的顺序性很重要，所以访问一个节点的话先下移懒标记，然后再进行插入操作
询问的话，询问过程中不要下传懒标记，把路过的节点的矩阵从底到顶乘起来就好了
接下来解决如何支持Cancel和Redo操作
仔细想想的话，Cancel就是回到过去线段树的某个状态，Redo就是再回去
这样我们把线段树所有状态记录下来不就好了吗
这个不可能吗……这个当然可能，一切的一切都开始于范浩强冬令营讲稿提到的一个概念 《函数性编程》
进行一个操作，新的线段树和原来的线段树有什么区别呢，区别在于有几个节点信息不一样
具体是几个节点呢，就是访问过的节点，最多logn个
那么我们可以把这些节点复制一份，连接上原来不需要修改的节点
这样每个节点可能有多个父亲节点，但子节点是唯一的……
即从上到下查询线段树得到的树是唯一的，即只要记录下每个状态的根节点，就可以查询到这个状态的树的信息……等价于记录了线段树的所有状态
这样就解决了这道题
函数性编程是十分前沿的一种思路，感觉高端选手都对此有很多的看法，需要注意吧
{$inline on}
program crisis;
uses
math;
const
eps=1e-10;
maxn=3000000;
type
matrix=array [1..3,1..3] of double;
var
now,tot,n,q,i,j,k:longint;
a,b:double;
root:array [0..50001] of longint;
x,y:array [0..20001] of double;
belong,left,right:array [0..maxn] of longint;
mat:array [0..maxn] of matrix;
squ:matrix;
order:char;
function matrixmul (a,b:matrix):matrix;inline;
var
ans:matrix;
i,j,k:longint;
begin
fillchar(ans,sizeof(ans),0);
for i:=1 to 3 do
for k:=1 to 3 do
if abs(a[i,k])>eps then
for j:=1 to 3 do
ans[i,j]:=ans[i,j]+a[i,k]*b[k,j];
exit(ans);
end;
procedure maketree (s,e,now:longint);
var
mid:longint;
begin
belong[now]:=0;
for mid:=1 to 3 do
mat[now][mid,mid]:=1;
if s=e then exit;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
maketree(s,mid,tot);
inc(tot);
right[now]:=tot;
maketree(mid+1,e,tot);
end;
procedure update (now:longint);inline;
begin
if left[now]=0 then exit;
if belong[left[now]]<>belong[now] then
begin
inc(tot);
mat[tot]:=mat[left[now]];
left[tot]:=left[left[now]];
right[tot]:=right[left[now]];
belong[tot]:=belong[now];
left[now]:=tot;
end;
mat[left[now]]:=matrixmul(mat[left[now]],mat[now]);
if belong[right[now]]<>belong[now] then
begin
inc(tot);
mat[tot]:=mat[right[now]];
left[tot]:=left[right[now]];
right[tot]:=right[right[now]];
belong[tot]:=now;
right[now]:=tot;
end;
mat[right[now]]:=matrixmul(mat[right[now]],mat[now]);
fillchar(mat[now],sizeof(mat[now]),0);
mat[now][1,1]:=1;
mat[now][2,2]:=1;
mat[now][3,3]:=1;
end;
procedure insert (s,e,l,r,last,now:longint);
var
mid:longint;
begin
update(last);
mat[now]:=mat[last];
if (s=l)and(e=r) then
begin
mat[now]:=matrixmul(mat[now],squ);
left[now]:=left[last];
right[now]:=right[last];
exit;
end;
mid:=(l+r) div 2;
if e<=mid then
begin
inc(tot);
left[now]:=tot;
belong[tot]:=now;
mat[tot]:=mat[left[last]];
right[now]:=right[last];
insert(s,e,l,mid,left[last],left[now]);
end
else
if s>mid then
begin
left[now]:=left[last];
inc(tot);
right[now]:=tot;
belong[tot]:=belong[now];
mat[tot]:=mat[right[last]];
insert(s,e,mid+1,r,right[last],right[now])
end
else
begin
inc(tot);
left[now]:=tot;
belong[tot]:=now;
mat[tot]:=mat[left[last]];
inc(tot);
right[now]:=tot;
belong[tot]:=belong[now];
mat[tot]:=mat[right[last]];
insert(s,mid,l,mid,left[last],left[now]);
insert(mid+1,e,mid+1,r,right[last],right[now]);
end;
end;
function find (x,l,r,now:longint):matrix;
begin
if l=r then exit(mat[now]);
if x<=(l+r) div 2 then
exit(matrixmul(find(x,l,(l+r) div 2,left[now]),mat[now]))
else
exit(matrixmul(find(x,(l+r) div 2 +1,r,right[now]),mat[now]));
end;
begin
read(n);
for i:=1 to n do
read(x[i],y[i]);
maketree(1,n,0);
readln(q);
while q>0 do
begin
dec(q);
read(order);
case order of
'M':begin
read(order,order,order);
read(i,j,a,b);
fillchar(squ,sizeof(squ),0);
squ[1,1]:=1;
squ[2,2]:=1;
squ[3,3]:=1;
squ[3,1]:=a;
squ[3,2]:=b;
inc(tot);
inc(now);
root[now]:=tot;
belong[tot]:=now;
insert(i,j,1,n,root[now-1],root[now]);
end;
'P':begin
read(order,order,order,order,order);
read(i,j,a);
fillchar(squ,sizeof(squ),0);
squ[1,1]:=cos(a);
squ[2,1]:=-sin(a);
squ[1,2]:=sin(a);
squ[2,2]:=cos(a);
squ[3,3]:=1;
inc(tot);
inc(now);
root[now]:=tot;
belong[tot]:=now;
insert(i,j,1,n,root[now-1],root[now]);
end;
'L':begin
read(order,order,order);
read(i,j);
fillchar(squ,sizeof(squ),0);
squ[3,3]:=1;
inc(tot);
inc(now);
root[now]:=tot;
belong[tot]:=now;
insert(i,j,1,n,root[now-1],root[now]);
end;
'C':begin
read(order,order,order,order,order);
read(i);
now:=now-i;
end;
'R':begin
read(order,order,order);
read(i);
now:=now+i;
end;
'A':begin
read(order,order);
read(i);
squ:=find(i,1,n,root[now]);
writeln(x[i]*squ[1,1]+y[i]*squ[2,1]+squ[3,1]:0:5,' ',
x[i]*squ[1,2]+y[i]*squ[2,2]+squ[3,2]:0:5);
end;
end;
readln;
end;
end.