2014
03-16

# The Beijing-Hangzhou Grand Canal

The Beijing-Hangzhou Grand Canal is the longest artificial canal, in which many transportation companies run their boats. Each transportation company is responsible for transporting on one leg of the river. For the regulations of the GBs, each company is only allowed to have the same type boats.

The sands of the river keep changing the depth of the water. Boats will get stranded if the water depth is less than the waterline, so the GM often digs the riverbed to maintain watercourse to transport smoothly.

Mr April wants to send a gift to Ms April for her birthday via the canal. But he do not know whether the watercourse is smooth, he turns to intelligent you for help to tell him whether he can deliver the gift or not.

In the first line ,there are 3 non-negative interger , S, H and X, S stands for the length of the river, H is the original depth of the water, and there are X transportation companies.

Then follow X lines, in the (1+i)th line ,there are 3 numbers, a , b, and c, indicate Company i is responsible for the transportation between a and b, and c is the waterline of the boats from the company.

In (X+2)th line there is an interger Q , indicating there would be Q command lines. There are 4 variations of the command.

(1)F a b h meaning for sand silting, from a to b of the river the water depth has reduce to h meters,but those places where the depth is less than h meters remain the same.

(2)D a b h indicating the GM is trying removing the sand silting and the water depth reaches h meters ,but those places where the depth is more than h meters keeps the same.

(3)O a b implying Mr April wants to know whether there is a possible ways to deliver the gift from a to b. In other words, he wants to find a way to cover the segment [a, b] or [b,a] by one or some company’s available boats.

(4)C a h saying Company a has changed all its boats to new ones which has the waterline as h.

0<S<100000, 0<=x<=100,0<=H <=1000, 0<=Q<=1000

In the first line ,there are 3 non-negative interger , S, H and X, S stands for the length of the river, H is the original depth of the water, and there are X transportation companies.

Then follow X lines, in the (1+i)th line ,there are 3 numbers, a , b, and c, indicate Company i is responsible for the transportation between a and b, and c is the waterline of the boats from the company.

In (X+2)th line there is an interger Q , indicating there would be Q command lines. There are 4 variations of the command.

(1)F a b h meaning for sand silting, from a to b of the river the water depth has reduce to h meters,but those places where the depth is less than h meters remain the same.

(2)D a b h indicating the GM is trying removing the sand silting and the water depth reaches h meters ,but those places where the depth is more than h meters keeps the same.

(3)O a b implying Mr April wants to know whether there is a possible ways to deliver the gift from a to b. In other words, he wants to find a way to cover the segment [a, b] or [b,a] by one or some company’s available boats.

(4)C a h saying Company a has changed all its boats to new ones which has the waterline as h.

0<S<100000, 0<=x<=100,0<=H <=1000, 0<=Q<=1000

10 2 2
1 6 4
5 8 2
8
O 5 7
O 3 7
D 3 5 4
O 3 7
F 6 7 1
O 3 7
C 2 1
O 3 7
4 3 2
1 2 1
3 4 2
1
O 2 3

Yes
No
Yes
No
Yes
Yes

1. [email protected]

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