题目：人工湖
描述：
【题目描述】
有一个湖，他的周围都是城市，每个城市都只和他相邻的两个城市有道路相连。假设有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".
【样例输入】
5 10
1 2 5
0 4 5
1 4 5
0 2 3
1 3 4
1 1 3
0 1 2
0 2 3
1 2 4
1 2 5
【样例输出】
YES
YES
YES
NO
YES
NO
【提示】
30% 2<=n,m<=100
50% 2<=n,m<=10000
100% 2<=n,m<=100000
乍一看此题，容易想到可以用搜索来求，但是因为M过大，再加上N的范围也不小，复杂度最大$O(NM)$,所以30分弃疗……但是，树状数组可以很好解决这个问题。将数组开到2*n，下标为1..2*N，第X个单元代表着从X到（X+1） mod 2*N的路径状态，用1表示有，0表示没有。再开一个数组，来存储一些区间中道路情况总和，然后对于每一次改变操作，先进行判断，然后两次改变树状数组中的值。如果是查询操作，则分两次计算：
1. 求x~Y 之间路径总状态，然后判断（注意，如果为‘NO’，不跳出）
2. 求Y~X+N之间的路径总状态，然后判断即可。
具体实现并没有什么难度，中间添加了一些小技巧而已。但是……F=0时，X,Y的大小不一定是从小到大……害得我全WA了一次……改了一遍才AC……总之总算见到了不是那么果的一道树状数组的题……
AC代码：
{
program zht;
var
i,j,k,m,n,y,x,f,t,z1,z2:longint;
a:array[0..200000] of longint;
c:array[0..200000] of longint;
procedure change;
var
k:longint;
begin
k:=0;
if a[x]=1 then
begin
t:=-1;
a[x]:=0;
a[x+n]:=0;
end
else
begin
t:=1;
a[x]:=1;
a[x+n]:=1;
end; // 改变状态
k:=x;
while k<=2*n do
begin
c[k]:=c[k]+t;
k:=k+(k and (-k));
end;
k:=x+n;
while k<=2*n do
begin
c[k]:=c[k]+t;
k:=k+(k and (-k));
end; // 树状数组两次改值
end; // gai bian zhuang tai
procedure chazhao;
var
k:longint;
begin
k:=0;
k:=x-1;
while k>0 do
begin
z1:=z1+c[k];
k:=k-(k and (-k));
end;
k:=0;
k:=y-1;
while k>0 do
begin
z2:=z2+c[k];
k:=k-(k and (-k));
end;
z1:=z2-z1;
if z1=y-x then begin writeln('YES'); exit; end; // 直接查找
z1:=0;
z2:=0;
k:=y-1;
while k>0 do
begin
z1:=z1+c[k];
k:=k-(k and (-k));
end;
k:=x+n-1;
while k>0 do
begin
z2:=z2+c[k];
k:=k-(k and (-k));
end;
if z2-z1=n-(y-x) then writeln('YES') else writeln('NO'); // 反向二次查找
end;
begin
assign(input,'lakee.in');
assign(output,'lakee.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to 2*n-1 do
a[i]:=1;
for i:=1 to 2*n-1 do
begin
t:=i and (-i);
for j:=i-t+1 to i do
c[i]:=c[i]+1;
end;
for i:=1 to m do
begin
readln(f,x,y);
t:=0;
z1:=0;
z2:=0;
if x>y then begin t:=x; x:=y; y:=t; end; // 坑点~~~
t:=0;
if f=0 then change
else chazhao;
end; // 分类讨论
close(input);
close(output);
end. // 简短的主程序
}
<Marvolo原创，严禁转载>