Блог пользователя WIL

Автор WIL, история, 9 лет назад, По-английски

Usually, for solve problems where we have to know the number of element least that some value X, is ease use some data structure of binary search tree (like treap). But in competition is it's heavy copy this code, and usually i use for similar thing the set structure. But after some time of searching, I don't find out, how can i know for a set, the position of an element in the sorted list. Example:

//If i have in my set.
set<int>s;
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(2);
//know the sorted position of 4.

if i search with some method (**find**,**lower_bound** or upper_bound) this return an iterator of the element, but it's posible know it's sorted position.

if I use a treap, I make an function where i keep the number of element to the left and finally when i find the element, the number of elements least that X is the number of elements to the left of X in the tree. An example in my treap:

class treap {
  struct node {
    int value, key, size,cc;
    node(int v, node *n):value(v){
      c[0] = c[1] = n;
      size = 1; key = rand() - 1;
      cc=1;
    }
    void rz() {
      size = c[0]->size + c[1]->size + cc;
    }
    node*c[2];
  }*root, *null;
  void rot(node*&t, bool d) {
    node*c = t->c[d];
    t->c[d] = c->c[!d];
    c->c[!d] = t;
    t->rz(); c->rz();
    t = c;
  }
  void insert(node*&t, int x) {
    if (t == null) {
      t = new node(x, null);
      return;
    }
    if (x == t->value){
        t->cc++;t->rz();
        return;
    }
    bool d = x > t->value;
    insert(t->c[d], x);
    if (t->c[d]->key < t->key) rot(t, d);
    else t->rz();
  }
  int Upper_bound(node*&t,int x,int izq){//For know the number of element <= X
      if(t==null)return izq;
      if(x==t->value)
          return t->c[0]->size+izq+t->cc;
      bool d=x>t->value;
      if(d)return Upper_bound(t->c[d],x,izq+t->c[0]->size+t->cc);
      return Upper_bound(t->c[d],x,izq);
  }
  void Delete(node*&t, int x) {
    if (t == null) return;
    if (t->value == x) {
      if(t->cc>1){
        t->cc--;t->rz();
        return;
      }
      bool d = t->c[1]->key < t->c[0]->key;
      if (t->c[d] == null) {
        delete t; t = null;
        return;
      }
      rot(t, d); Delete(t->c[!d], x);
    } else {
      bool d = x > t->value;
      Delete(t->c[d], x);
    }
    t->rz();
  }
public:
  treap() {
    null = new node(0, 0);
    null->size = 0;
    null->key = oo;
    root = null;
  }
  void ins(int x) {
    insert(root, x);
  }
  void del(int x) {
    Delete(root, x);
  }
  int busq(int x){
      return Upper_bound(root,x,0);
  }
};

It's posible make this in a set structure???

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i think you are looking for this