roads are built to connect all of them, which are also numbered from 1 toconnects the village+ 1. Sometimes, for some reasons, some roads are blocked, so some villages are not connected anymore. Now, you are assigned to write a program to offer dynamic information about the connectivity.
At first, all roads are not blocked. The input will tell you the road with numberiare blocked or unblocked, or ask you if villageiandjare connected. Here two villages are connected means we can reach another village from one via some unblocked road. BTW, all the roads are bidirectional.
InputThe first line of the input contains one integerT, which indicate the number of test cases. The very first line of each case contains two integers,(where 2 ≤(where 1 ≤lines each describe one query. For each line, the first integer (0 or 1) indicates the type of the query. If the first integer is 0, there will be another integerifollowed, if the roadiis blocked at present, it will be unblocked, and vice versa. If the query type is 1, there will be two more integersfollowed, if the villageare connected at present, the answer is 1, otherwise it shall be 0.OutputFor each query of type 1, output its answer in a single lineSample Input15 101 2 50 41 4 50 21 3 41 1 30 10 21 2 41 2 5Sample Output111010一开始以为是并查集，后来想想不能实现，看了别人的思路，发现因为连接的道路很有规律，所以可以用树状数组来实现，这题主要是判断两个点是否是相连的，这里因为是环装，所以两点有两种可能的连接顺序，，一种是从小的数到大的数，另一种是从大的数到小的数。#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<vector>#include<map>#include<queue>#include<stack>#include<string>#include<algorithm>using namespace std;int b[100005],n,zhi[100006];int lowbit(int x){return x&(-x);}void update(int pos,int num){while(pos<=n){b[pos]+=num;pos+=lowbit(pos);}}int getsum(int pos){int num=0;while(pos>0){num+=b[pos];pos-=lowbit(pos);}return num;}int main(){int m,i,j,T,a,c,d;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);for(i=1;i<=n;i++){zhi[i]=1;b[i]=lowbit(i);}for(i=1;i<=m;i++){scanf("%d",&a);if(a==0){scanf("%d",&c);if(zhi[c]==1){update(c,-1);zhi[c]=0;}else {update(c,1);zhi[c]=1;}}else{scanf("%d%d",&c,&d);if(c>d)swap(c,d);if( getsum(d-1)-getsum(c-1)==d-c || getsum(n)-getsum(d-1)+getsum(c-1)==c+n-d )printf("1\n");else printf("0\n");}}}return 0;}
绊住的不仅是双脚，还有未来。
