# Cod sursa(job #524619)

Utilizator Data 22 ianuarie 2011 14:18:35 Secv8 100 cpp done Arhiva de probleme 5.43 kb
``````#define _CRT_SECURE_NO_DEPRECATE

#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, b, a) for(int i = b - 1; i >= a; --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)

#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define MAX(A, B) ((A) > (B) ? (A) : (B))
#define ABS(A) ((A) < 0 ? (-(A)) : (A))
#define ALL(V) V.begin(), V.end()
#define SIZE(V) (int)V.size()
#define pb push_back
#define mp make_pair
#define EPS 1e-7
#define Pi 3.14159265358979

typedef long long Long;
typedef unsigned long long ULong;
typedef unsigned int Uint;
typedef unsigned char Uchar;
typedef vector <int> VI;
typedef pair <int, int> PI;

const int SZ = 1 << 20;

struct st
{
int y;
int cnt;
int val;
bool rev;
int left, right;
} a[SZ];

struct triple
{
int left, mid, right;
triple(int left_ = -1, int mid_ = -1, int right_ = -1): left(left_), mid(mid_), right(right_) { }
};

int sz = 0;

void fix_down(int cur)
{
if(cur == -1)
return;
if(a[cur].rev)
{
a[cur].rev = false;
if(a[cur].left != -1) a[a[cur].left].rev ^= true;
if(a[cur].right != -1) a[a[cur].right].rev ^= true;
swap(a[cur].left, a[cur].right);
}
}

int cnt(int cur)
{
return cur == -1 ? 0 : a[cur].cnt;
}

void update_cnt(int cur)
{
if(cur == -1) return;
a[cur].cnt = 1 + cnt(a[cur].left) + cnt(a[cur].right);
}

int merge(int left, int right)
{
fix_down(left), fix_down(right);
if(left == -1) return right;
if(right == -1) return left;
if(a[left].y > a[right].y)
{
a[left].right = merge(a[left].right, right);
update_cnt(left);
return left;
}
else
{
a[right].left = merge(left, a[right].left);
update_cnt(right);
return right;
}
}

PI split(int cur, int x)
{
fix_down(cur);
if(cur == -1)
return mp(-1, -1);
PI res;
if(cnt(a[cur].left) + 1 <= x)
{
res = split(a[cur].right, x - (cnt(a[cur].left) + 1));
a[cur].right = res.first;
res = mp(cur, res.second);
}
else
{
res = split(a[cur].left, x);
a[cur].left = res.second;
res = mp(res.first, cur);
}
update_cnt(cur);
return res;
}

set<int> y;
void init()
{
sz = 0;
y.clear();
}

void insert(int pos, int val)
{
if(pos < 0 || pos > cnt(head))
throw -1;
int cur = sz++;
do
{
a[cur].y = rand() * rand();
}
while(y.count(a[cur].y));
y.insert(a[cur].y);
a[cur].cnt = 1;
a[cur].val = val;
a[cur].rev = false;
a[cur].left = a[cur].right = -1;
}

void erase(int pos)
{
if(pos < 0 || pos >= cnt(head))
throw -1;
res = split(res.second, 1);
}

triple get_range(int start, int fin) // head invalid after this
{
PI p1 = split(head, fin + 1);
PI p2 = split(p1.first, start);
return triple(p2.first, p2.second, p1.second);
}

void reverse(int start, int fin)
{
triple t = get_range(start, fin);
a[t.mid].rev ^= true;
}

int val_at(int cur, int pos)
{
fix_down(cur);
if(cnt(a[cur].left) == pos)
return a[cur].val;
if(cnt(a[cur].left) > pos)
return val_at(a[cur].left, pos);
return val_at(a[cur].right, pos - (cnt(a[cur].left) + 1));
}

void get_all(int cur, VI &v)
{
fix_down(cur);
if(cur == -1) return;
get_all(a[cur].left, v);
v.pb(a[cur].val);
get_all(a[cur].right, v);
}

void erase(int start, int fin)
{
triple t = get_range(start, fin);
}

char buf[2];

int main()
{
freopen("secv8.in", "r", stdin);
freopen("secv8.out", "w", stdout);
int n;
scanf("%d%*d", &n);
init();
REP(i, n)
{
scanf("%s", buf);
if(buf[0] == 'I')
{
int pos, val;
scanf("%d%d", &pos, &val);
insert(pos - 1, val);
}
if(buf[0] == 'A')
{
int pos;
scanf("%d", &pos);
}
if(buf[0] == 'R')
{
int start, fin;
scanf("%d%d", &start, &fin);
reverse(start - 1, fin - 1);
}
if(buf[0] == 'D')
{
int start, fin;
scanf("%d%d", &start, &fin);
erase(start - 1, fin - 1);
}
}
VI v;