[CTSC2015] 葱
题目描述
小葱和小绪是一对好朋友,自从小葱11连出了1UR2SR之后,小绪就觉得小葱的人品特别好,于是小绪给小葱出了一道题来测试小葱的人品。
小绪首先在平面上画了$N$个点,分别是$P_1,P_2,...,P_N$。
小绪把这$N个点$顺次相连,即连接$(P_1,P_2),(P_2,P_3),...,(P_{N-1},P_N)$,得到$N-1$条线段。
之后小绪每次在平面上画出一条直线,然后问小葱这条直线与多少条线段相交。特别的,在线段端点处相交算作相交,直线完全覆盖线段时也算作相交。 这样的问题自然难不倒小葱,小葱只需要凭自己的人品用直觉就能给出正确的答案。
小绪想测试小葱的人品究竟有多好,于是他加大了问题的难度: 除了每次询问以外,小绪会不时地讲一个新的点$P$插入到$P_i$和$P_{i+1}$之间,然后按照顺序对所有的点重新标记下标,即在$P_i$之后的点的下标会依次增加,而点$P$会变成新的点$P_{i+1}$。
特别的,点$P$也可以插入到第一个点之前或最后一个点之后。
人品超级好的小葱依旧能够轻松的给出答案,于是小绪又进一步提高了难度:
每次插入或提问之后,小绪都将操作后的所有线段记录了下来,称作一个历史版本。历史版本$T$表示在第$T$次操作后得到的历史版本。
插入新点的操作改为了在某一个历史版本$T$的基础上,插入一个点$P$,并得到一个新的历史版本。
小绪对小葱的提问改为了对于一个历史版本$T$,给出一条直线,询问这条直线会与多少条线段相交。
小葱虽然人品很好,但面对这样的问题却也束手无策了,他只好找到来参加CTSC的你,请你来帮他解决这个问题。
输入输出格式
输入格式
第一行两个整数$N,M,C$,表示一开始的点数和总共的操作数,以及数据是否加密。
如果$C=1$,那么代表数据被加密过,每次询问操作中的$X_0,Y_0,X,Y$以及插入操作中的$X,Y$都是被加密过的数据,你需要将它们异或last_ans从而得到正确的数据,其中last_ans是上一次询问的答案,刚开始last_ans=0。
接下来$N$行每行两个整数,其中第$i$行的两个整数表示$P_i$的横坐标和纵坐标。
接下来$M$行,表示小绪的$M$次操作,其中第$i$行(从$1$开始标号)操作后得到的结果为历史版本$i$。
对于每次操作,首先会有一个字母代表小绪的这次操作的操作类型。
如果这个字母是$'H'$,代表本次操作为一次询问操作。接下来会有五个整数$T,X_0,Y_0,X,Y$,代表在历史版本$T$的情况下,小绪给出一条经过$(X_0,Y_0)$,方向为$(X,Y)$的直线,小葱要回答出它会和多少条直线相交。
如果这个字母是$'Z'$,代表本次操作为一次插入操作。接下来会有四个数$T,i,X,Y$,代表小绪在历史版本$T$的基础上,在$P_i$后面插入了一个坐标为$(X,Y)$的点。特别地,如果$i=0$,表示该点在$P_1$之前。
输出格式
要求对每一次询问操作,输出一行一个整数代表小葱应该回答的正确答案。
输入输出样例
输入样例 #1
2 3 0
0 0
1 1
H 0 1 0 -1 1
H 1 0 1 1 1
H 2 -1 -1 1 1
输出样例 #1
1
0
1
说明
样例解释1:
对于第三次询问,直线完全覆盖了线段,小绪会认为这也算相交。
数据规模和约定:
保证每次询问操作的$T$一定小于等于当前操作的数量,所有输入数据均为整数。
有以下$4$类特殊数据,它们两两没有交集:
1. 对于10%的数据,保证$1≤N,M≤1000$;
2. 对于15%的数据,保证对于第$i$次操作,$T=i-1$;
3. 对于15%的数据,保证$C=0$且不存在修改操作;
4. 对于15%的数据,对于询问操作,保证$Y=0$(加密过的数据指解密后的$Y$),即给出的直线平行于$x$轴。
以上数据还保证$1≤N,M≤5*10^4$。
对于100%的数据,保证$1≤N,M≤10^5$,所有的坐标范围在$[-10^8,10^8]$内,且每组数据中所有询问的答案总和不超过$10^6$,插入操作的次数不会超过$5*10^4$。注意这些线段可能会互相相交。