setovi.cpp

#include <algorithm>

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <set>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define TRACE(x) cout << #x << " = " << (x) << endl

typedef long long llint;
const int MAXNODE = 1e5 + 123;
const int inf = 1e9;

mt19937 mt;

struct Treap {
  struct Node {
    int key;
    int l, r, p;
    mt19937::result_type rank;
    
    Node() { key = -1; l = r = p = 0; rank = mt(); }
  } data[MAXNODE];

  int key_to_ref[MAXNODE];
  int data_mem; // data[0] is a dummy

  int root;

  Treap() { data_mem = 1; clear(); }

  void clear() {
    root = data_mem++;
    Node& nov = data[root];
    nov.key = 0;
    key_to_ref[0] = root;
  }

  void set_l(int up, int down) {
    data[up].l = down;
    data[down].p = up;
  }
  void set_r(int up, int down) {
    data[up].r = down;
    data[down].p = up;
  }
  void rotate(int up, int down) {
    int p = data[up].p;

    if (data[up].l == down) {
      set_l(up, data[down].r);
      set_r(down, up);
    } else if (data[up].r == down) {
      set_r(up, data[down].l);
      set_l(down, up);
    } else assert(false);

    if (p == 0) { root = down; data[down].p = 0; }
    else if (data[p].l == up) set_l(p, down);
    else if (data[p].r == up) set_r(p, down);
    else assert(false);
  }

  void repair(int ptr) {
    while (data[ptr].p != 0 && data[ptr].rank < data[data[ptr].p].rank) {
      rotate(data[ptr].p, ptr);
    }
  }

  int insert(int key, int after) {
    int up = key_to_ref[after];
    int nov_ind = data_mem++;
    key_to_ref[key] = nov_ind;
    Node& nov = data[nov_ind];
    nov.key = key;

    if (data[up].r == 0) {
      set_r(up, nov_ind);
    } else {
      int a = 0;
      int b = data[up].r;
      while (b != 0) {
        a = b;
        b = data[b].l;
      }
      set_l(a, nov_ind);
    }     
    repair(nov_ind);
    return nov_ind;
  }

  void print_out(vector<int>& V, int ptr) {
    if (ptr == 0) return;
    print_out(V, data[ptr].l);
    V.push_back(data[ptr].key);
    print_out(V, data[ptr].r);
  }
};

struct Tournament {
  struct Node {
    set<int> all;
    map<int, int> any; // except all
  };

  int n, offset;
  vector<Node> data;

  Tournament(int n) : n(n) {
    for (offset = 1; offset < n; offset *= 2);
    data.resize(offset*2);
  }

  int L, R, Val;

  int down_query(int x, int xl, int xr) {
    if (R <= xl || xr <= L) return +inf;
    if (L <= xl && xr <= R) {
      int ret = +inf;
      if (!data[x].all.empty()) ret = min(ret, *data[x].all.begin());
      if (!data[x].any.empty()) {
        assert(data[x].any.begin()->second > 0); /// !!!
        ret = min(ret, data[x].any.begin()->first);
      }
      return ret;
    }
    int ret = min(down_query(2*x, xl, (xl+xr)/2),
                  down_query(2*x+1, (xl+xr)/2, xr));
    if (!data[x].all.empty()) ret = min(ret, *data[x].all.begin());
    return ret;
  }

  int query(int l, int r) {
    L = l; R = r;
    return down_query(1, 0, offset);
  }

  void erase_all(int x) {
    assert(x < 2*offset);
    if (data[x].all.erase(Val)) return; // sve smo ih makli odavde
    if (data[x].any.erase(Val) == 0) return; // nema ga ovdje1
    erase_all(2*x);
    erase_all(2*x+1);
  }

  void down_insert(int x, int xl, int xr, int sz) {
    if (R <= xl || xr <= L) return;
    if (L <= xl && xr <= R) {
      data[x].all.insert(Val); // ne bi smjelo nista biti ispod toga
      assert(data[x].any.count(Val) == 0); // !!!
      return;
    }

    int inter = min(xr, R) - max(xl, L);
    if ((data[x].any[Val] += inter) == sz) {
      data[x].any.erase(Val);
      data[x].all.insert(Val);
      erase_all(2*x); // x nije list
      erase_all(2*x+1);
      //      if (x == 112 && data[2*x+1].all.count(Val)
    } else {
      down_insert(2*x, xl, (xl+xr)/2, sz / 2);
      down_insert(2*x+1, (xl+xr)/2, xr, sz / 2);
    }
  }

