EDIT: I tried this input's and I get correct answers...mf wrote:I don't know if your algorithm is correct, I'm no C++ guy.
The problem as I implemented it: with each "ADD" query add the number to your data structure. With the i-th "GET" query print the i-th smallest number in the data structure.
The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.
I use a balanced AVL
Code: Select all
#include <iostream>
using namespace std;
class AVL
{
private:
struct Node
{
int val;
Node* nleft;
Node* nright;
int hei;
int num;
Node(int v, Node* fe, Node* fd, int a, int n)
: val(v), nleft(fe), nright(fd), hei(a), num(n)
{ }
};
Node* arrel;
public:
AVL()
{
arrel = NULL;
}
void insert(int n)
{
insert(arrel, n);
}
int search(int x)
{
search(arrel, x);
}
private:
static int height(Node* p)
{
return p ? p->hei : -1;
}
static int number(Node* p)
{
return p ? p->num : 0;
}
static void update(Node* p)
{
p->hei = 1 + max(height(p->nleft), height(p->nright));
p->num = 1 + number(p->nleft) + number(p->nright);
}
static void LL(Node*& p)
{
Node* q = p;
p = p->nleft;
q->nleft = p->nright;
p->nright = q;
update(q);
update(p);
}
static void RR(Node*& p)
{
Node* q = p;
p = p->nright;
q->nright = p->nleft;
p->nleft = q;
update(q);
update(p);
}
static void LR(Node*& p)
{
RR(p->nleft);
LL(p);
}
static void RL(Node*& p)
{
LL(p->nright);
RR(p);
}
void balanceLeft(Node*& p)
{
if(height(p->nright) - height(p->nleft)==2)
{
if(height(p->nright->nleft) - height(p->nright->nright) == 1) RL(p);
else RR(p);
}
else update(p);
}
void balanceRight(Node*& p)
{
if(height(p->nleft) - height(p->nright) == 2)
{
if(height(p->nleft->nright) - height(p->nleft->nleft) == 1) LR(p);
else LL(p);
}
else update(p);
}
void insert(Node*& p, int val)
{
if(p)
{
if(val <= p->val)
{
insert(p->nleft, val);
if(height(p->nleft) - height(p->nright) == 2)
{
if(val <= p->nleft->val) LL(p);
else LR(p);
}
update(p);
}
else
{
insert(p->nright, val);
if(height(p->nright) - height(p->nleft) == 2)
{
if(val > p->nright->val) RR(p);
else RL(p);
}
update(p);
}
}
else p = new Node(val, 0, 0, 0, 1);
}
int search(Node* p, int x)
{
int aux = number(p) - number(p->nright);
if (x == aux) return p->val;
if(x > aux) return search(p->nright, x - aux);
return search(p->nleft, x);
}
};
int main()
{
int k, n, m;
scanf("%d", &k);
while (k--)
{
scanf("%d %d", &m, &n);
int A[m], u, ins = 0;
AVL T;
for (int i = 0; i < m; ++i) scanf("%d", &A[i]);
for (int i = 0; i < n; ++i)
{
scanf("%d", &u);
while (ins != u) { T.insert(A[ins]); ++ins; }
printf("%d\n", T.search(i + 1));
}
if (k) printf("\n");
}
}