crazy thairs(线段树求逆序数).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <memory>
#include <algorithm>
using namespace std;

/**** **** **** **** **** ****
*    Function Name :	BigNumber
*    Description :		BigNumber's HPC
*    Author :			HuangWei
*    Last Edited :		07.8.25
**** **** **** **** **** ****/

#define BASE    100000    // 基数
#define DIG        10    // 存储
using namespace std;

class BigNumber
{
private:
	int data[DIG];    // 数据区
	int len;        // 记录长度
public:
	BigNumber()     {len=1;memset(data,0,sizeof(data));data[0]=1;}
	BigNumber(int);    // 输入默认十进制
	BigNumber(char*);
	BigNumber(const BigNumber &);
	// 类型转换
	BigNumber & Num_BNum(int);
	BigNumber & Str_BNum(char*);
	int Int();
	string Str();
	void cprint();
	// HPC
	BigNumber & Add(const BigNumber &);
	BigNumber & Sub(const BigNumber &);
	BigNumber & Mul(const BigNumber &);
	BigNumber & Div(int);
	BigNumber & Mod(int);
	BigNumber & operator=(const BigNumber &);
	int Bigger(const BigNumber &) const;

	BigNumber operator + (const BigNumber &);
	BigNumber operator - (const BigNumber &);
	BigNumber operator * (const BigNumber &);
	BigNumber operator / (int);
	BigNumber operator % (int);
	BigNumber operator ^ (int);

	BigNumber & operator += (const BigNumber &);
	BigNumber & operator -= (const BigNumber &);
	BigNumber & operator *= (const BigNumber &);
	BigNumber & operator /= (int);
	BigNumber & operator %= (int);
};

BigNumber & BigNumber::Num_BNum(int b)
{
	len=1;     memset(data,0,sizeof(data));
	data[0] = 1;
	if(b < 0) {
		b = -b;
		data[0] = -1;
	}
	while(b > 0) {
		data[ len++ ] = b % BASE;
		b /= BASE;
	}
	return *this;
}

BigNumber & BigNumber::Str_BNum(char* sb)
{
	int t=0, d=1, b=0, slen=strlen(sb), i;
	len=1;     memset(data,0,sizeof(data));
	data[0] = 1;
	if(sb[0] == '-')     data[0] = -1, b=1;
	for(i=slen-1; i>=b ;i--) {
		while(t >= BASE || d > BASE) {
			data[ len++ ] = t % BASE;
			t /= BASE;
			d = 10;
		}
		t += (sb[i]-'0') * d;
		d *= 10;
	}
	while(t > 0) {
		data[ len++ ] = t % BASE;
		t /= BASE;
	}
	return *this;
}

int BigNumber::Int() 
{
	istringstream sin;
	int v;
	sin.str( this->Str() );
	sin >> v;
	return v;
}

string BigNumber::Str()
{
	int i,base_len=0;
	ostringstream sout;
	if(len == 1) {
		sout << '0';
		//sout << endl;
		return sout.str();
	}
	if(data[0] < 0)     sout << "-";
	sout << data[len-1];
	i = BASE;
	while(i > 1) {
		base_len++;
		i /= 10;
	}
	for(i=len-2; i>0 ;i--) {
		sout.width(base_len);
		sout.fill('0');
		sout << data[i];
	}
	//sout << endl;
	return sout.str();
}

BigNumber::BigNumber(int b)
{this->Num_BNum(b);}

BigNumber::BigNumber(char* sb)
{this->Str_BNum(sb);}
// -1 a<b, 0 a==b, 1 a>b
BigNumber::BigNumber(const BigNumber & b)
{len = b.len;     memcpy(data,b.data,sizeof(data));}

int BigNumber::Bigger(const BigNumber & b) const
{
	int i,flag;
	if(data[0] ==1 && b.data[0] ==1)        flag = 1;
	else if(data[0] ==1 && b.data[0] ==-1)    return 1;
	else if(data[0] ==-1 && b.data[0] ==1)    return -1;
	else    flag = -1;

	if(len > b.len)     return flag;
	else if(len == b.len) {
		for(i=len-1; i>0 ;i--)
			if(data[i] > b.data[i])     return flag;
	}
	if(i == 0)     return 0;
	return -flag;
}

BigNumber & BigNumber::Add(const BigNumber & b)
{
	int i;
	len= len > b.len ? len : b.len;
	for(i=1; i<len ;i++) {
		data[i] += b.data[i];
		if(data[i] >= BASE) {
			data[i+1]++;
			data[i] -= BASE;
		}
	}
	if(data[i] > 0)     len = i+1;
	return *this;
}

BigNumber & BigNumber::Sub(const BigNumber & b)
{
	int i;
	len= len > b.len ? len : b.len;
	for(i=1; i<len ;i++) {
		data[i] -= b.data[i];
		if(data[i] < 0) {
			data[i+1]--;
			data[i] += BASE;
		}
	}
	if(data[len] < 0) {
		for(i=0; i<=len ;i++)
			data[i] = -data[i];
		for(i=1; i<len ;i++)
			if(data[i] < 0) {
				data[i+1]--;
				data[i] += BASE;
			}
	}
	while(data[len-1] == 0)     len--;
	return *this;
}

