权值分块，虽然渐进复杂度不忍直视，但其极小的常数使得实际运行起来比平衡树快，大多数情况和递归版权值线段树差不多，有时甚至更快。但是被zkw线段树完虐。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define N 1000001 6 int maxv,minv=2147483647; 7 int n,op,a,m,ma[N],en,l[1100],r[1100],sumv[1100],sz,sum,num[N]; 8 bool b[N]; 9 void makeblock() 10 { 11 sz=sqrt(n); if(!sz) sz=1; r[0]=-1; 12 for(sum=1;sum*sz<n-1;sum++) 13 { 14 l[sum]=r[sum-1]+1; 15 r[sum]=sz*sum-1; 16 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 17 } 18 l[sum]=r[sum-1]+1; 19 r[sum]=n-1; 20 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 21 } 22 inline void Insert(const int &x){if(b[x]) return; b[x]=1; sumv[num[x]]++;} 23 inline void Delete(const int &x){if(!b[x]) return; b[x]=0; sumv[num[x]]--;} 24 inline int Next(const int &x) 25 { 26 for(int i=x+1;i<=r[num[x]];i++) if(b[i]) return i; 27 for(int i=num[x]+1;i<=sum;i++) if(sumv[i]) 28 for(int j=l[i];j<=r[i];j++) 29 if(b[j]) return j; 30 return -1; 31 } 32 inline int Pre(const int &x) 33 { 34 for(int i=x-1;i>=l[num[x]];i--) if(b[i]) return i; 35 for(int i=num[x]-1;i>=1;i--) if(sumv[i]) 36 for(int j=r[i];j>=l[i];j--) 37 if(b[j]) return j; 38 return -1; 39 } 40 inline int Min() 41 { 42 for(int i=1;i<=sum;i++) if(sumv[i]) 43 for(int j=l[i];j<=r[i];j++) if(b[j]) return j; 44 return -1; 45 } 46 inline int Max() 47 { 48 for(int i=sum;i>=1;i--) if(sumv[i]) 49 for(int j=r[i];j>=l[i];j--) if(b[j]) return j; 50 return -1; 51 } 52 int main() 53 { 54 scanf("%d%d",&n,&m); 55 makeblock(); 56 for(int i=1;i<=m;i++) 57 { 58 scanf("%d",&op); if(op!=3&&op!=4) scanf("%d",&a); 59 if(op==1) Insert(a); 60 else if(op==2) Delete(a); 61 else if(op==3) printf("%d ",Min()); 62 else if(op==4) printf("%d ",Max()); 63 else if(op==5) printf("%d ",Pre(a)); 64 else if(op==6) printf("%d ",Next(a)); 65 else printf("%d ",b[a] ? 1 : -1); 66 } 67 return 0; 68 }