首页 > 代码库 > BZOJ 3685 普通van Emde Boas树 zkw线段树
BZOJ 3685 普通van Emde Boas树 zkw线段树
题目大意:基本是一颗平衡树的基本操作。
思路:本来是Treap的题,但是为了体现出vEB树的独特用处,所以就比较卡时间。权值线段树的常数会小一点,但是还是会T,所以就只能用zkw来水过了。
只需要在求最大值最小值里面好好考虑一下,剩下就没什么好说的了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 #define LEFT (pos << 1) #define RIGHT (pos << 1|1) using namespace std; int range,asks,M; int tree[MAX << 2]; inline void Modify(int pos,int c) { tree[pos] += c; for(; pos; pos >>= 1) tree[pos] += c; } inline int GetMin(int pos) { if(!tree[pos]) return 0; while(pos <= M) { if(tree[LEFT]) pos = LEFT; else pos = RIGHT; } return pos - M; } inline int GetMax(int pos) { if(!tree[pos]) return 0; while(pos <= M) { if(tree[RIGHT]) pos = RIGHT; else pos = LEFT; } return pos - M; } inline int GetPred(int x) { int pos = x + M; while(1) { if(pos == 1) return 0; if(pos&1 && tree[pos^1]) return GetMax(pos^1); pos >>= 1; } return 0; } inline int GetSucc(int x) { int pos = x + M; while(1) { if(pos == 1) return 0; if(!(pos&1) && tree[pos^1]) return GetMin(pos^1); pos >>= 1; } return 0; } int main() { cin >> range >> asks; for(M = 1; M <= range; M <<= 1); for(int x,flag,i = 1; i <= asks; ++i) { scanf("%d",&flag); if(flag == 1) { scanf("%d",&x); ++x; if(!tree[M + x]) Modify(M + x,1); } else if(flag == 2) { scanf("%d",&x); ++x; if(tree[M + x]) Modify(M + x,-1); } else if(flag == 3) printf("%d\n",GetMin(1) - 1); else if(flag == 4) printf("%d\n",GetMax(1) - 1); else if(flag == 5) { scanf("%d",&x); ++x; printf("%d\n",GetPred(x) - 1); } else if(flag == 6) { scanf("%d",&x); ++x; printf("%d\n",GetSucc(x) - 1); } else { scanf("%d",&x); ++x; printf("%d\n",tree[x + M] ? 1:-1); } } return 0; }
BZOJ 3685 普通van Emde Boas树 zkw线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。