Two Array Problem
Problem Statement :
In this problem you operate on two arrays of integers. We will call them the and the respectively. Your goal is just to maintain them under the modification operations, such as: 1 : Reverse the subarray of the array, starting at the number, ending at the number, inclusively; 2 : Swap two consecutive fragments of the array, the first is from the number to the , the second is from the number to the ; 3 : Swap the piece that starts at the number and end at the one between the and the array; 4 : We consider only the piece from the number to the one. The numbers in the array are -coordinates of some set of points and the numbers in the array are -coordinates of them. For the obtained set of points we would like to place such a circle on a plane that would contain all the points in it and would have the minimal radius. Find this minimal radius. Input Format The first line of input contains two space separated integers and denoting the number of integers in arrays and the number of queries respectively. The second line contains space separated integers: the initial elements of the array. The third line contains space separated integers: the initial elements of the array. Then there are lines containing queries in the format listed above. Output Format For each type-4 query output the sought minimal radius with exactly two symbols after the decimal point precision. Constraints 1 <= N, M <= 10^5
Solution :
Solution in C :
In C++ :
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
void RI() {}
template<typename... T>
void RI( int& head, T&... tail ) {
scanf("%d",&head);
RI(tail...);
}
// }}}
const int INF=0x7FFFFFFF;
const int N=400010;
const double eps=1e-6;
struct P { double x,y; } p[N],q[3];
double dis2( P a, P b ) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); }
P operator -( P a, P b ) { return (P){a.x-b.x,a.y-b.y}; }
P operator +( P a, P b ) { return (P){a.x+b.x,a.y+b.y}; }
P operator /( P a, double b ) { return (P){a.x/b,a.y/b}; }
double abs2( P a ) { return a.x*a.x+a.y*a.y; }
double dot( P a, P b ) { return a.x*b.x+a.y*b.y; }
double X( P a, P b ) { return a.x*b.y-a.y*b.x; }
double X( P a, P b, P c ) { return X(b-a,c-a); }
struct C {
P o; double r2;
C() { o.x=o.y=r2=0; }
C( P a ) { o=a; r2=0; }
C( P a, P b ) { o=(a+b)/2; r2=dis2(o,a); }
C( P a, P b, P c ) {
double i,j,k,A=2*X(a,b,c)*X(a,b,c);
i=abs2(b-c)*dot(a-b,a-c);
j=abs2(a-c)*dot(b-a,b-c);
k=abs2(a-b)*dot(c-a,c-b);
o.x=(i*a.x+j*b.x+k*c.x)/A;
o.y=(i*a.y+j*b.y+k*c.y)/A;
r2=dis2(o,a);
}
bool cover( P a ) { return dis2(o,a)<=r2+eps; }
};
C MEC( int n, int m ) {
C mec;
if ( m==1 ) mec=C(q[0]);
else if ( m==2 ) mec=C(q[0],q[1]);
else if ( m==3 ) return C(q[0],q[1],q[2]);
for ( int i=0; i<n; i++ )
if ( !mec.cover(p[i]) ) {
q[m]=p[i];
mec=MEC(i,m+1);
}
return mec;
}
int my_rand() {
static int seed;
return seed=seed*1103515245+12345;
}
struct Treap {
static Treap mem[N],*pmem;
Treap *l,*r;
int rnd,size,val;
bool rev;
Treap() {}
Treap( int _val ):l(NULL),r(NULL),rnd(rand()),size(1),val(_val),rev(false) {}
} Treap::mem[N],*Treap::pmem=Treap::mem;
inline int size( Treap *t ) { return t?t->size:0; }
inline void push( Treap *t ) {
if ( !t ) return;
if ( t->rev ) {
if ( t->l ) t->l->rev^=1;
if ( t->r ) t->r->rev^=1;
swap(t->l,t->r);
t->rev=false;
}
}
inline void pull( Treap *t ) {
if ( !t ) return;
t->size=size(t->l)+size(t->r)+1;
}
Treap* merge( Treap *a, Treap *b ) {
if ( !a || !b ) return a?a:b;
if ( a->rnd < b->rnd ) {
push(a);
a->r=merge(a->r,b);
pull(a);
return a;
} else {
push(b);
b->l=merge(a,b->l);
pull(b);
return b;
}
}
void split( Treap *t, int k, Treap *&a, Treap *&b ) {
push(t);
if ( !t ) a=b=NULL;
else if ( k<=size(t->l) ) {
b=t;
split(t->l,k,a,b->l);
pull(b);
} else {
a=t;
split(t->r,k-size(t->l)-1,a->r,b);
pull(a);
}
}
void go( Treap *t, vector<int> &v ) {
if ( !t ) return;
push(t);
go(t->l,v);
v.PB(t->val);
go(t->r,v);
}
Treap* input( int n ) {
Treap *t=NULL;
REP1(i,1,n) {
int x;
RI(x);
t=merge(t,new (Treap::pmem++) Treap(x));
}
return t;
}
Treap *t[2];
int main() {
srand(time(0)^getpid()^514514514);
int n,m;
RI(n,m);
REP(i,2) t[i]=input(n);
while ( m-- ) {
int op;
RI(op);
if ( op==1 ) {
int id,l,r;
RI(id,l,r);
Treap *tl,*tr;
split(t[id],l-1,tl,t[id]);
split(t[id],r-l+1,t[id],tr);
t[id]->rev^=1;
t[id]=merge(merge(tl,t[id]),tr);
} else if ( op==2 ) {
int id,l1,r1,l2,r2;
RI(id,l1,r1,l2,r2);
Treap *t1,*t2,*t3,*t4,*t5;
split(t[id],l1-1,t1,t[id]);
split(t[id],r1-l1+1,t2,t[id]);
split(t[id],l2-r1-1,t3,t[id]);
split(t[id],r2-l2+1,t4,t5);
t[id]=merge(merge(merge(merge(t1,t4),t3),t2),t5);
} else if ( op==3 ) {
int l,r;
RI(l,r);
Treap *tl[2],*tm[2],*tr[2];
REP(i,2) {
split(t[i],l-1,tl[i],t[i]);
split(t[i],r-l+1,tm[i],tr[i]);
}
t[0]=merge(merge(tl[0],tm[1]),tr[0]);
t[1]=merge(merge(tl[1],tm[0]),tr[1]);
} else if ( op==4 ) {
int l,r;
RI(l,r);
vector<int> v[2];
REP(i,2) {
Treap *tl,*tr;
split(t[i],l-1,tl,t[i]);
split(t[i],r-l+1,t[i],tr);
go(t[i],v[i]);
t[i]=merge(merge(tl,t[i]),tr);
}
assert(v[0].size() == v[1].size());
int vn=SZ(v[0]);
REP(i,vn) {
p[i].x=v[0][i];
p[i].y=v[1][i];
}
random_shuffle(p,p+vn);
C c=MEC(vn,0);
double ans=sqrt(c.r2);
printf("%.2f\n",ans);
}
}
return 0;
}
In Java :
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Random;
import java.util.StringTokenizer;
public class TwoArrayProblem {
static int MAX = 1111111;
static class Node {
Node child[] = new Node[2], parent;
boolean reverse;
int value, size;
}
static class SplayTree {
public static final Node nil;
static {
nil = new Node();
nil.child[0] = nil.child[1] = nil.parent = nil;
nil.reverse = false;
nil.value = nil.size = 0;
}
private Node root = nil;
public SplayTree(int a[]) {
root = buildTree(a, 0, a.length - 1);
}
private Node buildTree(int a[], int l, int r) {
if (l > r) return nil;
int mid = (l + r) >> 1;
Node x = new Node();
x.value = a[mid];
x.parent = nil;
x.reverse = false;
setLink(x, buildTree(a, l, mid - 1), 0);
setLink(x, buildTree(a, mid + 1, r), 1);
update(x);
return x;
}
private void update(Node x) {
x.size = x.child[0].size + x.child[1].size + 1;
}
private void pushDown(Node x) {
if (x != nil) {
if (x.reverse) {
Node tmp = x.child[0];
x.child[0] = x.child[1];
x.child[1] = tmp;
x.reverse = false;
x.child[0].reverse = !x.child[0].reverse;
x.child[1].reverse = !x.child[1].reverse;
}
}
}
private static void setLink(Node parent,
Node child, int d) {
parent.child[d] = child;
child.parent = parent;
}
private int getDir(Node parent, Node child) {
return parent.child[0] == child ? 0 : 1;
}
private void rotate(Node x, int d) {
Node y = x.child[d], z = x.parent;
setLink(x, y.child[d ^ 1], d);
setLink(y, x, d ^ 1);
setLink(z, y, getDir(z, x));
update(x);
update(y);
}
private void splay(Node x) {
while (x.parent != nil) {
Node y = x.parent, z = y.parent;
int dy = getDir(y, x), dz = getDir(z, y);
if (z == nil) rotate(y, dy);
else if (dy == dz) {
rotate(z, dz);
rotate(y, dy);
} else {
rotate(y, dy);
rotate(z, dz);
}
}
root = x;
}
public void reverse(int right) {
if (right <= 1) return;
if (right == root.size) root.reverse = !root.reverse;
else {
accessByPos(right + 1);
root.child[0].reverse = !root.child[0].reverse;
}
}
public void reverse(int left, int right) {
if (left >= right) return;
reverse(right);
reverse(right - left + 1);
reverse(right);
}
public void swap(int left1, int right1,
int left2, int right2) {
reverse(left1, right1);
reverse(left2, right2);
reverse(right1 + 1, left2 - 1);
reverse(left1, right2);
}
private void dfs(Node root, int[] buffer) {
if (root == nil) return;
pushDown(root);
dfs(root.child[0], buffer);
buffer[++buffer[0]] = root.value;
dfs(root.child[1], buffer);
}
public void collect(int left, int right, int[] buffer) {
buffer[0] = 0;
if (left == 1 && right == root.size) {
dfs(root, buffer);
} else {
reverse(right);
Node x = accessByPos(right - left + 2).child[0];
dfs(x, buffer);
reverse(right);
}
}
public Node accessByPos(int pos) {
assert (pos >= 1 && pos <= root.size);
Node x = root;
pushDown(x);
while (x.child[0].size + 1 != pos) {
if (pos < x.child[0].size + 1) x = x.child[0];
else {
pos -= x.child[0].size + 1;
x = x.child[1];
}
pushDown(x);
}
splay(x);
return x;
}
}
static int n, m;
static int[] a;
static int[] buffer2 = new int[MAX];
static int[] buffer1 = new int[MAX];
static Random rand = new Random();
static double[][] p = new double[MAX][2];
static final double eps = 1E-8;
static double dis(double[] a, double[] b) {
return Math.sqrt((a[0] - b[0]) * (
a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
static void circumcenter(double[] a,
double[] b, double[] c, double[] res) {
double a1 = b[0] - a[0], b1 = b[1] - a[1],
c1 = (a1 * a1 + b1 * b1) / 2;
double a2 = c[0] - a[0], b2 = c[1] - a[1],
c2 = (a2 * a2 + b2 * b2) / 2;
double d = a1 * b2 - a2 * b1;
res[0] = a[0] + (c1 * b2 - c2 * b1) / d;
res[1] = a[1] + (a1 * c2 - a2 * c1) / d;
}
static double minDisk(int[] x, int[] y) {
// randomly permute them
for (int n = x[0]; n >= 1; n--) {
int i = rand.nextInt(n) + 1;
int tmp = x[i];
x[i] = x[n];
x[n] = tmp;
tmp = y[i];
y[i] = y[n];
y[n] = tmp;
}
for (int i = 1; i <= x[0]; i++) {
p[i][0] = x[i];
p[i][1] = y[i];
}
double[] c = p[1].clone();
double r = 0;
for (int i = 2; i <= x[0]; i++) {
if (dis(p[i], c) > r + eps) // ????
{
c[0] = p[i][0];
c[1] = p[i][1];
r = 0;
for (int j = 1; j < i; j++)
if (dis(p[j], c) > r + eps) // ????
{
c[0] = (p[i][0] + p[j][0]) / 2;
c[1] = (p[i][1] + p[j][1]) / 2;
r = dis(p[j], c);
for (int k = 1; k < j; k++)
if (dis(p[k], c) > r + eps) // ????
{// ?????????????
circumcenter(p[i], p[j], p[k], c);
r = dis(p[i], c);
}
}
}
}
return r;
}
public static void main(String[] args)
throws Exception {
BufferedReader cin = new BufferedReader(
new InputStreamReader(System.in));
BufferedWriter cout = new BufferedWriter(
new OutputStreamWriter(System.out));
StringTokenizer token =
new StringTokenizer(cin.readLine());
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
a = new int[2 * n];
int index = 0;
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
SplayTree tree = new SplayTree(a);
for (; m > 0; m--) {
token = new StringTokenizer(cin.readLine());
int op = Integer.parseInt(token.nextToken());
if (op == 1) {
int id = Integer.parseInt(token.nextToken());
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
if (id == 1) {
left += n;
right += n;
}
tree.reverse(left, right);
} else if (op == 2) {
int id = Integer.parseInt(token.nextToken());
int left1 = Integer.parseInt(token.nextToken());
int right1 = Integer.parseInt(token.nextToken());
int left2 = Integer.parseInt(token.nextToken());
int right2 = Integer.parseInt(token.nextToken());
if (id == 1) {
left1 += n;
right1 += n;
left2 += n;
right2 += n;
}
tree.swap(left1, right1, left2, right2);
} else if (op == 3) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.swap(left, right, left + n, right + n);
} else if (op == 4) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.collect(left, right, buffer1);
tree.collect(left + n, right + n, buffer2);
double r = minDisk(buffer1, buffer2);
cout.write(String.format("%.2f%n", r));
}
}
cin.close();
cout.close();
}
}
In C :
#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("%.2lf\n",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;
}
View More Similar Problems
Kitty's Calculations on a Tree
Kitty has a tree, T , consisting of n nodes where each node is uniquely labeled from 1 to n . Her friend Alex gave her q sets, where each set contains k distinct nodes. Kitty needs to calculate the following expression on each set: where: { u ,v } denotes an unordered pair of nodes belonging to the set. dist(u , v) denotes the number of edges on the unique (shortest) path between nodes a
View Solution →Is This a Binary Search Tree?
For the purposes of this challenge, we define a binary tree to be a binary search tree with the following ordering requirements: The data value of every node in a node's left subtree is less than the data value of that node. The data value of every node in a node's right subtree is greater than the data value of that node. Given the root node of a binary tree, can you determine if it's also a
View Solution →Square-Ten Tree
The square-ten tree decomposition of an array is defined as follows: The lowest () level of the square-ten tree consists of single array elements in their natural order. The level (starting from ) of the square-ten tree consists of subsequent array subsegments of length in their natural order. Thus, the level contains subsegments of length , the level contains subsegments of length , the
View Solution →Balanced Forest
Greg has a tree of nodes containing integer data. He wants to insert a node with some non-zero integer value somewhere into the tree. His goal is to be able to cut two edges and have the values of each of the three new trees sum to the same amount. This is called a balanced forest. Being frugal, the data value he inserts should be minimal. Determine the minimal amount that a new node can have to a
View Solution →Jenny's Subtrees
Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .
View Solution →Tree Coordinates
We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For
View Solution →