http://acm.hrbeu.edu.cn/index.php?act=problem&id=1001&cid=19 人工湖的公路

  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);
                else
                    Updata(1, x, y);
            }
            else
            {
                bool a = Query(1, x, y) | (Query(1, 1, x) & Query(1, y, n+1));
                if( a )
                    puts("YES");
                else
                    puts("NO");
            }
        }
    }

return 0;
}