| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
OrzIn Reply To:Problem E Posted by:ACRush at 2009-11-01 10:07:26 > E是查询问题,有n个数X0,X1...Xn-1 > > 有3中操作: > I p v: 得知X[p]=v > I p q v: 得知X[p] xor X[q]=v > Q k p1 p2 ... pk 计算X[p1] xor X[p2] xor ... xor X[pk] > > 算法: > 并查集 > > 对于操作I p q v,把root(p)和root(q)合并 > 对于操作I p v,把root(p)标注一定的信息 > 一旦发现合并或者标出是root(p)的信息冲突,就输出conflick > 对于操作Q k p1 p2 ... pk,如果pi中在某一个集合中出现了奇数次,并且这个集合的root没有被标注过,输出unknown,否则就一定可以计算。 > > 时间复杂度O(m*logn),其中m是总输入量 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator