块链 RE 一个点求助
查看原帖
块链 RE 一个点求助
519384
Link_Cut_Y楼主2023/1/12 12:18

92pts\texttt{92pts},只 RE\texttt{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;
}
2023/1/12 12:18
加载中...