92pts,只 RE 了一个点。
指针写的,求调(代码有注释)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )
using namespace std;
const int INF = 1e9;
int n, S;
struct node { // 构建块状链表类
node *next, *pre;
vector<int> v;
node() { next = pre = NULL; }
void insert(int x) { v.emplace_back(x); }
int vsize() { return v.size(); }
int back() { return v[v.size() - 1]; }
int front() { return v[0]; }
vector<int>::iterator vbegin() { return v.begin(); }
vector<int>::iterator vend() { return v.end(); }
vector<int>::iterator lower(int x) { return lower_bound(v.begin(), v.end(), x); }
vector<int>::iterator upper(int x) { return upper_bound(v.begin(), v.end(), x); }
}*head;
node *find(int x) { // 找到 x 所在块
node *now = head;
if (!(now -> vsize())) return now;
while (now -> back() < x && now -> next) now = now -> next;
return now;
}
void split(node *p) { // 将大块分裂成两个小块
node *q = new node();
q -> next = p -> next; if (q -> next) q -> next -> pre = q;
p -> next = q, q -> pre = p;
rop(i, S, p -> vsize()) q -> insert((p -> v)[i]);
(p -> v).erase(p -> vbegin() + S, p -> vend());
}
void insert(int x) { // 插入操作
node *p = find(x); p -> insert(x);
sort(p -> vbegin(), p -> vend());
if (p -> vsize() >= 2 * S) split(p);
}
void remove(int x) { // 移除数 x
node *p = find(x); // 找到 x 的位置
(p -> v).erase(p -> lower(x));
if (p -> vsize() == 0) { // 如果当前块空了
if (p == head) { // 如果是头结点,更新头结点
head = p -> next, head -> pre = NULL;
return;
}
// 更新与下一个节点的关系
p -> pre -> next = p -> next;
p -> next -> pre = p -> pre;
p -> next = p -> pre = NULL;
}
}
int get_rank(int x) { // 根据权值找排名
int cnt = 0;
for (node *now = head; now; now = now -> next) {
if (now -> back() >= x) {
cnt += (now -> lower(x)) - (now -> vbegin()); return cnt + 1;
}
else cnt += now -> vsize();
}
return cnt + 1;
}
int get_kth(int k) { // 根据排名找权值
int cnt = 0;
for (node *now = head; now; now = now -> next) {
if (cnt + now -> vsize() < k) {
cnt += now -> vsize(); continue;
}
return (now -> v)[k - cnt - 1];
}
}
int get_pre(int x) { // 找前驱
node *p = find(x);
if (p -> front() >= x) return p -> pre -> back();
return *((p -> lower(x)) - 1);
}
int get_next(int x) { // 找后继
node *p = find(x);
if (p -> back() == x) return *(p -> next -> upper(x));
return *(p -> upper(x));
}
int main() {
scanf("%d", &n);
S = (int)sqrt(n); // 块长
head = new node();
while (n -- ) {
int op, x;
scanf("%d%d", &op, &x);
if (op == 1) insert(x);
if (op == 2) remove(x);
if (op == 3) printf("%d\n", get_rank(x));
if (op == 4) printf("%d\n", get_kth(x));
if (op == 5) printf("%d\n", get_pre(x));
if (op == 6) printf("%d\n", get_next(x));
}
return 0;
}