推荐题目：洛谷 P5843 [SCOI2012] Blinker 的噩梦

推荐题目洛谷P5843 [SCOI2012] Blinker 的噩梦题目描述一天 Blinker 醒来发现自己成为了一个二维世界的点而且被标记上了一个奇怪的值。这个世界是由N NN个边界互不相交且不相切的图形组成这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次 Blinker 走进或走出某个图形时相切时经过不算Blinker 的标记值就会被异或上那个值。现在我们记录了 Blinker 在这个世界的M MM天的信息。每天可能发生两种事情一种是某个图形的权值更改为某个值另一种是 Blinker 从某个点走到另一个点。我们假设 Blinker 首次出发前的标记值为0 00我们希望知道他每次到达目的地后的标记值。输入格式输入的第一行包含2 22个数N NN和M MM分别表示这个世界的图形数和记录的天数。接下来有N NN行每行表示一个图形。如果一行以字符C开头表示这个图形是一个圆后面紧跟着三个实数x xx,y yy,r rr和一个整数v vv分别表示圆的x xx坐标y yy坐标和圆的半径以及该图形对应的值。如果一行以字符P开头表示这个图形是凸多边形后面紧跟着一个整数L LL表示凸多边形的点数然后后面有L LL对实数x 0 x_0x0​,y 0 y_0y0​,x 1 x_1x1​,y 1 y_1y1​⋯ \cdots⋯表示L LL个点的坐标这一行最后一个数是一个整数v vv表示这个图形对应的值保证凸多边形上的点按照顺时针给出。接下来有M MM行每行表示一天的记录信息。如果一行以字符Q开头表示这一天 Blinker 出行了接下来有x 0 , y 0 , x 1 , y 1 x_0,y_0,x_1,y_1x0​,y0​,x1​,y1​四个实数分别表示出发点的坐标和目的地的坐标。如果一行以字符C开头表示这一天某个图形的值改变了接下来有两个i ii和v vv表示输入中第i ii个出现的图形的值变成v vv。输出格式对于 Blinker 的每个出行输出他到达目的地后的标记值很显然这个值与 Blinker 的路径无关。输入输出样例 #1输入 #12 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输出 #10 2 0说明/提示样例解释样例的世界形如上图第一天 Binker 的初始标记值为0 00可能从A AA沿直线走到B BB或者他绕过圆走到B BB他的标记值最终都保持不变为0 00假设沿直线从A AA走到B BB共穿过4 44次边界Binker 的标记值变化过程为1 , 3 , 1 , 0 1,3,1,01,3,1,0;第二天 Binker 的初始标记值为0 00他通过某种不经过图形边界的方法到达了C CC点即 Binker 瞬间移动或闪烁然后从C CC沿某种路径走到D DD这时他的标记值变为2 22第三天圆的权值变为1005 10051005第四天 Binker 的初始标记值为2 22他再次回到C CC并再次从C CC走到D DD这时他的标记值又变为0 00。数据范围对于30 % 30\%30%的数据1 ≤ M ≤ 10.00 1 \le M \le 10.001≤M≤10.00凸多边形的点数加上圆的个数小于等于1000 10001000对于100 % 100\%100%的数据1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤1051 ≤ M ≤ 10 5 1 \le M \le 10^51≤M≤105单个凸多边形的点数小于等于34 3434。图形互不相交且 Binker 的出发点和目的地不在图形的边界。