BigNumber & BigNumber::Mul(const BigNumber & b)
{
	BigNumber bt;
	int i,j,up;
	int temp,temp1;

	bt.data[0] = data[0] * b.data[0];
	for(i=1; i<len ;i++) {
		up = 0;
		for(j=1; j<b.len ;j++) {
			temp = data[i] * b.data[j] + bt.data[i+j-1] + up;
			if(temp >= BASE) {
				temp1 = temp % BASE;
				up = temp / BASE;
				bt.data[i+j-1] = temp1;
			}
			else {
				up = 0;
				bt.data[i+j-1] = temp;
			}
		}
		if(up != 0)     bt.data[i+j-1] = up;
	}
	bt.len = i+j;
	while(bt.data[bt.len-1] == 0) bt.len--;
	*this=bt;
	return *this;
}

BigNumber & BigNumber::Div(int b)
{
	BigNumber bt;
	int i,down = 0;

	if(b < 0)     bt.data[0] = -data[0] , b = -b;
	else          bt.data[0] = data[0];
	for(i=len-1; i>=1 ;i--) {
		bt.data[i] = (data[i] + down * BASE) / b;
		down = data[i] + down * BASE - bt.data[i] * b;
	}
	bt.len = len;
	while(bt.data[bt.len-1] == 0)     bt.len--;
	*this=bt;
	return *this;
}

BigNumber & BigNumber::Mod(int b)
{
	int temp = 0, up = 0, i;
	for(i=len-1; i>=1 ;i--) {
		temp = data[i];
		temp += up * BASE;
		up = temp % b;
	}
	if(data[0] < 0)     up = -up;
	*this = up;
	return *this;
}

BigNumber BigNumber::operator ^ (int b)
{
	BigNumber bt = *this;
	BigNumber bt2 = 1;
	int i,j;
	if(b == 0) {
		return bt2;
	}
	else {
		while(b > 1) {
			if(b%2) {
				bt2 *= bt;
			}
			bt *= bt;
			b /= 2;
		}
	}
	return bt*bt2;
}

void BigNumber::cprint()
{
	int i,base_len=0;
	if(len == 1) {
		printf("0\n");
		return ;
	}
	if(data[0] < 0)    printf("-");
	printf("%d", data[len-1]);
	i = BASE;
	while(i > 1) {
		base_len++;
		i /= 10;
	}
	for(i=len-2; i>0 ;i--) {
		printf("%0*d", base_len ,data[i]);
	}
	printf("\n");
}

BigNumber & BigNumber::operator = (const BigNumber & b)
{len = b.len;     memcpy(data,b.data,sizeof(data));     return *this;}

BigNumber BigNumber::operator + (const BigNumber & b)
{BigNumber bt=*this;     return bt.Add(b);}

BigNumber BigNumber::operator - (const BigNumber & b)
{BigNumber bt=*this;     return bt.Sub(b);}

BigNumber BigNumber::operator * (const BigNumber & b)
{BigNumber bt=*this;     return bt.Mul(b);}

BigNumber BigNumber::operator / (int b)
{BigNumber bt=*this;     return bt.Div(b);}

BigNumber BigNumber::operator % (int b)
{BigNumber bt=*this;     return bt.Mod(b);}

BigNumber & BigNumber::operator += (const BigNumber & b)
{return this->Add(b);}

BigNumber & BigNumber::operator -= (const BigNumber & b)
{return this->Sub(b);}

BigNumber & BigNumber::operator *= (const BigNumber & b)
{return this->Mul(b);}

BigNumber & BigNumber::operator /= (int b)
{return this->Div(b);}

BigNumber & BigNumber::operator %= (int b)
{return this->Mod(b);}


const int MAX = 51000;
int n, num[MAX], snum[MAX];
int temp[MAX], * lnum, * tnum;
BigNumber cal[MAX];

struct node {
	int l, r;
	node * pl, * pr;
	BigNumber ex;
}mem[2*MAX];
int mem_pos;

node * new_node() {
	memset(mem + mem_pos, 0, sizeof(node));
	return mem + (mem_pos ++);
}

node * make_tree(int il, int ir) {
	node * root = new_node();
	root->l = snum[il];
	root->r = snum[ir];
	if(il != ir) {
		int mid = (il+ir)/2;
		root->pl = make_tree(il, mid);
		root->pr = make_tree(mid+1, ir);
	}
	return root;
}

BigNumber anti;
void insert(node * root, int pos) {
	root->ex += cal[pos];
	if(root->l == root->r) {
		return;
	}
	if(root->pl->r >= lnum[pos]) {
		insert(root->pl, pos);
	}
	else {
		anti += root->pl->ex;
		insert(root->pr, pos);
	}
}

void clear() {
	int i;
	for(i=0;i<mem_pos;i++) {
		mem[i].ex = 0;
	}
}

int main() {
	int i,j,k;
	BigNumber ans;
	while(scanf("%d", &n)==1) {
		for(i=0;i<n;i++) {
			scanf("%d", num+i);
			snum[i] = num[i];
			cal[i] = 1;
		}
		sort(snum, snum+n);
		ans = 0;
		mem_pos = 0;
		lnum = num;
		tnum = temp;
		node * root = make_tree(0,n-1);
		for(i=2;i<=5;i++) {
			k = 0;
			for(j=0;j<n;j++) {
				anti = 0;
				insert(root,j);
				if(anti.Bigger(0) != 0) {
					cal[k] = anti;
					tnum[k ++] = lnum[j];
					if(i == 5) ans += anti;
				}
			}
			n = k;
			int * pt = lnum;
			lnum = tnum;
			tnum = pt;
			clear();
		}
		//printf("%d\n", ans);
		ans.cprint();
	}
}