【NOIP模拟赛by wulala】公主的朋友

2014年8月16日1,1440

出题人说:正解分块。。。

但是这不是和某次cf的dzy loves color一样么T T

修改的时候顺便查询,如果要修改的这一段宗教相同,打个标记并且统计答案后return

否则递归

复杂度我们可以这样想

因为如果修改1-n,但是宗教都不同,这样是每个都要递归到最下面,这样一次修改就要nlogn

但是这种情况并不会一直出现,询问完后1-n会被修改成同一种宗教,再把1-n变成不同的,又要额外修改n次

也就是说,每次修改,最多让后面的查询多一个logn

所以这样均摊复杂度是logn的