01、实例分析：人工湖公路

问题描述:

有一个湖，它的周围都是城市，但是由于水路不发达，所以在城市间来往都是靠陆地交通。很奇怪，每一个城市都只和与它相邻的城市建有公路，假设有n个城市，编号依次是1到n，那么编号为i的城市只和i%n+1,(i-2+n)%n+1两个城市有公路相连。公路是双向的，有的公路已坏，但是有的公路又会被工人修好。现在有人向你询问某两个城市是否可以互相到达。
输入:

第一行有两个数n和m（2≤n≤100000和1≤m≤100000）,分别代表城市的数目和询问次数，接下来有m行，每一行一个标志数f和两个城市的编号x，y。

当f=0时，如果x，y之间的公路是好的，则x，y之间的公路会坏掉，否则x，y之间的公路将被修好。

当f=1时，代表那个人要向你询问x，y之间是否可以相互到达。

输入到文件结束。

输出:

对于每次询问，若x，y互相可以到达，则输出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

解题思路:

(1) 这个题看似用一个搜索就可以解决，确实是可以得出正确答案，因为是否可以到达两个城市，无非有两种情况，画上圆后编号，顺时针走过去或者逆时针走过去，只要广度优先搜索就可以了，但是因为数据范围超限，故这种方法是行不通的。

(2) 这些城市之间的公路很奇怪，只有相邻的两个城市之间有公路，我们用1表示当前公路和它的下一条公路相连，用0表示不相连，那么，要知道两个城市是否相连，只要知道它们之间顺时针的1的个数是否等于它们之间顺时针间的城市个数就可以了，或者只要知道逆时针的1的个数是否等于它们之间逆时针间的城市个数就可以了。这时可采用快速求和的方法，如树状数组。

用一个数组记录当前这个城市是否和它的下一个城市相连，若相连，则将数组设置为1，否则设置为0，数组的第n个元素表示当前这个城市是否和第1个城市相连。这样就可以在询问两个城市是否相连时快速求出和了，但是需要求两次，若顺时针可以到达或者是逆时针可以到达，则是可以到达的，否则是不可以到达的。

参考程序:

#include< stdio.h>
#include<string.h>
int c[100001],ma[100001];
int lowbit(int t)
//位运算
return t&(-t);
void insert(int k,int d,int max)
while(k<=max)
c[k]+=d;
k= k+lowbit (k);
int getsum(int k)
//快速求和
int t=0;
while(k>0)
t+=c[k];
k-=lowbit(k);
1
return t;
int main()
int i,j,k,t,n;while(scanf("dd",&n,&k)!=EOF)memset(c,0,sizeof(c)) ;for(i=l;i<=n;i++)
insert(i,1,n);ma[i]=1;
//将 c 数组初始化
//起初任意城市间的公路都是完好的
//ma 数组记录当前城市是否和下一个城市相连
while(k--)
int a,b,f;scanf("号d%d%d",&f,&a,&b) ;if(f==0)
//若是好的公路，则毁坏;若是坏的公路，则修好
if(a>b) {
   
   t=a;a=b;b=t;}
if(b==n&&a==1)
{
   
   
if(ma[b]==1)
insert(b,-1,n);
ma[b]= 0;
else
insert(b,1,n);ma[b]= 1;
else
}
if (ma[a]==1)
insert(a,-1,n);
ma[a]= 0;
else
insert(a,1,n);
ma[a]= 1;
if(f==1)
//询问是否可以到达
if(a>b) {
   
   t=a;a=b;b=t;]int t1,t2,t3,t4;t1=getsum(a-1);t2=getsum(b-1);
int flag=0;
//判断顺时针是否可以到达if(t2-t1==b-a)
flag=1;
printf("YES\n");
if(!flag)
//判断逆时针是否可以到达
t3=getsum(n)-t2;if(t3+t1==n-b+a)printf("YES\n");flag=1;
if(!flag)
printf("NO\n");