平板电视求条玄关

P6136 【模板】普通平衡树（数据加强版）

JOKER_chu @ 2024-10-18 15:31:53

double 版：76 pts

#include <iostream>

#include <bits/extc++.h>

#define int long long

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using namespace std;

int n, q, ans, last;

tree<long double, null_type, less<long double>, rb_tree_tag, tree_order_statistics_node_update> t;

signed main() {
  srand(20111019 + 'Y' + 'u');
  ios :: sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for ( int i = 1, x; i <= n; ++i ) {
    cin >> x;
    t.insert(x + i * 1e-9 + (i + rand()) * 1e-15);
  }
  while (q--) {
    int op, x;
    cin >> op >> x;
    x ^= last;
    if (op == 1) {
      t.insert(x + q * 1e-9 + (q + rand()) * 1e-14);
    } else if (op == 2) {
      t.erase(t.lower_bound(x));
    } else if (op == 3) {
      ans ^= t.order_of_key(*t.lower_bound(x)) + 1;
      last = t.order_of_key(*t.lower_bound(x)) + 1;
    } else if (op == 4) {
      ans ^= (int)floor(*t.find_by_order(x - 1));
      last = (int)floor(*t.find_by_order(x - 1));
    } else if (op == 5) {
      ans ^= (int)floor(*(prev(t.lower_bound(x))));
      last = (int)floor(*(prev(t.lower_bound(x))));
    } else if (op == 6) {
      ans ^= (int)floor(*(t.lower_bound(x + 1)));
      last = (int)floor(*(t.lower_bound(x + 1)));
    }
  }
  cout << ans;
  return 0;
}

pair 版，68 pts

#include <iostream>

#include <bits/extc++.h>

#define int long long

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using namespace std;

int n, q, ans, last;

unordered_map<int, int> v;
/*
pair<int,char>x;
x.first
x.second
tot
tot++
*/
tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t;

signed main() {
  ios :: sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for ( int i = 1, x; i <= n; ++i ) {
    cin >> x;
    t.insert(make_pair(x, ++v[x]));
  }
  while (q--) {
    int op, x;
    cin >> op >> x;
    x ^= last;
    if (op == 1) {
      t.insert(make_pair(x, ++v[x]));
    } else if (op == 2) {
      t.erase(t.lower_bound(make_pair(x, 1ll)));
    } else if (op == 3) {
      ans ^= t.order_of_key(*t.lower_bound(make_pair(x, 1ll))) + 1;
      last = t.order_of_key(*t.lower_bound(make_pair(x, 1ll))) + 1;
    } else if (op == 4) {
      ans ^= (*t.find_by_order(x - 1)).first;
      last = (*t.find_by_order(x - 1)).first;
    } else if (op == 5) {
      ans ^= (*(prev(t.lower_bound(make_pair(x, 1ll))))).first;
      last = (*(prev(t.lower_bound(make_pair(x, 1ll))))).first;
    } else if (op == 6) {
      ans ^= (*(t.lower_bound(make_pair(x + 1, 1ll)))).first;
      last = (*t.lower_bound(make_pair(x + 1, 1ll))).first;
    }
  }
  cout << ans;
  return 0;
}

条出一个一关

by nr0728 @ 2024-10-18 16:04:55

@JOKER_chu 直接用 int 不好吗，AC Code:

#include <iostream>
#include <bits/extc++.h>
#define int long long
using namespace __gnu_pbds;
using namespace std;

int n, q, ans, last;

tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> t;

signed main() {
  ios :: sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for ( int i = 1, x; i <= n; ++i ) {
    cin >> x;
    t.insert(x);
  }
  while (q--) {
    int op, x;
    cin >> op >> x;
    x ^= last;
    if (op == 1) {
      t.insert(x);
    } else if (op == 2) {
      t.erase(t.upper_bound(x));
    } else if (op == 3) {
      ans ^= t.order_of_key(x) + 1;
      last = t.order_of_key(x) + 1;
    } else if (op == 4) {
      ans ^= *t.find_by_order(x - 1);
      last = *t.find_by_order(x - 1);
    } else if (op == 5) {
      ans ^= *prev(t.upper_bound(x));
      last = *prev(t.upper_bound(x));
    } else if (op == 6) {
     ans ^= *t.lower_bound(x);
     last = *t.lower_bound(x);
    }
  }
  cout << ans;
  return 0;
}

by nr0728 @ 2024-10-18 16:05:57

注意 less_equal<int>

by z_yq @ 2024-10-18 17:05:41

@JOKER_chu 菜**练(bushi

by JOKER_chu @ 2024-10-18 20:42:15

@nr0728 已关谢巨佬

|