为了更好的阅读体验,请点击这里
套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度 \(O(N \log^2 N)\)。
但是一定要记住 不可以直接使用 std::swap
交换包含带有指针的类的实例(如代码中的 Treap
类)! 原因在于在 std::swap
函数中涉及了调用析构函数来析构用于承载交换的中间变量,如果你没写析构函数释放空间还好,如果写了那么它会把中间变量中的指针(从正常指针复制)指向的空间给释放掉!
为了避免这种情况,因此写一个成员函数用于交换。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
#define IL inline
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl
template <typename T>
void _debug(const char* format, T t) {
cerr << format << '=' << t << endl;
}
template <class First, class... Rest>
void _debug(const char* format, First first, Rest... rest) {
while (*format != ',') cerr << *format++;
cerr << '=' << first << ',';
_debug(format + 1, rest...);
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& V) {
os << "[ ";
for (const auto& vv : V) os << vv << ", ";
os << ']';
return os;
}
#ifdef LOCAL
#define dbg(...) _debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif
template<typename Tp> IL void read(Tp &x) {
x=0; int f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
x *= f;
}
template<typename First, typename... Rest> IL void read(First &first, Rest&... rest) {
read(first); read(rest...);
}
int buf[42];
template<typename Tp> IL void write(Tp x) {
int p = 0;
if(x < 0) { putchar('-'); x=-x;}
if(x == 0) { putchar('0'); return;}
while(x) {
buf[++p] = x % 10;
x /= 10;
}
for(int i=p;i;i--) putchar('0' + buf[i]);
}
template<typename First, typename... Rest> IL void write(const First& first, const Rest&... rest) {
write(first); putchar(32); write(rest...);
}
template<class T> class Treap {
public:
Treap() {}
~Treap() { _clear(root);}
void insert(T x) { _insert(root, x);}
void erase(T x) { _erase(root, x);}
int rank(T x) { return _GetRankOfVal(root, x);}
T kth(int x) { assert(1 <= x && x <= root->sz); return _GetValOfRank(root, x);}
T pre(T x) { Node *ans = null; query_pre(root, x, ans); return ans->v;}
T nxt(T x) { Node *ans = null; query_nxt(root, x, ans); return ans->v;}
bool empty() { return root->sz == 0;}
int size() { return root -> sz;}
void clear() { _clear(root);}
void swap(Treap<T>& rhs) { std::swap(root, rhs.root);}
private:
struct Node {
Node *ch[2];
T v;
int sz, r, cnt;
Node() { sz = r = cnt = 0;}
Node(const T &v):v(v) { ch[0] = ch[1] = null; r=rand(); sz = cnt = 1;}
bool operator < (const Node& rhs) const { return r < rhs.r;}
int cmp(const T& x) const {
if(!(x < v || v < x)) return -1;
return v < x;
}
void upd() { sz = ch[0] -> sz + ch[1] -> sz + cnt;}
};
static Node *null;
Node *root = null;
void rotate(Node* &o, const int &d) {
Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->upd(); k->upd(); o = k;
}
void _insert(Node* &o, const T &x) {
if (o == null) { o = new Node(x); return;}
o->sz++;
int d = o->cmp(x);
if (d == -1) {o->cnt++; return;}
_insert(o->ch[d], x);
if (o->r < o->ch[d]->r) rotate(o, d^1);
o -> upd();
}
void _erase(Node* &o, const T &x) {
if (o == null) return;
int d = o->cmp(x);
if (d == -1) {
Node* u = o;
if (o->cnt > 1) {o->cnt--; o->sz--; return;}
if (o->ch[0] != null && o->ch[1] != null) {
int d2 = o->ch[0]->r > o->ch[1]->r;
rotate(o, d2); _erase(o->ch[d2], x);
}
else {
if (o->ch[0] == null) o = o->ch[1]; else o = o->ch[0];
delete u;
}
}
else _erase(o->ch[d], x);
if(o != null) o->upd();
}
int _GetRankOfVal(Node *&o, const T &x) {
if (o == null) return 1;
if (!(o->v < x || x < o->v)) return o->ch[0]->sz + 1;
else if (o->v < x) return o->ch[0]->sz + o->cnt + _GetRankOfVal(o->ch[1], x);
else return _GetRankOfVal(o->ch[0], x);
}
T _GetValOfRank(Node *&o, const int &k) {
if (o == null) return T();
if (!(o->ch[0]->sz < k)) return _GetValOfRank(o->ch[0], k);
else if(o->ch[0]->sz + o->cnt < k)
return _GetValOfRank(o->ch[1], k - o->ch[0]->sz - o->cnt);
return o->v;
}
void query_pre(Node *&o, const T &x, Node *&ans) {
if (o == null) return;
if (o->v < x) { ans = o; query_pre(o->ch[1], x, ans);}
else query_pre(o->ch[0], x, ans);
}
void query_nxt(Node *&o, const T &x, Node *&ans) {
if (o == null) return;
if (x < o->v) { ans = o; query_nxt(o->ch[0], x, ans);}
else query_nxt(o->ch[1], x, ans);
}
void _clear(Node*& o) {
if (o == null || o == NULL) return;
_clear(o -> ch[0]);
_clear(o -> ch[1]);
delete o;
return;
}
};
template<class T> typename Treap<T>::Node* Treap<T>::null = new Node();
void solve() {
int n; read(n);
vector<int> a(n);
for (int i = 0; i < n; i++) read(a[i]);
int q; read(q);
vector<Treap<pair<int, int> > > id2val(q + 1), val2id(q + 1);
for (int i = 0; i < n; i++) id2val[0].insert(mk(i, a[i]));
for (int i = 0; i < n; i++) val2id[0].insert(mk(a[i], i));
for (int i = 1; i <= q; i++) {
int op, s, x; read(op, s, x);
vector<pair<int, int> > unsolved;
if (op == 1) {
int nowsz = id2val[s].size();
if (x >= nowsz / 2) { // 删后面的
for (int j = x + 1; j <= nowsz; j++) unsolved.push_back(id2val[s].kth(j));
}
else {
for (int j = 1; j <= x; j++) unsolved.push_back(id2val[s].kth(j));
}
for (auto v : unsolved) {
id2val[i].insert(v);
id2val[s].erase(v);
val2id[i].insert(mk(v.se, v.fi));
val2id[s].erase(mk(v.se, v.fi));
}
if (x < nowsz / 2) {
id2val[s].swap(id2val[i]);
val2id[s].swap(val2id[i]);
}
}
else {
int nowsz = val2id[s].size();
int rankx = val2id[s].rank(mk(x, (int)1e9)); // > x 第一个数的 rank
if (rankx >= nowsz / 2) { // 删后面的
for (int j = rankx; j <= nowsz; j++) unsolved.push_back(val2id[s].kth(j));
}
else {
for (int j = 1; j < rankx; j++) unsolved.push_back(val2id[s].kth(j));
}
for (auto v : unsolved) {
val2id[i].insert(v);
val2id[s].erase(v);
id2val[i].insert(mk(v.se, v.fi));
id2val[s].erase(mk(v.se, v.fi));
}
if (rankx < nowsz / 2) {
id2val[s].swap(id2val[i]);
val2id[s].swap(val2id[i]);
}
}
assert(id2val[i].size() == val2id[i].size());
write(id2val[i].size()); putchar(10);
}
}
int main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
#endif
int T = 1;
// read(T);
while(T--) solve();
return 0;
}
- 题解 Beginner Generate Atcoder Contest题解beginner generate atcoder 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332