•【题目描述】

有一个湖，他的周围都是城市，每个城市都只和他相邻的两个城市有道路相连。假设有n个城市，编号1-n，公路是双向的，公路有时候是好的，有时候是坏的，现在询问你两个城市是否可以互相到达。

•【输入格式】

第一行两个数，一个2<=n<=100000  和 1<=m<=100000，分别代表城市数目和询问次数；

接下来m行，每一行三个数f，a，b。f=0时，如果公路a，b之间的道路之前是好的，现在就变成坏的，如果之前是坏的，现在就变成好的。f=1时，询问a，b两个城市是否可以互相到达。

•【输出格式】

对于每一个f=1的询问，能到达输出“YES”，否则输出"NO".

思路如下：

首先，我们可以设g[x]数组表示x号城市与x+1号城市之间的道路好坏情况：g[x]=1时表示坏，g[x]=0时表示好，同时设sz为坏的道路的个数。

因为所有城市围起来形成一个圆，规定x到（x+1）号城市为顺时针方向，x到（x-1）号城市为逆时针方向。

我们来谈谈f=1时，即判断a、b两城市是否可以到达（预处理使a<b）。

那么在判断a、b两城市是否可以到达时，我们只需考虑两种情况：

（1）：沿顺时针道路判断是否可以到达

令G=g[a]+g[a+1]+g[a+2]+……+g[b-1]（即a沿顺时针到b间的路径间坏的道路的个数）很明显，我们只需判断G是否>=1。若是，则表示a沿顺时针到b之间的路径有坏的道路，不能从a顺时针到达b。

（2）：沿逆时针道路判断是否可以到达

其实思路也不难想出，我们可以简单地处理出sz（即坏的道路的个数），若sz-G=0，

即表示除a沿顺时针到b的路径间坏的道路外，没有坏的道路，这就等同于a沿逆时针到b的路径间没有坏的道路，可以从a到b。

反之（sz-G不为0）则表示a沿逆时针到b之间的路径有坏的道路，不能从a顺时针到达b。

好了，现在你已经了解了这题的大致思路了，那么就尝试AC吧！！！（不是

以上思路大家肯定都想到了（所以以上都是废话），那么我们开始优化时间吧！

我们懂得，若按照以上思路暴力求解，那么时间复杂度为O(nm)，只能拿到50pts

接下来考虑100pts算法

我们可以发现g是一维数组，求G为g的区间求和，那么很自然的就联想到树状数组

设树状数组f[x]表示坏的道路的个数， G=g[a]+g[a+1]+g[a+2]+…… +g[b-1] =求和f(b-1)-求和f(a-1）

然后1与n号城市间的道路做个特殊处理。

最后推荐大家参考代码理解（COGS代码已开放）

Over!!!