第一眼看到这题，没错就拿他来做treap的练手了，然而我错了，卡treap，我哭了，写了两三次treap（），这两天几乎都在写数据结构了。后来我又可耻地看了题解，原来这道题已经给了数列中数的范围，可以写成权值线段树，当然线段树要写成zkw才更快。 最重要的是，在我看过的一个人的题解中， 他是用一个bool 数组来判断一个数是否出现过，比我们这些第一反应写treap，还要写个find，去查找这个数是否存在的高级多了，节省了不少时间，关键是还学到了，输出优化。加油吧！ 对于权值线段树的理解和应用也要加强。

这份代码3000多毫秒。

1 #include
     
        2 #include
      
         3 #define rep(i,j,k) for(int i = j; i <= k; i++)  4 using namespace std;  5    6 int tree[1<<21|1];  7 int po = 1, cnt = 0;  8 bool in[1<<20];  9   10 inline int read() 11 { 12     int s =0, t =1; char c = getchar(); 13     while( !isdigit(c) ){ 14         if( c == '-' ) t = -1; c = getchar(); 15     } 16     while( isdigit(c) ){ 17         s = s * 10 + c - '0'; c = getchar(); 18     } 19     return s * t; 20 } 21   22 void update(int t,int d) 23 { 24     for(tree[t+=po]=d, t>>=1; t; t>>=1 ){ 25         tree[t] = tree[t<<1] | tree[t<<1|1]; 26     } 27 } 28   29 int get_min(int t) 30 { 31     for(;t <= po; ) 32     { 33         if( tree[t<<1] ) t = (t<<1); 34         else t = (t<<1)+1; 35     } 36     return t-po; 37 } 38   39 int get_max(int t) 40 { 41     for(;t <= po; ){ 42         if( tree[t<<1|1] ) t = (t<<1)+1; 43         else t = t << 1; 44     } 45     return t-po; 46 } 47   48 void put(int x) 49 { 50     if( x / 10 ) put(x/10); 51     putchar(x%10+'0'); 52 } 53   54 int main() 55 { 56     int n = read(), m = read(); while( 1<
       
        < n ) po++; po = (1<
        
         >=1){ 74                     if( (t & 1) && tree[t^1] ) { 75                         t = t ^ 1; break; 76                     } 77                 } 78                 if( t == 1 ) puts("-1"); 79                 else { 80                     put(get_max(t)-1); puts(""); 81                 } 82             } 83             if( x == 6 ){ 84                 int t; 85                 for(t = y+po; t != 1; t>>=1){ 86                     if( !(t & 1) && tree[t^1] ) { 87                         t = t ^ 1; break; 88                     } 89                 } 90                 if( t == 1 ) puts("-1"); 91                 else { 92                     put(get_min(t)-1); puts(""); 93                 } 94             } 95             if( x == 7 ){ 96                 if( in[y] ) { 97                     put(1); puts(""); 98                 } 99                 else puts("-1"); 100             }101         }102         else {103             if( !cnt ) {104                 puts("-1"); continue;105             }106             if( x == 3 ){107                 put(get_min(1)-1); puts("");108             }109             else if( x == 4 ) {110                 put(get_max(1)-1); puts("");111             }112         }113     }114     return 0;115 }
        
       
      
     

 

另附这道题，我刚才突发奇想用vector写了分块，一开始由于鲁棒性不强RE了，后来改了后AC了，用时6800多毫秒，还是很快的。（其实昨天就写了vector，但由于没分块，TLE了）

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define mod 1005  6 #define rep(i,j,k) for(int i = j; i <= k; i++)  7 #define down(i,j,k) for(int i = j; i >= k; i--)  8 using namespace std;  9  10 int read() 11 { 12     int s = 0, t = 1; char c = getchar(); 13     while( !isdigit(c) ){ 14         if( c == '-' )t = -1; c = getchar(); 15     } 16     while( isdigit(c) ){ 17         s = s * 10 + c - '0'; c = getchar(); 18     } 19     return s * t; 20 }  21  22 bool in[1000006] = {
   0}; int tot = 0; 23  24 struct node{ 25 vector
         
           a; 26 int cnt; 27 node(){ 28   a.insert(a.begin(),0x7fffffff); cnt = 0; 29 } 30 } nod[1005]; 31 vector
          
            s; int cnt = 0; 32 33 void insert(int y) 34 { 35 tot++; 36 int key = y / mod; 37 if( !nod[key].cnt ) { 38 s.insert(lower_bound(s.begin(),s.end(),key),key); 39 cnt++; 40 } 41 nod[key].cnt++; 42 nod[key].a.insert(lower_bound(nod[key].a.begin(),nod[key].a.end(),y),y); 43 } 44 45 void remove(int y) 46 { 47 tot--; 48 int key = y / mod; 49 nod[key].cnt--; 50 if( !nod[key].cnt ) { 51 s.erase(lower_bound(s.begin(),s.end(),key)); 52 cnt--; 53 } 54 nod[key].a.erase(lower_bound(nod[key].a.begin(),nod[key].a.end(),y)); 55 } 56 57 void put(int x) 58 { 59 if(x / 10 ) put(x/10); 60 putchar(x%10+'0'); 61 } 62 63 int minl() 64 { 65 if( !tot ) return -1; 66 else return nod[s[0]].a[0]; 67 } 68 69 int maxl() 70 { 71 if( !tot ) return -1; 72 else return nod[s[cnt-1]].a[nod[s[cnt-1]].cnt-1]; 73 } 74 75 int pre(int y) 76 { 77 if( !tot || minl() >= y ) return -1; 78 int key = y / mod; 79 int k = lower_bound(s.begin(),s.end(),key) - s.begin(); 80 down(i,k,0){ 81 int x = s[i]; 82 int zhi = lower_bound(nod[x].a.begin(),nod[x].a.end(),y) - nod[x].a.begin(); 83 if( zhi == 0 ) continue; return nod[x].a[zhi-1]; 84 } 85 } 86 87 int suc(int y) 88 { 89 if( !tot || maxl() <= y ) return -1; 90 int key = y / mod; 91 int k = lower_bound(s.begin(),s.end(),key) -s.begin(); 92 rep(i,k,cnt-1){ 93 int x = s[i]; 94 int zhi = upper_bound(nod[x].a.begin(),nod[x].a.end(),y) - nod[x].a.begin(); 95 if( nod[x].a[zhi] != 0x7fffffff ) return nod[x].a[zhi]; 96 } 97 } 98 99 int main()100 {101 int n = read(), m = read(); s.insert(s.begin(),0x7fffffff); 102 while( m-- ){103 int x = read(), y, key;104 switch( x ){105 case 1: y = read()+1; if( !in[y] ) insert(y), in[y] = 1; break;106 case 2: y = read()+1; if( in[y] ) remove(y), in[y] = 0; break;107 case 3: key = minl(); if( key == -1 ) puts("-1"); else put(key-1), puts(""); break;108 case 4: key = maxl(); if( key == -1 ) puts("-1"); else put(key-1), puts(""); break;109 case 5: y = read()+1; key = pre(y); if( key == -1 ) puts("-1"); else put(key-1), puts(""); break;110 case 6: y = read()+1; key = suc(y); if( key == -1 ) puts("-1"); else put(key-1), puts(""); break;111 case 7: y = read()+1; if( in[y] ) put(1), puts(""); else puts("-1"); break;112 }113 }114 return 0;115 }
          
         
        
       
      
     

加油，相信自己，能行的。