1 #include<iostream> 2 #define MAX 100000 3 using namespace std; 4 long A[MAX+1];//環形公路數據 5 long com[MAX+1];//樹狀數組 6 long N,M;//節點數和詢問次數 7 8 long lowbit(long x) 9 { 10 return x&(-x); 11 } 12 13 void modify(long pos,int value) 14 { 15 while(pos<=N) 16 { 17 com[pos]+=value; 18 pos+=lowbit(pos); 19 } 20 } 21 22 long query(long x) 23 { 24 long sum=0; 25 while(x>0) 26 { 27 sum+=com[x]; 28 x-=lowbit(x); 29 } 30 return sum; 31 } 32 33 void init() 34 { 35 for(long i=1;i<=N;i++) 36 { 37 com[i]=0; 38 } 39 for(long i=1;i<=N;i++) 40 { 41 modify(i,1); 42 } 43 } 44 45 void solve(long x,long y) 46 { 47 long sum1,sum2; 48 sum1=query(x); 49 sum2=query(y); 50 if(sum2-sum1==y-x) 51 { 52 cout<<"YES"<<endl; 53 return; 54 } 55 long sum3; 56 sum1=query(x); 57 sum2=query(y); 58 sum3=query(N); 59 sum2=sum3-sum2; 60 if(sum1+sum2==x+N-y) 61 { 62 cout<<"YES"<<endl; 63 } 64 else 65 { 66 cout<<"NO"<<endl; 67 } 68 } 69 70 int main() 71 { 72 while(cin>>N>>M) 73 { 74 init(); 75 for(long i=1;i<=N;i++) 76 { 77 A[i]=1; 78 } 79 int f; 80 long x,y; 81 for(long i=0;i<M;i++) 82 { 83 cin>>f>>x>>y; 84 if(x>y) 85 { 86 long temp; 87 x=temp; 88 x=y; 89 y=temp; 90 } 91 if(f==0) 92 { 93 if(x==1&&y==N) 94 { 95 if(A[y]==1) 96 { 97 modify(x,-1); 98 A[x]=0; 99 } 100 else 101 { 102 modify(x,1); 103 A[x]=1; 104 } 105 } 106 else 107 { 108 if(A[y]==1) 109 { 110 modify(y,-1); 111 A[y]=0; 112 } 113 else 114 { 115 modify(y,1); 116 A[y]=1; 117 } 118 } 119 } 120 else 121 { 122 solve(x,y); 123 } 124 } 125 } 126 return 0; 127 }

?

#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> #define MID(x,y) ( ( x + y ) >> 1 ) #define L(x) ( x << 1 ) #define R(x) ( x << 1 | 1 ) #define FOR(i,s,t) for(int i=(s); i<(t); i++) #define BUG puts("here!!!") #define STOP system("pause") #define file_r(x) freopen(x, "r", stdin) #define file_w(x) freopen(x, "w", stdout)using namespace std;const int MAX = 100010;struct Tnode{ // 一維線段樹 int l,r;bool ok; int len() { return r - l;}
int mid() { return MID(l,r);}bool in(int ll,int rr) { return l >= ll && r <= rr; }void lr(int ll,int rr){ l = ll; r = rr;} }; Tnode node[MAX<<2]; void Build(int t,int l,int r) {node[t].lr(l,r);node[t].ok = true;if( node[t].len() == 1 )return ;int mid = MID(l,r);Build(L(t),l,mid);Build(R(t),mid,r); }void Updata(int t,int l,int r) {if( node[t].in(l,r) ){node[t].ok ^= 1;return ;}if( node[t].len() == 1 ) return ;int mid = node[t].mid();if( l < mid ) Updata(L(t),l,r);if( r > mid ) Updata(R(t),l,r);node[t].ok = node[L(t)].ok & node[R(t)].ok; }bool Query(int t,int l,int r) {if( l >= r ) return true;if( node[t].in(l,r) ) return node[t].ok;if( node[t].len() == 1 ) return 0;int mid = node[t].mid();bool ans = true;if( l < mid ) ans &= Query(L(t),l,r);if( r > mid ) ans &= Query(R(t),l,r);return ans; }int main() {int n, m, x, y, op;while( ~scanf("%d%d", &n, &m) ){Build(1, 1, n+1);while( m-- ){scanf("%d%d%d", &op, &x, &y);if( x > y )swap(x, y);if( op == 0 ){if( y - x > 1 )Updata(1, y, y+1);elseUpdata(1, x, y);}else{bool a = Query(1, x, y) | (Query(1, 1, x) & Query(1, y, n+1));if( a )puts("YES");elseputs("NO");}}}return 0; }

?

轉載于:https://www.cnblogs.com/feiguo/archive/2012/05/26/2519511.html

總結

以上是生活随笔為你收集整理的http://acm.hrbeu.edu.cn/index.php?act=problemid=1001cid=19 人工湖的公路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。