第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树

#include<stdio.h>
#define N 200010
long long ans = 0; 
int n,val,index=1; 
 
int S[N],left[N],right[N],key[N];
int rRotate(int t){ 
	int tem = left[t];
	left[t] = right[tem];
	right[tem] = t;
	S[t] = S[left[t]]+S[right[t]]+1;
	S[tem] = S[left[tem]]+S[right[tem]]+1;
	return tem;
} 
int lRotate(int t){
	int tem = right[t];
	right[t] = left[tem];
	left[tem] = t;
	S[t] = S[right[t]]+S[left[t]]+1;
	S[tem] = S[right[tem]]+S[left[tem]]+1;
	return tem;
}
int adjust(int t,int flag){
	if(flag){
		if(S[left[left[t]]]>S[right[t]] || S[right[left[t]]]>S[right[t]]){
			if(S[right[left[t]]]>S[right[t]]){
				left[t] = lRotate(left[t]);
			}
			return rRotate(t);
		}
	}else{
		if(S[right[right[t]]]>S[left[t]] || S[left[right[t]]]>S[left[t]]){
			if(S[left[right[t]]]>S[left[t]]){
				right[t] = rRotate(right[t]);
			}
			return lRotate(t);
		}
	}
	return t; 
}
int insert(int t,int node){ 
	S[t]++;
	if(key[node]<key[t]){ 
		if(left[t]==0){ 
			left[t]=node;
		}else{ 
			left[t] = insert(left[t],node);
		}
	}else{
		if(right[t]==0){
			right[t]=node;
		}else{
			right[t] = insert(right[t],node);
		}
	}
	return adjust(t,key[node]<key[t]); 
}
int rank(int t,int val){ 
	if(t==0)return 0; 
	if(val>=key[t]){
		return rank(right[t],val);
	}else{
		return rank(left[t],val)+1+S[right[t]];
	}
}
int merge(int node,int begin,int end){
	long long lens=0,rans=0; 
	int i;
	for(i=begin;i<end;i++){
		int tem = rank(node,key[i]); 
		lens += tem;
		rans += S[node] - tem;
	}
	ans += lens < rans ? lens : rans;
	for(i=begin;i<end;i++){
		left[i]=right[i]=0;
		S[i]=1;
		node = insert(node,i);
	}
	return node;
} 
int buildTree(){
	scanf("%d",&val);
	if(val!=0){
		left[index]=right[index]=0;
		S[index]=1;
		key[index]=val;
		return index++;
	}
	int a = index;
	int lt = buildTree();
	int b = index;
	int rt = buildTree();
	int c = index;
	if(b - a > c - b){ 
		return merge(lt,b,c);
	}else{
		return merge(rt,a,b);
	}
}
int main(){
	scanf("%d",&n);
	buildTree();
	printf("%I64d\n",ans); 
	return 0; 
}

#include<stdio.h>
#include<iostream>
using namespace std;
#define ForD(i,n) for(int i=n;i;i--)
#define F (100000007)
#define MAXN (2*200000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}

int n,root=0;/*n->叶子结点数,root->根序号？*/
struct node
{
    int fa;        /*父结点的下标*/
    int ch[2];    /*0->左树下标    1->右树下标*/
    int size;    /*size->当前结点含有的有效结点数*/ 
    int c;        /*当前结点的数值*/
    node():size(0),c(0){ch[0]=ch[1]=fa=0;}    /*初始化为0*/
}a[MAXN];                                    /*树形数组->纪录各叶结点的数值*/

void update(int x)/*更新叶结点个数*/
{
    a[x].size=a[a[x].ch[0]].size+a[a[x].ch[1]].size+(a[x].c>0);
}
int tail=0;
void pushdown(int x)/*将叶结点的父结点指向当前结点*/
{
    a[a[x].ch[0]].fa=a[a[x].ch[1]].fa=x;
}

/*创建树*/
void build(int &x)
{
    if (!x) x=++tail;
    scanf("%d",&a[x].c);
    if (a[x].c==0)
    {
        build(a[x].ch[0]);/*创建左子树*/
        build(a[x].ch[1]);/*创建右子树*/
        update(x);pushdown(x);/*更新当前结点的有效叶结点个数，以及父结点指向*/
    }else a[x].size=1;
}

