[SCOI2012]Blinker的噩梦

时间限制:50s      空间限制:512MB

题目描述

一天Blinker醒来,发现自己成为了一个二维世界的点,而且被标记上了一个奇怪的值。 这个世界是由N个边界互不相交(且不相切)的图形组成,这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次Blinker走进或走出某个图形时(相切时经过不算),Blinker的标记值就会被异或上那个值。 现在,我们记录了Blinker在这个世界的M天的信息。每天可能发生两种事情,一种是某个图形的权值更改为某个值;另一种是Blinker从某个点走到另一个点。 我们假设Blinker首次出发前的标记值为0,我们希望知道他每次到达目的地后的标记
值。


输入格式

输入的第一行包含2个数,N和M,分别表示这个世界的图形数和记录的天数。 接下来有N行,每行表示一个图形。 如果一行以字符C开头,表示这个图形是一个圆,后面紧跟着三个实数x, y, r和一个整数v,分别表示圆的x坐标,y坐标和圆的半径以及该图形对应的值。 如果一行以字符P开头,表示这个图形是凸多边形,后面紧跟着一个整数L,表示凸多
边形的点数,然后后面有L对实数x0,y0,x1,y1…,表示L个点的坐标,这一行最后一个数是一个整数v,表示这个图形对应的值,保证凸多边形上的点按照顺时针给出。 接下来有M行,每行表示一天的记录信息。
如果一行以字符Q开头,表示这一天Blinker出行了,接下来有x0,y0,x1,y1四个实数,
分别表示出发点的坐标和目的地的坐标。
如果一行以字符C开头,表示这一天某个图形的值改变了,接下来有两个i 和v,表示
输入中第i 个出现的图形的值变成v。


输出格式

对于Blinker的每个出行输出他到达目的地后的标记值,很显然这个值与Blinker的路径
无关。


样例输入

2 4 
C 0 0 2 1 
P 4 -1 -1 -1 1 1 1 1 -1 2 
Q -2 -2 2 2 
Q -1.5 0 0.0 0.0 
C 1 1005 
Q -1.5 0 0.0 0.0 

样例输出

0 
2 
0 

提示

对于30%的数据,保证:

1<=M<=10.0,凸多边形的点数加上圆的个数小于等于1000

剩余数据中,保证:

存在一组无图形值变动的数据;

存在一组无凸多边形的数据;

对于100%的数据,保证:

1<=N<=1000001<=M<=100000,单个凸多边形的点数小于等于34。图形互不相交,且Blinker的出发点和目的地不在图形的边界。


题目来源

没有写明来源