[HackerRank Weekly Challenges -- Week11][Treap] Two Array Problem

原題連結

對最小包圓算法還不了解的可以先做這題。
因為他有保證詢問的區間總和不超過10^6，所以只要期望線性的作法就行了。

我們剩下的任務就是好好維護原序列。

其實除掉最小包圓之後留下來的問題就很單純了：維護兩顆可分裂合併Treap(or Splay），該做什麼操作就好好做那個操作就可以了。

細節上要注意reverse的tag傳遞要想清楚，不要寫錯。

還有一個神奇的地方是，code中用到的random_shuffle是用來防止特殊測資讓最小包圓算法失效的動作。
我原本只用了1次random_shuffle結果怎麼樣都過不了第5個testcase
後來我突發奇想再多用了一次，竟然又多錯了一筆！？

我就想：那就再多用一次好了，了不起再多錯一筆。

然後就AC了。幾十億人都驚呆了。

#define LL long long
#define DB double
#include<ctime>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cassert>
using namespace std;
unsigned ran()
{
    static unsigned x=20150307;
    return x=x*0xdefaced+1;
}
struct Node
{
    Node *lc,*rc;
    LL rev,val,pri,size;
    void push()
    {
        if(!rev) return;
        if(lc) lc->rev^=1;
        if(rc) rc->rev^=1;
        swap(lc,rc);
        rev=0;
    }
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0)+1;}
    Node() {}
    Node(LL x) {size=1;rev=0;pri=ran();val=x;lc=rc=NULL;}
}*root[2];
Node* merge(Node* a,Node* b)
{
    if(!a || !b) return a?a:b;
    else if(a->pri > b->pri)
    {
        a->push();
        a->rc=merge(a->rc,b);
        a->pull();
        return a;
    }
    else
    {
        b->push();
        b->lc=merge(a,b->lc);
        b->pull();
        return b;
    }
}
void split(Node* t,LL k,Node* &a,Node* &b)
{
    if(!t) {a=b=NULL;return;}
    t->push();
    if(((t->lc?t->lc->size:0)+1)<=k)
    {
        a=t;
        split(t->rc,k-(t->lc?t->lc->size:0)-1,a->rc,b);
        a->pull();
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        b->pull();
    }
}
void dfs(Node* now,vector<DB>& vec)
{
    if(!now) return;
    now->push();
    dfs(now->lc,vec);
    vec.push_back(now->val);
    dfs(now->rc,vec);
    now->pull();
}
struct Point
{
    DB x,y;
    Point() {}
    Point(DB _x,DB _y):x(_x),y(_y) {}
};
typedef Point Vector;
Vector operator + (const Vector& A,const Vector& B) {return Vector(A.x+B.x,A.y+B.y);}
Vector operator * (const Vector& A,const DB& t) {return Vector(A.x*t,A.y*t);}
Vector operator - (const Vector& A,const Vector& B) {return Vector(A.x-B.x,A.y-B.y);}
DB dis(const Point& A,const Point& B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
DB Cross(const Vector& A,const Vector& B) {return A.x*B.y-B.x*A.y;}
Point LineIntersec(Point& P,Vector& v,Point& Q,Vector& w)
{
    Vector u=P-Q;
    DB t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
Point get_center(const Point& A,const Point& B,const Point& C)
{
    Point P,v,Q,w;
    P=Point((A.x+B.x)*0.5,(A.y+B.y)*0.5);
    v=Vector(-(B.y-A.y),B.x-A.x);
    Q=Point((A.x+C.x)*0.5,(A.y+C.y)*0.5);
    w=Vector(-(C.y-A.y),C.x-A.x);
    return LineIntersec(P,v,Q,w); 
}
vector<DB> vec;
DB get_radius(Node* Tx,Node* Ty)
{
    vector<Point> point;
    vec.clear();
    dfs(Tx,vec);
    point.resize(vec.size());
    for(LL i=0;i<point.size();i++) point[i].x=vec[i];

    vec.clear();
    dfs(Ty,vec);
    assert(vec.size()==point.size());
    for(LL i=0;i<point.size();i++) point[i].y=vec[i];

    random_shuffle(point.begin(),point.end());
    random_shuffle(point.begin(),point.end());
    random_shuffle(point.begin(),point.end());
    Point center=Point(point[0].x,point[0].y);
    DB radius=0;
    LL n=point.size();
    for(LL i=1;i<n;i++)
    {
        if(dis(point[i],center) < radius) continue;
        center=point[i];
        for(LL j=0;j<i;j++)
        {
            if(dis(point[j],center) < radius) continue;
            center.x= (point[i].x+point[j].x)*0.5;
            center.y= (point[i].y+point[j].y)*0.5;
            radius= dis(point[j],center);
            for(LL k=0;k<j;k++)
            {
                if(dis(point[k],center) < radius) continue;
                center= get_center(point[i],point[j],point[k]);
                radius= dis(point[k],center);
            }    
        }
    }
    return radius;
}
Node *t[6];
int main()
{
    srand(time(NULL));
    LL N,M;
    scanf("%lld%lld",&N,&M);
    for(LL i=0,x;i<N;i++) {scanf("%lld",&x);root[0]=merge(root[0],new Node(x));}
    for(LL i=0,x;i<N;i++) {scanf("%lld",&x);root[1]=merge(root[1],new Node(x));}
    for(LL i=0,type,id,L[2],R[2];i<M;i++)
    {
        scanf("%lld",&type);
        if(type==1)
        {
            scanf("%lld%lld%lld",&id,L,R);
            split(root[id],L[0]-1,t[0],t[1]);
            split(t[1],R[0]-L[0]+1,t[1],t[2]);
            t[1]->rev^=1;
            root[id]=merge(t[0],merge(t[1],t[2]));
        }
        else if(type==2)
        {
            scanf("%lld%lld%lld%lld%lld",&id,L,R,L+1,R+1);

            split(root[id],L[0]-1,t[0],t[1]);
            split(t[1],R[0]-L[0]+1,t[1],t[2]);
            
            split(t[2],L[1]-R[0]-1,t[2],t[3]);
            split(t[3],R[1]-L[1]+1,t[3],t[4]);
            
            root[id]=merge(t[0],merge(t[3],merge(t[2],merge(t[1],t[4]))));
        }
        else if(type==3)
        {
            scanf("%lld%lld",L,R);
            split(root[0],L[0]-1,t[0],t[1]);
            split(t[1],R[0]-L[0]+1,t[1],t[2]);

            split(root[1],L[0]-1,t[3],t[4]);
            split(t[4],R[0]-L[0]+1,t[4],t[5]);

            root[0]=merge(t[0],merge(t[4],t[2]));
            root[1]=merge(t[3],merge(t[1],t[5]));
        }
        else
        {
            scanf("%lld%lld",L,R);
            split(root[0],L[0]-1,t[0],t[1]);
            split(t[1],R[0]-L[0]+1,t[1],t[2]);

            split(root[1],L[0]-1,t[3],t[4]);
            split(t[4],R[0]-L[0]+1,t[4],t[5]);
            
            printf("%.2f\n",get_radius(t[1],t[4]));
            root[0]=merge(t[0],merge(t[1],t[2]));
            root[1]=merge(t[3],merge(t[4],t[5]));
        }
    }
}