记录编号	423845	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	1.544 s
提交时间	2017-07-12 16:45:52	内存使用	3.59 MiB

#include <cstring>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const double alpha = 0.755;
const int MAXN = 20005;
int n,h[MAXN],len,m;
long long Ans;


template<typename _t>
inline _t read(){
    _t x = 0;
    int f = 1;
    char ch = getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x*10)+(ch^48);
    return (_t)x*f;
}

struct node{
    int s,cover,v,ex;
    node *ch[2];
    
    void operator delete (void *p);

    void* operator new (size_t);

    bool bad(){
        return ch[0]->cover > cover * alpha || ch[1]->cover > cover * alpha;
    }

    void Maintain(){
        s = ch[0]->s+ch[1]->s+ex;
        cover =ch[0]->cover+ch[1]->cover+1;
    }

    node(){
        s=v=cover=ex=0;
        ch[0]=ch[1]=NULL;
    }

    node(int x);
    
}*null = new node(),*lst[MAXN<<5],*C,*mempool;

vector<node*>q;

void* node :: operator new (size_t){
    node * p;
    if(!q.empty()){
        p = q.back();
        q.pop_back();
    }
    else{
        if(C==mempool){
            C = new node[1<<15];
            mempool = C + (1<<15);
        }
        p = C++;
    }
    return p;
}

void node :: operator delete (void *p){
    q.push_back((node*)p);
}

node :: node(int x){
    v=x;s=cover=ex=1;
    ch[0]=ch[1]=null;
}

void travel(node *p){
    if(p == null)return;
    travel(p->ch[0]);
    if(p->ex)lst[++len] = p;
    else delete p;
    travel(p->ch[1]);
}

node *divide(int l,int r){
    if(l>r)return null;
    int m = l + r >> 1;
    lst[m]->ch[0]=divide(l,m-1);
    lst[m]->ch[1]=divide(m+1,r);
    lst[m]->Maintain();
    return lst[m];
}

void rebuild(node *&o){
    len = 0;
    travel(o);
    o=divide(1,len);
}

inline int rank_min(node *o,int x){
    int Ans = 0;
    while(o!=null){
        if(x<=o->v)o = o -> ch[0];
        else Ans += o->ch[0]->s+o->ex,o = o->ch[1];
    }
    return Ans;
}

inline int rank_max(node *o,int x){
    int Ans = 0;
    while(o!=null){
        if(x>=o->v)o = o->ch[1];
        else Ans += o->ch[1]->s+o->ex,o=o->ch[0];
    }
    return Ans;
}

node **insert(node *&o,int x){
    if(o == null){
        o = new node(x);
        return &null;
    }
    node **p = insert(o->ch[o->v<=x],x);
    if(o->bad())p = &o;
    o->Maintain();
    return p;
}

void Insert(node *&o,int x){
    node **p = insert(o,x);
    if(*p!=null)rebuild(*p);
}

void erase(node *o,int k){
    if(o->ex && k == o->ch[0]->s +1){
        o -> ex=0;
        o-> Maintain();
        return;
    }
    if(o->ch[0]->s>=k)erase(o->ch[0],k);
    else erase(o->ch[1],k-o->ch[0]->s-o->ex);
    o -> Maintain();
}

void Erase(node *&o,int x){
    erase(o,rank_min(o,x)+1);
    if(o->s < o->cover *alpha)rebuild(o);
}

struct Tree{
    int l,r,m;
    Tree *ls,*rs;
    node *root;
    void *operator new (size_t);
    Tree(){
        ls=rs=NULL;
        root=null;
        m = l = r =0;
    }
}*QAQ,*S,*T;

void* Tree :: operator new (size_t){
    if(S==T){
        S = new Tree[1<<15];
        T = S + (1<<15);
    }
    return S++;
}

void build(Tree *&o,int l,int r){
    if(!o)o=new Tree;
    o->l=l,o->r=r,o->m=l+r>>1;
    for(int i=l;i<=r;i++)Insert(o->root,h[i]);
    if(l==r)return;
    build(o->ls,l,o->m);
    build(o->rs,o->m+1,r);
}

void Tree_insert(Tree *o,int x,int w){
    Insert(o->root,w);
    if(o->l==o->r)return;
    if(x<=o->m)Tree_insert(o->ls,x,w);
    else Tree_insert(o->rs,x,w);
}

void Tree_erase(Tree *o,int x,int w){
    Erase(o->root,w);
    if(o->l==o->r)return;
    if(x<=o->m)Tree_erase(o->ls,x,w);
    else Tree_erase(o->rs,x,w);
}

int Tree_max(Tree *o,int x,int y,int w){
    if(x<=o->l&&o->r<=y)return rank_max(o->root,w);
    int ans = 0;
    if(x<=o->m)ans += Tree_max(o->ls,x,y,w);
    if(o->m<y)ans += Tree_max(o->rs,x,y,w);
    return ans;
}

int Tree_min(Tree *o,int x,int y,int w){
    if(x<=o->l&&o->r<=y)return rank_min(o->root,w);
    int ans = 0;
    if(x<=o->m)ans += Tree_min(o->ls,x,y,w);
    if(o->m<y)ans += Tree_min(o->rs,x,y,w);
    return ans;
}

int main(){
    freopen("nt2011_queue.in","r",stdin);
    freopen("nt2011_queue.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    build(QAQ,1,n);
    for(int i=2;i<=n;i++)Ans+=Tree_max(QAQ,1,i-1,h[i]);
    scanf("%d",&m);
    printf("%lld\n",Ans);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        if(l!=1)Ans-=Tree_max(QAQ,1,l-1,h[l]);
        if(l!=n)Ans-=Tree_min(QAQ,l+1,n,h[l]);
        Tree_erase(QAQ,l,h[l]);
        if(r!=1)Ans+=Tree_max(QAQ,1,r-1,h[l]);
        if(r!=n)Ans+=Tree_min(QAQ,r+1,n,h[l]);
        Tree_insert(QAQ,r,h[l]);
        if(l!=1)Ans+=Tree_max(QAQ,1,l-1,h[r]);
        if(l!=n)Ans+=Tree_min(QAQ,l+1,n,h[r]);
        Tree_erase(QAQ,r,h[r]);
        if(r!=1)Ans-=Tree_max(QAQ,1,r-1,h[r]);
        if(r!=n)Ans-=Tree_min(QAQ,r+1,n,h[r]);
        Tree_insert(QAQ,l,h[r]);
        swap(h[l],h[r]);
        printf("%lld\n",Ans);
    }
}