利用并查集处理合并，并保存每个块对应的覆盖范围(在y轴上的)上下界；利用线段树（更新区间的范围从并查集维护的信息中得到）维护每个x.5的点对应的州数和城市数。区间修改单点查询，只要确定好x.5这些点在线段树中的对应的下标就可以了，我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1，只能把读进来的东西都++。具体的操作：对于road，先找两个点是否在一个块里，如果是了那就不用任何操作（画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了），否则先把这两个的分别的块对应的区域在线段树中减去他的影响，再将两个块合并之后，再在线段树中加上这一新块的影响。先减后加，这样就可以避免繁杂的分类讨论了。。。
第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了，推了一下感觉可以去掉maintain的操作。。。试了下果然可以，而且快了很多，在vjudge上已经是用线段树的跑的最快的了（前几名都是用的BIT emmm
wa的点：本来一气呵成写完很舒服但是没想到出了很多bug，因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
继续阅读“[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom”