2024年5月23日发(作者：欧昭懿)
}
int newnode(int val) {
cnt++;
t[cnt].val = val;
t[cnt].rnd = rand();
t[cnt].cnt = 1;
t[cnt].size = 1;
return cnt;
}
void build() {
root = newnode(-0x7fffffff);
t[root].son[1] = newnode(0x7fffffff);
upd(root);
}
void insert(int &x, int val) {
if(!x) {
x = newnode(val);
return ;
}
t[x].size++;
if(t[x].val == val)t[x].cnt++;
else {
int d = t[x].val < val;
insert(t[x].son[d], val);
if(t[x].rnd > t[t[x].son[d]].rnd) rotate(x, d);
}
}
void del(int &x, int val) {
if(!x) return ;
if(t[x].val == val) {
if(t[x].cnt > 1) {
t[x].cnt--;
t[x].size--;
return ;
}
if(!t[x].son[0] || !t[x].son[1]) {
x = t[x].son[1] + t[x].son[0];
} else {
int d = t[t[x].son[0]].rnd > t[t[x].son[1]].rnd;
rotate(x, d);
del(x, val);
}
} else {
t[x].size--;
int d = t[x].val < val;
del(t[x].son[d], val);
}
}
int rank(int x, int val) {
if(!x) return 0;
if(t[x].val == val) return t[t[x].son[0]].size + 1;
if(t[x].val > val) {
return rank(t[x].son[0], val);
} else {
return rank(t[x].son[1], val) + t[t[x].son[0]].size + t[x].cnt;
}
}
int kth(int x, int rnk) {
if(!x) return 0x7fffffff;
if(rnk <= t[t[x].son[0]].size) {
return kth(t[x].son[0], rnk);
} else {
if(rnk <= t[t[x].son[0]].size + t[x].cnt) {
return t[x].val;
} else {
return kth(t[x].son[1], rnk - t[x].cnt - t[t[x].son[0]].size);
}
}
}
int pre(int x, int val) {
if(!x) return -0x7fffffff;
if(t[x].val >= val) {
return pre(t[x].son[0], val);
} else {
return max(pre(t[x].son[1], val), t[x].val);
}
}
int nxt(int x, int val) {
if(!x) return 0x7fffffff;
if(t[x].val <= val) {
return nxt(t[x].son[1], val);
} else {
return min(nxt(t[x].son[0], val), t[x].val);
}
}
int flag = 0, change[10010], c[10010];
void order(int x) {
if(!x) return ;
if(t[x].cnt > 1) {
change[++flag] = t[x].val;
c[flag] = t[x].cnt;
t[x].cnt = 1;
}
order(t[x].son[0]);
order(t[x].son[1]);
}
void update() {
for(int i = 1; i <= flag; i++) {
if(c[i] % 2 == 0) {
del(root, change[i]);
}
for(int j = 0; j < c[i] / 2; j++) {
insert(root, change[i] + 1);
}
}
}
void order1(int x) {
if(!x) return;
order1(t[x].son[0]);
c[++flag] = t[x].val;
order1(t[x].son[1]);
}
int main() {
int n;
cin >> n;
build();
srand(time(NULL));
for(int i = 1; i <= n; i++) {
int data; cin >> data;
insert(root, data);
}
while(1) {
flag = 0;
order(root);
if(!flag) break;
update();
}
flag = -1;
memset(c, 0, sizeof(c));
order1(root);
c[0] = -1;
int ans = 0;
for(int i = 1; i < flag; i++) {
// cout << c[i] << endl;
ans += c[i] - c[i - 1] - 1;
}
cout << ans << endl;
return 0;
}
Loading [MathJax]/jax/output/HTML-CSS/
2024年5月23日发(作者：欧昭懿)
}
int newnode(int val) {
cnt++;
t[cnt].val = val;
t[cnt].rnd = rand();
t[cnt].cnt = 1;
t[cnt].size = 1;
return cnt;
}
void build() {
root = newnode(-0x7fffffff);
t[root].son[1] = newnode(0x7fffffff);
upd(root);
}
void insert(int &x, int val) {
if(!x) {
x = newnode(val);
return ;
}
t[x].size++;
if(t[x].val == val)t[x].cnt++;
else {
int d = t[x].val < val;
insert(t[x].son[d], val);
if(t[x].rnd > t[t[x].son[d]].rnd) rotate(x, d);
}
}
void del(int &x, int val) {
if(!x) return ;
if(t[x].val == val) {
if(t[x].cnt > 1) {
t[x].cnt--;
t[x].size--;
return ;
}
if(!t[x].son[0] || !t[x].son[1]) {
x = t[x].son[1] + t[x].son[0];
} else {
int d = t[t[x].son[0]].rnd > t[t[x].son[1]].rnd;
rotate(x, d);
del(x, val);
}
} else {
t[x].size--;
int d = t[x].val < val;
del(t[x].son[d], val);
}
}
int rank(int x, int val) {
if(!x) return 0;
if(t[x].val == val) return t[t[x].son[0]].size + 1;
if(t[x].val > val) {
return rank(t[x].son[0], val);
} else {
return rank(t[x].son[1], val) + t[t[x].son[0]].size + t[x].cnt;
}
}
int kth(int x, int rnk) {
if(!x) return 0x7fffffff;
if(rnk <= t[t[x].son[0]].size) {
return kth(t[x].son[0], rnk);
} else {
if(rnk <= t[t[x].son[0]].size + t[x].cnt) {
return t[x].val;
} else {
return kth(t[x].son[1], rnk - t[x].cnt - t[t[x].son[0]].size);
}
}
}
int pre(int x, int val) {
if(!x) return -0x7fffffff;
if(t[x].val >= val) {
return pre(t[x].son[0], val);
} else {
return max(pre(t[x].son[1], val), t[x].val);
}
}
int nxt(int x, int val) {
if(!x) return 0x7fffffff;
if(t[x].val <= val) {
return nxt(t[x].son[1], val);
} else {
return min(nxt(t[x].son[0], val), t[x].val);
}
}
int flag = 0, change[10010], c[10010];
void order(int x) {
if(!x) return ;
if(t[x].cnt > 1) {
change[++flag] = t[x].val;
c[flag] = t[x].cnt;
t[x].cnt = 1;
}
order(t[x].son[0]);
order(t[x].son[1]);
}
void update() {
for(int i = 1; i <= flag; i++) {
if(c[i] % 2 == 0) {
del(root, change[i]);
}
for(int j = 0; j < c[i] / 2; j++) {
insert(root, change[i] + 1);
}
}
}
void order1(int x) {
if(!x) return;
order1(t[x].son[0]);
c[++flag] = t[x].val;
order1(t[x].son[1]);
}
int main() {
int n;
cin >> n;
build();
srand(time(NULL));
for(int i = 1; i <= n; i++) {
int data; cin >> data;
insert(root, data);
}
while(1) {
flag = 0;
order(root);
if(!flag) break;
update();
}
flag = -1;
memset(c, 0, sizeof(c));
order1(root);
c[0] = -1;
int ans = 0;
for(int i = 1; i < flag; i++) {
// cout << c[i] << endl;
ans += c[i] - c[i - 1] - 1;
}
cout << ans << endl;
return 0;
}
Loading [MathJax]/jax/output/HTML-CSS/