|
|
| Admin | Sep.24.2014 at 02:27:59 PM | |
| 0 | /*
N.K.A
*/
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define in insert
struct Treap{
int y , data , size;
Treap *l;
Treap *r;
};
typedef Treap * item;
void Create( item &t, int x){
t = new Treap;
t ->l = t->r = NULL;
t->data = x;
t->y = (rand()<<16) | rand();
}
int cnt(item t){
return t == NULL ? 0 : t->size;
}
void recalc(item t){
|
| Admin | Sep.24.2014 at 02:29:19 PM | |
| 1 | void recalc(item t){
if(t!=NULL)
t->size = cnt(t->l) + cnt(t->r) + 1;
}
void split(item t,int index,item &L, item &R,int add = 0){
if( t == NULL ){
L = R = NULL;
return;
}
int cur_index = add + cnt(t->l);
if( cur_index <= index )
split( t->r ,index, t->r , R , add + cnt(t->l) + 1 ) , L = t;
else
split( t->l ,index, L , t->l , add ) , R = t;
recalc(t);
}
void merge(item &t,item L,item R){
if( L == NULL || R == NULL )
t = R!=NULL ? R : L;
else if(L->y > R->y )
merge(L->r,L->r,R) , t = L;
else
merge(R->l,L,R->l) , t = R;
recalc(t);
}
void insert(item &t,int pos , int x ){
item l , r , m;
|
| Admin | Sep.24.2014 at 02:29:43 PM | |
| 2 | item l , r , m;
split(t,pos-1,l,r);
//cout << x << endl;
Create(m,x);
merge(l,l,m);
merge(t,l,r);
}
void erase(item &t , int pos ){
item l , r , m;
split(t,pos-1,l,r);
split(r,0,m,r);
merge(t,l,r);
}
void show(item t){
if(t == NULL)return;
if(t->l!=NULL)
show(t->l);
cout << t->data <<" ";
if(t->r!=NULL)
show(t->r);
}
void to_front(item &t , int from , int to){
item m,l, r ;
split(t,from-1,l,r);
split(r,to - from,m,r);
merge(t,l,r);
merge(t,m,t);
}
main(){
srand(time(NULL));
item root = NULL;
int i,l,r,n,m;
cin >> n;
for(i = 0; n>i ; i++){
ins
|
| Admin | Sep.24.2014 at 02:30:11 PM | |
| 3 | cin >> n;
for(i = 0; n>i ; i++){
insert(root,i,i+1);
}
//show(root);
cin >> m;
for(i = 0; m>i ; i++)
{
cin >> l >> r;
l -- , r -- ;
to_front(root,l,r);
// show(root);
}
show(root);
}
|
|
|