void rotate(int x)/*旋转*/
{
    int y=a[x].fa,z=a[y].fa;
    bool p=a[y].ch[0]==x;
    if (z)        /*有爷爷*/
    {
        if (a[z].ch[0]==y) /*未旋转*/
            a[z].ch[0]=x;/*将子树提拔为父树(升序)*/
        else 
            a[z].ch[1]=x;    /*还原状态*/
    }
    a[x].fa=z,a[y].fa=x;/*当前结点与父结点交换(父结点指向)*/ 
    if (a[x].ch[p])     /*原子树是否有右树(隔代转移)*/
        a[a[x].ch[p]].fa=y;
    a[y].ch[p^1]=a[x].ch[p];
    a[x].ch[p]=y;        /*父树移至子树的右端(右树)*/
    update(y);    /*更新旋转后，子树的结点的有效结点数*/
}

void splay(int x)
{
    while (a[x].fa)/*不为根结点*/
    {
        int y=a[x].fa,z=a[y].fa;
        if (z)        /*有爷爷*/
            if ((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);/*旋转*/
            else rotate(y);
        rotate(x);
    }
    update(x);
}
void ins(long long &tot,int x,int y)
{
    a[x].size++;            /*插入+1*/
    if (a[y].c<=a[x].c)        /*是逆序对*/
    {
        if (a[x].ch[0])     /*左树有子*/
            ins(tot,a[x].ch[0],y);
        else                 /*左树无子*/
            a[y].fa=x,splay(a[x].ch[0]=y);/*右数插入到左树子*/
    }
    else
    {
        tot+=a[a[x].ch[0]].size+(a[x].c>0);
        if (a[x].ch[1]) ins(tot,a[x].ch[1],y);
        else a[y].fa=x,splay(a[x].ch[1]=y);
    }
}


int q[MAXN],size;

void clac(int x,int y)
{
    if (a[y].ch[0]) clac(x,a[y].ch[0]);
    if (a[y].c) q[++size]=y;
    if (a[y].ch[1]) clac(x,a[y].ch[1]);
}

long long merge(bool &lor,int z)/*分治*/
{
    int x=a[z].ch[0],y=a[z].ch[1];
    if (a[x].size<a[y].size) /*判断叶结点多的往前调(平衡树?)*/ 
        swap(x,y);
 
    a[x].fa=0;a[y].fa=0;q[1]=y;
    size=0;clac(x,y);
    long long tot=0;    /*最少逆序对*/
    ForD(i,size)        /*循环（子结点数）次*/
    {
        int now=q[i];
        a[now].ch[0]=a[now].ch[1]=a[now].fa=0;
        a[now].size=1;
        ins(tot,x,now);
        x=now;
    }
    a[x].fa=z;
    a[z].ch[0]=0,a[z].ch[1]=x;
    return tot;
}


long long qur(int &x)
{
    if (a[x].c) return 0;/*若根结点没有叶结点，则逆序对为0*/
    else
    {
        long long lson=a[a[x].ch[0]].size,rson=a[a[x].ch[1]].size,ls=qur(a[x].ch[0]),rs=qur(a[x].ch[1]);
        bool lor=0;
        long long ms=merge(lor,x);
        return ls+rs+min(lson*rson-ms,ms);
    }
}
int main()
{
    scanf("%d",&n);
    build(root);
    cout<<qur(root)<<endl;
    return 0;
}

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.*;

public class Main {

    static Node[] tree;
    static int inReturn;
    static int[] noLeaf;
    static Queue<PQItem> inQ;

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        int n = in.nextInt(); long cnt = 0;
        noLeaf = new int[n];
        tree = new Node[n*2];
        tree[0] = new Node(0);
        tree[1] = new Node(1);
        build(tree[1], 1, in);
        inQ = new PriorityQueue();
        for (int i = n - 2; i >= 0; i--) cnt += merge(noLeaf[i]);
        System.out.print(cnt);
    }


    static void build(Node node, int offset, InputReader in) throws IOException {
        LinkedList<Node> queue = new LinkedList();
        int index = 0;
        queue.addFirst(node);
        while (queue.size() > 0) {
            Node now = queue.poll();
            noLeaf[index] = now.weight;
            now.weight = in.nextInt();
            if (now.weight == 0) {
                now.left = ++offset;
                queue.addFirst(tree[++offset] = new Node(offset));
                now.right = offset;
                queue.addFirst(tree[offset - 1] = new Node(offset - 1));
                index++;
            } else now.size = 1;
        }
    }

    static long merge(int node) {
        long LS = tree[tree[node].left].size, RS = tree[tree[node].right].size, cnt = 0;
        if (LS > RS) {
            Queue(tree[node].right);
            tree[node] = tree[tree[node].left];
        } else {
            Queue(tree[node].left);
            tree[node] = tree[tree[node].right];
        }
        while (inQ.size() > 0) {
            inReturn = 0;
            insert(node, reSet(inQ.poll().node));
            cnt += inReturn;
        }
        return Math.min(cnt, LS * RS - cnt);
    }


    static void Queue(int node) {
        if (tree[node].left != 0) Queue(tree[node].left);
        if (tree[node].right != 0) Queue(tree[node].right);
        if (tree[node].weight != 0) inQ.offer(new PQItem(tree[node].weight, node));
    }

    static void insert(int node, int value) {
        ++tree[node].size;
        if (tree[node].weight >= tree[value].weight) {
            if (tree[node].left != 0) insert(tree[node].left, value);
            else  tree[node].left = value;
            maintain(node, true);
        } else {
            inReturn += tree[tree[node].left].size + 1;
            if (tree[node].right != 0) insert(tree[node].right, value);
            else tree[node].right = value;
            maintain(node, false);
        }
    }

    static int reSet(int node) {
        tree[node].size = 1;
        tree[node].left = 0;
        tree[node].right = 0;
        return node;
    }

    static void LeftRotate(int node) {
        Node temp = tree[node];
        int r = temp.right;
        tree[r].size = temp.size;
        temp.right = tree[r].left;
        temp.size = tree[temp.left].size + tree[temp.right].size + 1;
        tree[r].left = r;
        tree[node] = tree[r];
        tree[r] = temp;
    }

    static void RightRotate(int node) {
        Node temp = tree[node];
        int l = temp.left;
        tree[l].size = temp.size;
        temp.left = tree[l].right;
        temp.size = tree[temp.left].size + tree[temp.right].size + 1;
        tree[l].right = l;
        tree[node] = tree[l];
        tree[l] = temp;
    }

    static void maintain(int node, boolean flag) {
        if (flag) {
            if (tree[tree[tree[node].left].left].size > tree[tree[node].right].size) RightRotate(node);
            else if (tree[tree[tree[node].left].right].size > tree[tree[node].right].size) {
                LeftRotate(tree[node].left);
                RightRotate(node);
            } else return;
        } else {
            if (tree[tree[tree[node].right].right].size > tree[tree[node].left].size) LeftRotate(node);
            else if (tree[tree[tree[node].right].left].size > tree[tree[node].left].size) {
                RightRotate(tree[node].right);
                LeftRotate(node);
            } else return;
        }
        maintain(tree[node].left, true);
        maintain(tree[node].right, false);
    }

    static class Node {
        int weight;
        int size;
        int left;
        int right;

        Node(int weight) { this.weight = weight; }
    }

    static class PQItem implements Comparable<PQItem> {

        int index;
        int node;

        PQItem (int index, int node) {
            this.node = node;
            this.index = index;
        }

        @Override
        public int compareTo(PQItem o) {
            if (this.index > o.index) return -1;
            return +1;
        }
    }

    static class InputReader {

        BufferedReader read;
        StringTokenizer tokens;
        String delimiters;

        InputReader (InputStream in, String delimiters) {
            this.read = new BufferedReader(new InputStreamReader(in));
            this.delimiters = delimiters;
            this.tokens = new StringTokenizer("", delimiters);
        }

        InputReader (InputStream in) { this(in, " \t\n\r\f"); }

        String next() throws IOException {
            while (!tokens.hasMoreTokens()) tokens = new StringTokenizer(read.readLine(), delimiters);
            return tokens.nextToken();
        }

        int nextInt() throws IOException { return Integer.parseInt(next()); }

        void close() throws IOException { read.close(); }
    }
}