In this HackerRank Two Array Problem solution, we are given two arrays of N integers. we need to perform some modification operations on that.
Problem solution in Java Programming.
import java.io.*;
import java.util.*;
public class Solution {
static class Vec {
double x, y;
Vec() {
}
Vec(double x, double y) {
this.x = x;
this.y = y;
}
Vec add(Vec q) {
return new Vec(x + q.x, y + q.y);
}
Vec minus(Vec q) {
return new Vec(x - q.x, y - q.y);
}
Vec mult(double t) {
return new Vec(x * t, y * t);
}
Vec div(double t) {
return new Vec(x / t, y / t);
}
double mult(Vec q) {
return x * q.x + y * q.y;
}
double modulo(Vec q) {
return x * q.y - y * q.x;
}
}
static final int N = 100000;
static final int V = (N + 2) * 2;
static Vec[] a;
static double hypot(double x, double y) {
return Math.sqrt(x * x + y * y);
}
static double abs(Vec p) {
return hypot(p.x, p.y);
}
static class Circle {
double x, y, r;
Circle(double x, double y, double r) {
this.x = x;
this.y = y;
this.r = r;
}
Circle(Vec a, double r) {
this.x = a.x;
this.y = a.y;
this.r = r;
}
}
static boolean inCircle(Circle c, Vec a) {
return hypot(a.x - c.x, a.y - c.y) <= c.r;
}
static Vec circumcenter(Vec p, Vec q, Vec r) {
Vec a = p.minus(r);
Vec b = q.minus(r);
Vec c = new Vec(a.mult(p.add(r)) / 2, b.mult(q.add(r)) / 2);
Vec x = new Vec(a.x, b.x);
Vec tmp = new Vec(c.modulo(new Vec(a.y, b.y)), x.modulo(c));
return tmp.div(a.modulo(b));
}
static Circle smallestEnclosingCircle(int n) {
Circle C = new Circle(0, 0, -1);
for (int i = 0; i < n; i++) {
if (!inCircle(C, a[i])) {
C = new Circle(a[i], 0);
for (int j = 0; j < i; j++) {
if (!inCircle(C, a[j])) {
C = new Circle((a[i].add(a[j])).div(2), abs(a[i].minus(a[j])) / 2);
for (int k = 0; k < j; k++) {
if (!inCircle(C, a[k])) {
Vec o = circumcenter(a[i], a[j], a[k]);
C = new Circle(o, abs(o.minus(a[k])));
}
}
}
}
}
}
return C;
}
static int[] y = new int[N];
static int ny;
static class Node {
boolean flp;
Node l, r;
int key, size;
void init(int k, int s) {
flp = false;
key = k;
size = s;
l = r = nodeNull;
}
int cmp(int k) {
if (l.size == k) {
return -1;
}
return l.size < k ? 1 : 0;
}
void mconcat() {
size = l.size + 1 + r.size;
}
void untag() {
if (flp) {
flp = false;
l.flip();
r.flip();
}
}
void flip() {
if (this == nodeNull) {
return;
}
Node tmp = l;
l = r;
r = tmp;
flp = !flp;
}
}
static Node[] pool = new Node[V];
static int allo = 0;
static Node nodeNull = new Node();
static Node splay(Node x, int k) {
Node lspine = nodeNull;
Node rspine = nodeNull;
for (;;) {
x.untag();
if (x.l.size == k) {
break;
}
if (x.l.size < k) {
k -= x.l.size + 1;
Node y = x.r;
y.untag();
if (x.r.cmp(k) == 1) {
k -= x.r.l.size + 1;
x.r = y.l;
y.l = x;
x.mconcat();
x = y.r;
y.r = lspine;
lspine = y;
} else {
x.r = lspine;
lspine = x;
x = y;
}
} else {
Node y = x.l;
y.untag();
if (x.l.cmp(k) == 0) {
x.l = y.r;
y.r = x;
x.mconcat();
x = y.l;
y.l = rspine;
rspine = y;
} else {
x.l = rspine;
rspine = x;
x = y;
}
}
}
{
Node z = x.l;
while (lspine != nodeNull) {
Node y = lspine.r;
lspine.r = z;
lspine.mconcat();
z = lspine;
lspine = y;
}
x.l = z;
}
{
Node z = x.r;
while (rspine != nodeNull) {
Node y = rspine.l;
rspine.l = z;
rspine.mconcat();
z = rspine;
rspine = y;
}
x.r = z;
}
x.mconcat();
return x;
}
static Node range(Node rt, int L, int R) {
rt = splay(rt, L - 1);
rt.r = splay(rt.r, R - L);
return rt;
}
static void inorder(Node rt, int d) {
if (rt != nodeNull) {
rt.untag();
inorder(rt.l, d + 1);
y[ny++] = rt.key;
inorder(rt.r, d + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
for (int i = 0; i < pool.length; i++) {
pool[i] = new Node();
}
a = new Vec[n];
for (int i = 0; i < a.length; i++) {
a[i] = new Vec();
}
Node[] rt = { pool[allo++], pool[allo++] };
nodeNull.init(0, 0);
for (int d = 0; d < 2; d++) {
rt[d].init(-1, 1);
st = new StringTokenizer(br.readLine());
for (int i = 0; i <= n; i++) {
Node node = pool[allo];
if (i < n) {
int item = Integer.parseInt(st.nextToken());
node.init(item, i + 2);
} else {
node.init(-1, i + 2);
}
node.l = rt[d];
rt[d] = pool[allo++];
}
}
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int query = Integer.parseInt(st.nextToken());
int l0, r0, id;
Node p = null, q = null;
switch (query) {
case 1:
id = Integer.parseInt(st.nextToken());
l0 = Integer.parseInt(st.nextToken());
r0 = Integer.parseInt(st.nextToken());
rt[id] = range(rt[id], l0, r0 + 1);
rt[id].r.l.flip();
break;
case 2:
id = Integer.parseInt(st.nextToken());
l0 = Integer.parseInt(st.nextToken());
r0 = Integer.parseInt(st.nextToken());
int l1 = Integer.parseInt(st.nextToken());
int r1 = Integer.parseInt(st.nextToken());
if (r0 + 1 == l1) {
rt[id] = range(rt[id], l0, r0 + 1);
rt[id].r.l.flip();
rt[id] = range(rt[id], l1, r1 + 1);
rt[id].r.l.flip();
rt[id] = range(rt[id], l0, r1 + 1);
rt[id].r.l.flip();
} else {
rt[id] = range(rt[id], l1, r1 + 1);
q = rt[id].r.l;
rt[id].r.l = nodeNull;
rt[id].r.mconcat();
rt[id].mconcat();
rt[id] = range(rt[id], l0, r0 + 1);
p = rt[id].r.l;
rt[id].r.l = q;
rt[id].r.mconcat();
rt[id].mconcat();
int s = l1 + (r1 - r0) - (l1 - l0);
rt[id] = range(rt[id], s, s);
rt[id].r.l = p;
rt[id].r.mconcat();
rt[id].mconcat();
}
break;
case 3:
l0 = Integer.parseInt(st.nextToken());
r0 = Integer.parseInt(st.nextToken());
rt[0] = range(rt[0], l0, r0 + 1);
p = rt[0].r.l;
rt[1] = range(rt[1], l0, r0 + 1);
q = rt[1].r.l;
rt[0].r.l = q;
rt[0].r.mconcat();
rt[0].mconcat();
rt[1].r.l = p;
rt[1].r.mconcat();
rt[1].mconcat();
break;
case 4:
l0 = Integer.parseInt(st.nextToken());
r0 = Integer.parseInt(st.nextToken());
ny = 0;
rt[0] = range(rt[0], l0, r0 + 1);
p = rt[0].r.l;
inorder(p, 0);
id = ny;
for (int i = 0; i < id; i++) {
a[i].x = y[i];
}
ny = 0;
rt[1] = range(rt[1], l0, r0 + 1);
q = rt[1].r.l;
inorder(q, 0);
for (int i = 0; i < id; i++) {
a[i].y = y[i];
}
double result = smallestEnclosingCircle(id).r;
bw.write(String.format("%.2fn", result));
break;
default:
break;
}
}
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++ programming.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
#define MAXN 200005
#define kt root->ch[1]->ch[0]
const int inf = 100000;
struct Node
{
Node *ch[2],*pre;
int sz,key,rev;
};
class Splay
{
public:
void init()
{
cnt=0;
top=0;
nill=node;
nill->sz=0;
root=new_node(nill,-inf);
root->ch[1]=new_node(root,-inf);
up(root);
}
void insert(int pos,int num[],int l,int r)
{
Node *x=find_k(pos),*y=find_k(pos+1);
splay(x,nill);
splay(y,root);
kt=make_tree(root->ch[1],num,l,r);
up(root->ch[1]);
up(root);
}
void reverse(int pos,int n)
{
Node *x=find_k(pos-1),*y=find_k(pos+n);
splay(x,nill);
splay(y,root);
kt->rev^=1;
up(root->ch[1]);
up(root);
}
void cut(int pos1, int n1, int pos2, int n2) {
Node *x = find_k(pos1 - 1), *y = find_k(pos1 + n1);
splay(x, nill);
splay(y, root);
Node *c1 = kt;
kt = nill;
up(root->ch[1]);
up(root);
x = find_k(pos2 - n1 - 1);
y = find_k(pos2 - n1 + n2);
splay(x, nill);
splay(y, root);
Node *c2 = kt;
kt = c1;
c1->pre = root->ch[1];
up(root->ch[1]);
up(root);
x = find_k(pos1 - 1);
y = find_k(pos1);
splay(x, nill);
splay(y, root);
kt = c2;
c2->pre = root->ch[1];
up(root->ch[1]);
up(root);
}
void takeNum(int *a, int pos, int n) {
Node *x = find_k(pos - 1), *y = find_k(pos + n);
splay(x, nill);
splay(y, root);
int sz = 0;
make_array(a, sz, kt);
}
private:
int cnt,top;
Node node[MAXN],*mem[MAXN],*root,*nill,*stack[MAXN];
void up(Node *x)
{
x->sz=1+x->ch[0]->sz+x->ch[1]->sz;
}
void down(Node *x)
{
if(x->rev)
{
x->rev=0;
x->ch[0]->rev^=1;
x->ch[1]->rev^=1;
swap(x->ch[0],x->ch[1]);
}
}
Node *new_node(Node *f,int v)//??????v?????f
{
Node *x;
if(top) x=mem[--top];
else x=&node[++cnt];
x->key=v;
x->sz=1;
x->rev=0;
x->pre=f;
x->ch[0]=x->ch[1]=nill;
return x;
}
void rotate(Node *x,int f)
{
Node *y=x->pre;
//down(y);
// down(x);
y->ch[!f]=x->ch[f];
x->ch[f]->pre=y;
x->pre=y->pre;
if(y->pre!=nill) y->pre->ch[y->pre->ch[1]==y]=x;
x->ch[f]=y;
y->pre=x;
up(y);
}
void splay(Node *x,Node *to)//?x???to???
{
int tot=0;
Node *tmp=x;
while(true)
{
stack[tot++]=tmp;
tmp=tmp->pre;
if(tmp==nill) break;
}
for(int i=tot-1;i>=0;i--) down(stack[i]);
while(x->pre!=to)
{
if(x->pre->pre==to) rotate(x,x->pre->ch[0]==x);
else
{
Node *y=x->pre,*z=y->pre;
int f=(z->ch[0]==y);
if(y->ch[f]==x) rotate(x,!f),rotate(x,f);
else rotate(y,f),rotate(x,f);
}
}
up(x);
if(to==nill) root=x;
}
Node *find_k(int k)//?????k???
{
Node *x=root;
while(true)
{
down(x);
if(x->ch[0]->sz==k) return x;
if(x->ch[0]->sz>k) x=x->ch[0];
else
{
k-=(1+x->ch[0]->sz);
x=x->ch[1];
}
}
}
Node *make_tree(Node *f,int num[],int l,int r)
{
if(r<l) return nill;
int mid=(l+r)/2;
Node *x=new_node(f,num[mid]);
x->ch[0]=make_tree(x,num,l,mid-1);
x->ch[1]=make_tree(x,num,mid+1,r);
up(x);
return x;
}
void make_array(int *a, int &sz, Node *x) {
if (x == nill) return;
down(x);
make_array(a, sz, x->ch[0]);
a[sz ++] = x->key;
make_array(a, sz, x->ch[1]);
}
void clear(Node *x)//????
{
if(x==nill) return;
mem[top++]=x;
clear(x->ch[0]);
clear(x->ch[1]);
}
};
Splay splay;
int num[MAXN],n,m;
int px[MAXN], py[MAXN];
const double EPS = 1e-8;
int sgn(double x)
{
if (fabs(x)<=EPS) return 0;
return x>0?1:-1;
}
struct point
{
double x,y;
point(): x(0),y(0) {}
point(double a,double b): x(a),y(b) {}
point operator + (const point &b) const
{
return point(x+b.x,y+b.y);
}
point operator - (const point &b) const
{
return point(x-b.x,y-b.y);
}
double operator * (const point &b) const
{
return x*b.y-y*b.x;
}
double dis(const point &b) const
{
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
}
};
struct hplane
{
point s,t;
point cross (const hplane &b) const
{
point p=b.t-s;
double s1=(b.t-s)*(b.s-s);
double s2=(b.s-t)*(b.t-t);
return point((s.x*s2+t.x*s1)/(s2+s1),(s.y*s2+t.y*s1)/(s2+s1));
}
};
point p[MAXN],cen;
double calCircle(int *px, int *py, int n) {
for (int i = 0; i < n; i ++) {
p[i].x = px[i];
p[i].y = py[i];
}
srand(time(0));
random_shuffle(p, p + n);
cen = p[0];
double r = 0;
for (int i=1;i<n;i++)
if (sgn(cen.dis(p[i])-r)>0)
{
cen=p[i]; r=0;
for (int j=0;j<i;j++)
if (sgn(cen.dis(p[j])-r)>0)
{
cen=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0);
r=p[i].dis(p[j])/2.0;
for (int k=0;k<j;k++)
if (sgn(cen.dis(p[k])-r)>0)
{
hplane l1,l2;
l1.s=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0);
l1.t=l1.s+point(p[i].y-p[j].y,p[j].x-p[i].x);
l2.s=point((p[i].x+p[k].x)/2.0,(p[i].y+p[k].y)/2.0);
l2.t=l2.s+point(p[i].y-p[k].y,p[k].x-p[i].x);
cen=l1.cross(l2);
r=cen.dis(p[i]);
}
}
}
return r;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
splay.init();
for (int i = 1; i <= n * 2; i ++) {
scanf("%d", num + i);
}
splay.insert(0, num, 1, n * 2);
for (int i = 0; i < m; i ++) {
int ope;
scanf("%d", &ope);
if (ope == 1) {
int id, l, r;
scanf("%d%d%d", &id, &l, &r);
if (id == 0) {
splay.reverse(l, r - l + 1);
} else {
splay.reverse(l + n, r - l + 1);
}
} else if (ope == 2) {
int id, l1, r1, l2, r2;
scanf("%d%d%d%d%d", &id, &l1, &r1, &l2, &r2);
if (id == 0) {
splay.cut(l1, r1 - l1 + 1, l2, r2 - l2 + 1);
} else {
splay.cut(l1 + n, r1 - l1 + 1, l2 + n, r2 - l2 + 1);
}
} else if (ope == 3) {
int l, r;
scanf("%d%d", &l, &r);
splay.cut(l, r - l + 1, l + n, r - l + 1);
} else {
int l, r;
scanf("%d%d", &l, &r);
splay.takeNum(px, l, r - l + 1);
splay.takeNum(py, l + n, r - l + 1);
printf("%.2fn", calCircle(px, py, r - l + 1));
}
}
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct _ct_node{
int size;
int priority;
int value;
int reverse;
struct _ct_node *left,*right;
} ct_node;
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By);
double get_r(int x1,int y1,int x2,int y2,int x3,int y3);
int inside(int x,int y);
void sed(int idx,int r_size,int x1,int x2,
int x3,int y1,int y2,int y3);
double solve();
void tra(ct_node *root,int *A);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void push(ct_node *root);
ct_node* reverse(int A,int B,ct_node *root);
void computeTree();
int get_size(ct_node *root);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,
int*left_b,int*right_b,int left_size, int right_size);
int P[100000],st[100000],T[100000],a[100000],
b[100000],h1[100000],h2[100000],N,NN;
double pi,CX,CY,R;
ct_node poll[200000],*root[2];
int main(){
int M,x,l1,l2,r1,r2,i;
ct_node *p1,*p2,*p3,*p4,*p5,*p6;
pi=atan(1)*4;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++){
scanf("%d",&poll[i].value);
poll[i].priority=P[i]=rand();
poll[i].reverse=0;
poll[i].left=poll[i].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[0]=&poll[i];
else
if(i<T[i])
poll[T[i]].left=&poll[i];
else
poll[T[i]].right=&poll[i];
get_size(root[0]);
for(i=0;i<N;i++){
scanf("%d",&poll[i+N].value);
poll[i+N].priority=P[i]=rand();
poll[i+N].reverse=0;
poll[i+N].left=poll[i+N].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[1]=&poll[i+N];
else
if(i<T[i])
poll[T[i]+N].left=&poll[i+N];
else
poll[T[i]+N].right=&poll[i+N];
get_size(root[1]);
while(M--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d%d",&x,&l1,&r1);
root[x]=reverse(l1-1,r1-1,root[x]);
break;
case 2:
scanf("%d%d%d%d%d",&x,&l1,&r1,&l2,&r2);
split(r2-1,&p4,&p5,root[x]);
split(l2-2,&p3,&p4,p4);
split(r1-1,&p2,&p3,p3);
split(l1-2,&p1,&p2,p2);
root[x]=merge(merge(p1,p4),merge(p3,merge(p2,p5)));
break;
case 3:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
root[0]=merge(merge(p1,p5),p3);
root[1]=merge(merge(p4,p2),p6);
break;
default:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
NN=0;
tra(p2,a);
NN=0;
tra(p5,b);
root[0]=merge(merge(p1,p2),p3);
root[1]=merge(merge(p4,p5),p6);
printf("%.2lfn",solve());
break;
}
}
return 0;
}
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By){
return (Ax-Ox)*(By-Oy)-(Ay-Oy)*(Bx-Ox);
}
double get_r(int x1,int y1,int x2,
int y2,int x3,int y3){
int minx,maxx;
double s2,s3,mx2,my2,mx3,my3;
mx2=((double)(x2+x1))/2;
my2=((double)(y2+y1))/2;
mx3=((double)(x3+x1))/2;
my3=((double)(y3+y1))/2;
if(y1==y2 && y1==y3){
CY=y1;
minx=x1;
if(x2<minx)
minx=x2;
if(x3<minx)
minx=x3;
maxx=x1;
if(x2>maxx)
maxx=x2;
if(x3>maxx)
maxx=x3;
CX=((double)(minx+maxx))/2;
return ((double)(maxx-minx))/2;
}
if(y1==y2){
s3=(x1-x3)/(double)(y3-y1);
CX=mx2;
CY=s3*CX-s3*mx3+my3;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
if(y1==y3){
s2=(x1-x2)/(double)(y2-y1);
CX=mx3;
CY=s2*CX-s2*mx2+my2;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
s2=(x1-x2)/(double)(y2-y1);
s3=(x1-x3)/(double)(y3-y1);
if(s2==s3)
return 0;
CX=(mx2*s2-mx3*s3-my2+my3)/(s2-s3);
CY=(my3*s2-my2*s3+s2*s3*mx2-s2*s3*mx3)/(s2-s3);
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
int inside(int x,int y){
return sqrt((x-CX)*(x-CX)+(y-CY)*(y-CY))<=R;
}
void sed(int idx,int r_size,int x1,
int x2,int x3,int y1,int y2,int y3){
if(idx==NN || r_size==3){
if(r_size<=1){
R=0;
CX=x1;
CY=y1;
}
else if(r_size==2){
R=sqrt((x2-x1)*(double)(x2-x1)+(y2-y1)*(
double)(y2-y1))/2;
CX=((double)(x1+x2))/2;
CY=((double)(y1+y2))/2;
}
else
R=get_r(x1,y1,x2,y2,x3,y3);
return;
}
sed(idx+1,r_size,x1,x2,x3,y1,y2,y3);
if(!inside(h1[idx],h2[idx]))
switch(r_size){
case 0:
sed(idx+1,r_size+1,h1[idx],x2,x3,h2[idx],y2,y3);
break;
case 1:
sed(idx+1,r_size+1,x1,h1[idx],x3,y1,h2[idx],y3);
break;
default:
sed(idx+1,r_size+1,x1,x2,h1[idx],y1,y2,h2[idx]);
}
return;
}
double solve(){
int n=NN,k=0,t,i,j;
sort_a2(a,b,NN);
for(i=0;i<n;i++){
while(k>=2 && cross(h1[k-2],h2[k-2],h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
for(i=n-2,t=k+1;i>=0;i--){
while(k>=t && cross(h1[k-2],h2[k-2],
h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
k--;
if(k<=1)
return 0;
if(k==2)
return sqrt((h1[0]-h1[1])*(
double)(h1[0]-h1[1])+(h2[0]-h2[1])*
(double)(h2[0]-h2[1]))/2;
for(i=0;i<k;i++){
j=rand()%(k-i)+i;
t=h1[i];
h1[i]=h1[j];
h1[j]=t;
t=h2[i];
h2[i]=h2[j];
h2[j]=t;
}
NN=k;
sed(0,0,0,0,0,0,0,0);
return R;
}
void tra(ct_node *root,int *A){
if(!root)
return;
push(root);
tra(root->left,A);
A[NN++]=root->value;
tra(root->right,A);
return;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
L->right=merge(L->right,R);
recalc(L);
return L;
}
push(R);
R->left=merge(L,R->left);
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x){
split(x-curIndex-1,&t,R,root->right);
root->right=t;
recalc(root);
*L=root;
}
else{
split(x,L,&t,root->left);
root->left=t;
recalc(root);
*R=root;
}
return;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}
ct_node* reverse(int A,int B,ct_node *root){
ct_node *l,*m,*r;
split(A-1,&l,&r,root);
split(B-A,&m,&r,r);
m->reverse^=1;
return merge(merge(l,m),r);
}
void computeTree(){
int i,k,top=-1;
for(i=0;i<N;i++){
k=top;
while(k>=0 && P[st[k]]<P[i])
k--;
if(k!=-1)
T[i]=st[k];
if(k<top)
T[st[k+1]]=i;
st[++k]=i;
top=k;
}
T[st[0]]=-1;
return;
}
int get_size(ct_node *root){
if(!root)
return 0;
root->size=get_size(root->left)+get_size(root->right)+1;
return root->size;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,
int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i] < right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