  void insert(int l, int r, int val) {
    L = l; R = r; Val = val;
    down_insert(1, 0, offset, offset);
  }

  void down_erase(int x, int xl, int xr, int sz) {
    if (R <= xl || xr <= L) return;
    if (L <= xl && xr <= R) {
      assert(data[x].all.count(Val) == 1);
      data[x].all.erase(Val);
      return;
    }
    int inter = min(xr, R) - max(xl, L);

    if (data[x].all.count(Val)) { // all -> any
      assert(sz - inter > 0);
      data[x].any[Val] = sz - inter;
      data[x].all.erase(Val);

      data[2*x].all.insert(Val);
      data[2*x+1].all.insert(Val);

    } else {
      assert(data[x].any[Val] >= inter); // !!!
      if ((data[x].any[Val] -= inter) == 0) {
        data[x].any.erase(Val);
      }
    }

    down_erase(2*x, xl, (xl+xr)/2, sz / 2);
    down_erase(2*x+1, (xl+xr)/2, xr, sz / 2);
  }


  void erase(int l, int r, int val) {
    L = l; R = r; Val = val;
    down_erase(1, 0, offset, offset);
  }

  void test_tree() { test_tree(1, offset); }

  map<int, int> test_tree(int x, int sz) {
    map<int, int> ret;

    if (sz > 1) {
      map<int, int> A = test_tree(2*x, sz/2);
      map<int, int> B = test_tree(2*x+1, sz/2);
      for (auto p : A) ret[p.first] += p.second;
      for (auto p : B) ret[p.first] += p.second;
      // printf("x = %d sz = %d\n", x, sz);
      // printf("A = "); for (auto p : A) printf("(%d,%d) ", p.first, p.second); putchar('\n');
      // printf("B = "); for (auto p : B) printf("(%d,%d) ", p.first, p.second); putchar('\n');
      // printf("ALL = "); for (auto p : data[x].all) printf("%d ", p); putchar('\n');
      // printf("ret = "); for (auto p : ret) printf("(%d,%d) ", p.first, p.second); putchar('\n');
      // printf("any = "); for (auto p : data[x].any) printf("(%d,%d) ", p.first, p.second); putchar('\n');

      for (auto it = ret.begin(); it != ret.end(); ) {
        if (it->second == sz) {
          assert(false);
        } else {
          ++it;
        }
      }
      for (auto val : data[x].all) {
        assert(data[x].any.count(val) == 0);
        assert(ret.count(val) == 0);
      }
      assert(ret == data[x].any);
      for (auto val : data[x].all) ret[val] += sz;
    } else {
      // printf("x = %d sz = %d\n", x, sz);
      // printf("all = "); for (auto p : data[x].all) printf("%d ", p); putchar('\n');
      // printf("any = "); for (auto p : data[x].any) printf("(%d,%d) ", p.first, p.second); putchar('\n');
      // TRACE(offset);
      assert(data[x].any.empty());
      for (int val : data[x].all) ret[val] = sz;
    }

    return ret;
  }
};

