坦率机器猫

文章
5
资源
0
加入时间
2年10月17天

POJ - 1611 The Suspects(并查集)

2003年4月16日,世界卫生组织根据包括中国内地和香港地区,加拿大、美国在内的11个国家和地区的13个实验室通力合作研究的结果,宣布重症急性呼吸综合征的病因是一种新型的冠状病毒,称为SARS冠状病毒。很不幸,小明同学昨天晚上被确诊以经感染非典病毒,为此,校医院需要对他隔离治疗并隔离观察与他直接或间接接触者。可以认为,同一个社团内如果有人感染病毒或可能感染病毒,那么这个社团内所有人都被认为是可能已经感染了病毒,由于时间紧迫,需要尽快找到所有可能携带病毒的同学并隔离,以防止更大范围的病毒扩散,院长

hdu5869 Different GCD Subarray Query 线段树

题意:长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.题解:考虑固定左端点的不同GCD值,只有不超过logA种, 所以事件点只有nlogA个. 那么离线处理, 按照区间右端点排序从小到大处理询问,用一个树状数组维护每个GCD值的最大左端点位置即可. 复杂度是O(nlogAlogn).#includeusing namespace std;#