题意：
有一个n×m的地图，上面有三种符号 分别表示向上，，向左，向右
有两种操作，A X Y询问从一个点（X，Y）开始最终会走到哪个点或者死循环 ， C X Y ch 表示将地图上（X，Y）的符号换成ch
考虑到没有向下的操作，那么陷入死循环的情况只有一种可能即’>’ ‘<‘
用分块操作，分成sqrt（n）块，用DP预处理每一块中的点可以到哪个点，-1表示这个点死循环
对于操作A，如果这个点移动到了所在的块的边界处，则输出。否则递归的输出上面的一块
对于操作C，重新对点所在的块进行DP，由于C操作最多只有1W次，又进行了分块处理，所以不会太慢。。。。
D. Conveyor Belts
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Automatic Bakery of Cyberland (ABC) recently bought ann×mrectangle table. To serve the diners, ABC placed seats around the table. The size of each seat is equal to a unit square, so there are2(n+m)seats in total.
ABC placed conveyor belts on each unit square on the table. There are three types of conveyor belts: "^", "<" and ">". A "^" belt can bring things upwards. "<" can bring leftwards and ">" can bring rightwards.
Let’s number the rows with1tonfrom top to bottom, the columns with1tomfrom left to right. We consider the seats above and below the top of the table are rows0andn+1respectively. Also we define seats to the left of the table and to the right of the table to be column0andm+1. Due to the conveyor belts direction restriction there are currently no way for a diner sitting in the rown+1to be served.
Given the initial table, there will beqevents in order. There are two types of events:
"Axy" means, a piece of bread will appear at rowxand columny(we will denote such position as(x,y)). The bread will follow the conveyor belt, until arriving at a seat of a diner. It is possible that the bread gets stuck in an infinite loop. Your task is to simulate the process, and output the final position of the bread, or determine that there will be an infinite loop."Cxyc" means that the type of the conveyor belt at(x,y)is changed toc.
Queries are performed separately meaning that even if the bread got stuck in an infinite loop, it won’t affect further queries.
Input
The first line of input contains three integersn,mandq(1≤n≤105,1≤m≤10,1≤q≤105), separated by a space.
Nextnlines, each line containsmcharacters, describing the table. The characters can only be one of "<^>".
Nextqlines, each line describes an event. The format is "C x y c" or "A x y" (Consecutive elements are separated by a space). It’s guaranteed that1≤x≤n,1≤y≤m.cis a character from the set "<^>".
There are at most10000queries of "C" type.
Output
For each event of type "A", output two integerstx,tyin a line, separated by a space, denoting the destination of(x,y)is(tx,ty).
If there is an infinite loop, you should outputtx=ty=-1.
Sample test(s)
input
2 2 3>>^^A 2 1C 1 2 <A 2 1
output
1 3-1 -1
input
4 5 7><<^<^<^^>>>>^>>^>>^A 3 1A 2 2C 1 4 <A 3 1C 1 2 ^A 3 1A 2 2
output
0 4-1 -1-1 -10 20 2
Note
For the first sample:
If the bread goes from(2,1), it will go out of the table at(1,3).
After changing the conveyor belt of(1,2)to "<", when the bread goes from(2,1)again, it will get stuck at "><", so output is(-1,-1).
纵然走过那么多城市，对于未知的风景，还是好奇。
