权值线段树。。。。各种脑残错误

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define l(a) ((a)<<1) 9 #define r(a) (((a)<<1)+1) 10 #define clr(a,x) memset(a,x,sizeof(a)) 11 #define rep(i,l,r) for(int i=l;i
             
              >1); 45 } 46 void build(int a,int l,int r) 47 { 48 x[a].l=l,x[a].r=r,x[a].v=0,x[a].mx=0,x[a].mn=inf; 49 if(l==r){ 50 f[l]=a; 51 return; 52 } 53 int mid=(l+r)>>1; 54 build(l(a),l,mid); 55 build(r(a),mid+1,r); 56 } 57 int find(int k) 58 { 59 if(x[f[k]].v) return 1; 60 return -1; 61 } 62 void insert(int k) 63 { 64 if(find(k)==-1){ 65 x[f[k]].v=1; 66 x[f[k]].mx=x[f[k]].mn=k; 67 update(f[k]>>1); 68 } 69 } 70 void del(int k) 71 { 72 if(find(k)==1){ 73 x[f[k]].v=0; 74 x[f[k]].mx=0; 75 x[f[k]].mn=inf; 76 update(f[k]>>1); 77 } 78 } 79 int pre(int a,int k) 80 { 81 if(!x[a].v) return 0; 82 if(x[a].l==x[a].r) return (x[a].l
              
               >1; 84 if(mid>=k) return pre(l(a),k); 85 int ans=pre(r(a),k); 86 return (!ans)?pre(l(a),k):ans; 87 } 88 int suc(int a,int k) 89 { 90 if(!x[a].v) return 0; 91 if(x[a].l==x[a].r) return (x[a].l>k)?x[a].l:0; 92 int mid=(x[a].l+x[a].r)>>1; 93 if(k>=mid) return suc(r(a),k); 94 int ans=suc(l(a),k); 95 return (!ans)?suc(r(a),k):ans; 96 } 97 int main() 98 { 99 int n=read(),m=read();100 build(1,1,n+1);101 while(m--){102 int opt=read(),t;103 switch(opt){104 case 1:t=read();insert(++t);break;105 case 2:t=read();del(++t);break;106 case 3:printf("%d\n",(x[1].mn==inf)?-1:(x[1].mn-1));break;107 case 4:printf("%d\n",x[1].mx-1);break;108 case 5:t=read();printf("%d\n",pre(1,++t)-1);break;109 case 6:t=read();printf("%d\n",suc(1,++t)-1);break;110 case 7:t=read();printf("%d\n",find(++t));break;111 }112 }113 return 0;114 }
              
             
            
           
          
         
        
       
      

3685: 普通van Emde Boas树

Time Limit: 9 Sec  Memory Limit: 128 MB

Submit: 619  Solved: 217

[][][]

Description

设计数据结构支持:

1 x  若x不存在,插入x

2 x  若x存在,删除x

3    输出当前最小值,若不存在输出-1

4    输出当前最大值,若不存在输出-1

5 x  输出x的前驱,若不存在输出-1

6 x  输出x的后继,若不存在输出-1

7 x  若x存在,输出1,否则输出-1

Input

第一行给出n,m 表示出现数的范围和操作个数

接下来m行给出操作

n<=10^6,m<=2*10^6,0<=x<n

 

Output

 

Sample Input

10 11

1 1

1 2

1 3

7 1

7 4

2 1

3

2 3

4

5 3

6 2

Sample Output

1

-1

2

2

2

-1

HINT

 

Source

[ ][ ][ ]