## HDU 6039 Gear Up 并查集 dfs序 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6039

# Gear Up

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:
1. They share a common edge (i.e. they have equal linear velocity).
2. They share a common shaft (i.e. they have equal angular velocity).
It is guaranteed that no pair of gears meets both of the above conditions.
A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.
Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.
sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

### Input

There are multiple test cases (about $30$).
For each test case:
The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$
The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$
Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
$a = 1$ means to replace the $x$-th gear with another one of radius $y$.
$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

### Output

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

# Differencia

Time Limit: 10000/10000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Professor Zhang has two sequences a1,a2,...,an and b1,b2,...,bn. He wants to perform two kinds of operations on the sequences:
1. + l r x: set ai to x for all lir.
2. ? l r: find the number of i such that aibi and lir.

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains four integers n, m, A and B (1n105,1m3000000,1A,B216) -- the length of the sequence, the number of operations and two parameters.
The second line contains n integers a1,a2,...,an (1ai109). The third line contains n integers b1,b2,...,bn (1bi109).
As there are too many operations, the m operations are specified by parameters A and B given to the following generator routine.

For the i-th operation, first call rnd(last) three times to get l, r and x (i.e. l = rnd(last) % n + 1, r = rnd(last) % n + 1, x = rnd(last) + 1). Then if l>r, you should swap their value. And at last, the i-th operation is type ?, if (l+r+x) is an even number, or type + otherwise.
Note: last is the answer of the latest type ? operation and assume last=0 at the beginning of each test case.

Output
For each test case, output an integer S=(i=1mizi) mod (109+7), where zi is the answer for i-the query. If the i-th query is of type +, then zi=0.

Sample Input

3
5 10 1 2
5 4 3 2 1
1 2 3 4 5
5 10 3 4
5 4 4 2 1
1 2 3 4 5
5 10 5 6
5 4 5 2 1
1 2 2 4 5

Sample Output
81
88
87

Author
zimpha
Source