SGU 336. Elections

336. ElectionsTime limit per test: 7.50 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard

New parliament election in Berland is coming soon. Each of N political parties wants to be elected into the parliament. There is a law in Berland that allows only parties with more than a certain amount of votes be elected. Thus, some of the smaller parties are trying to use different technologies to collect necessary amount of votes.

The first technology is completely legal. Two or more parties can go to the elections together, forming so-called .

The second technology is not so legal. Some parties have specific information about their opponents. Those opponents don’t want this information to become public.

If several parties join into one election block, their information is joined together as well. Thus, they become more powerful. However, the opponents of each party of the block know something discreditable about the whole block. The party or block might have some ‘black’ information on itself.

Let us now enumerate parties with the integers from 1 to N. Parties and blocks are allowed to join together into new blocks. Those blocks are numbered with the consecutive integers (N+1, N+2, etc.).

You are to write a program that processes queries of two different kinds.

  • Query ‘ 1 a b ‘ means that you have to answer the question: is there any discreditable information that party or block a knows about party or block b?
  • Query ‘ 2 a b ‘ means that you need to join party or block a with party or block b. The new block will have all the information a has, and all the information b has. All the information that was known by some parties or blocks about a and b now concerns the newly created block.

InputThe first line of the input file contains integers N and M (1 ≤ N ≤ 105; 1 ≤ M ≤ 2 · 105). Next M lines contain pairs of integers a and b denoting that party a knows something discreditable about party b (1 ≤ ab ≤ N). The next line contains single integer number Q (1 ≤ Q ≤ 2 · 105). Each of the next Q lines contains a query. A query of the first kind looks like ‘1 a b’. A query of the second kind looks like ‘2 a b’. You should process queries in the order they are given. Each pair ab references only existing parties or blocks. It is guaranteed that numbers a and b are different in any ‘2 a b’ query, but they can be equal in a ‘1 a b’ query. 

OutputWrite on the separate lines of the output file answer YES or NO for each query of the first kind.

Example(s) sample input sample output 4 6 1 2 1 3 3 2 4 4 2 4 1 2 4 1 3 4 2 2 3 1 5 4 1 4 5 NO YES NO 额。。其实这题挺裸的阿炯。。不知道为神马AC的人那么少炯。。
合并关系可以看成一颗树,那么如果先序遍历一下,一个顶点对应的所有原来的顶点
就是一个区间了。。那么只需要询问某个定点掌握的黑资料里面有没有一个区间内的数。。
用set进行启发式合并,就可以在LogN完成询问。。
然后set和启发式合起来就是O(NLogN^2)。。。
或者把黑资料也用一样的方式先序遍历一下
问题就变成一行数,然后每次询问一段数中有没有一个区间的数。。
用离线+树状数组可以NLogN搞定。。
或者用线段树可以NLogN + LogN^2*Q搞定。。
或者用划分树可以NLogN + LogN*Q搞定。。
Code:
www.ideone.com/a1nJa

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>