int main_tour() {
// int main() {
  mt19937 mt;

  const int n = 200;
  const int maxval = 2;
  int inset[maxval][n] = {{0}};
  Tournament Tset(n);
  
  REP(iter, 123123) {
    int val = mt() % maxval;
    char c = mt() % 2 ? 'I' : 'E';
    int c_set = (c == 'I') ? 1 : 0;
    
    vector<pair<int, int> > intervals;
    int first = -1;
    REP(i, n) {
      if (first == -1 && inset[val][i] != c_set) first = i;
      if (first != -1 && (i+1 == n || inset[val][i+1] == c_set)) {
        intervals.push_back(make_pair(first, i+1));
        first = -1;
      }
    }

    if (intervals.size() == 0) { puts("PASS"); continue; }
    pair<int, int> p = intervals[mt() % intervals.size()];
    int L = mt() % (p.second-p.first) + p.first; // [0, 2)
    int R = mt() % (p.second-p.first) + p.first;
    if (L > R) swap(L, R);
    p.first = L; p.second = R+1;

    printf("%c %d [%d, %d)\n", c, val, p.first, p.second);
    if (c == 'I') Tset.insert(p.first, p.second, val);
    else Tset.erase(p.first, p.second, val);

    REP(i, p.second-p.first) {
      assert(inset[val][p.first+i] == (c_set^1));
      inset[val][p.first+i] = c_set;
    }
    Tset.test_tree();

    // queryji
    {
      int L = mt() % n;
      int R = mt() % n;
      if (L > R) swap(R, L); ++R;
      int brute = +inf;
      for (int i = L; i < R; ++i) REP(j, maxval) if (inset[j][i]) brute = min(brute, j);
      int ret = Tset.query(L, R);
      printf("[%d, %d) brute = %d ret = %d\n", L, R, brute, ret);
      assert(brute == ret);
    }
  }

  return 0;
}

int main_intervali() {
  //int main() {
  const int n = 2000;

  bool used[n]; memset(used, 0, sizeof used);
  map<int, set<pair<int, char> > > int_to_S;

  REP(iter, 20000) {
    char c = mt() % 2 ? 'I' : 'E';
    int x; for (; used[x = mt()%n]; );
    int val = mt() % 1;

    auto &S = int_to_S[val];
    auto it = S.insert(make_pair(x, c)).first;

    char prije = 'E';
    if (it != S.begin()) {
      --it;
      prije = it->second;
      ++it;
    }

    int poslije_pos = n;
    ++it;
    if (it != S.end()) {
      poslije_pos = it->first;
    }
    --it;

    printf("%c %d %d\n", c, x, val);

    if (c != prije) {
      printf("--> %c [%d, %d)\n", c, x, poslije_pos);
    }
  }

  return 0;
}

//int main(void)
int main_order()
{
  vector<int> V = {0};
  Treap orderT;

  mt19937 mt;
  REP(iter, 12312) {
    int key = iter + 1;
    int after = mt() % (iter+1);
    orderT.insert(key, after);
    V.insert(find(V.begin(), V.end(), after) + 1, key);

    vector<int> order;
    orderT.print_out(order, orderT.root);

    assert(V == order);
  }

  return 0;
}

//int main_all() {
int main() {
  const int MAXOPER = 1e5 + 123;

  int n_oper; scanf("%d", &n_oper);
  Treap order;
  
  char inpC[MAXOPER];
  int inpVal[MAXOPER];

  REP(iter, n_oper) {
    char c; int after; scanf(" %c %d", &c, &after);
    inpC[iter] = c;
    if (c == 'I' || c == 'E') {
      scanf("%d", inpVal+iter);
    }
    order.insert(iter+1, after);
  }

  vector<int> orderV; order.print_out(orderV, order.root);
  static int event_to_pos[MAXOPER];
  REP(i, (int)orderV.size()) {
    event_to_pos[orderV[i]] = i;
  }

  map<int, set<pair<int, char> > > int_to_S;
  Tournament Tset(orderV.size());

  REP(iter, n_oper) {
    char c = inpC[iter];
    int val = inpVal[iter];
    int x = event_to_pos[iter+1];

    if (c == 'I' || c == 'E') {
      auto &S = int_to_S[val];
      auto it = S.insert(make_pair(x, c)).first;

      char prije = 'E';
      if (it != S.begin()) {
        --it;
        prije = it->second;
        ++it;
      }

      int poslije_pos = (int)orderV.size();
      ++it;
      if (it != S.end()) {
        poslije_pos = it->first;
      }
      --it;

      if (c != prije) {
        if (c == 'I') {
          Tset.insert(x, poslije_pos, val);
        } else if (c == 'E') {
          Tset.erase(x, poslije_pos, val);
        }
      }
    } else {
      int ret = Tset.query(0, x);
      if (ret >= inf) printf("empty\n");
      else printf("%d\n", ret);
    }

  }

  return 0;
}