BZOJ 2141 排隊 樹套樹

BZOJ 2141 排隊 樹套樹

題目大意：給出一個數列，支持交換兩個數字的操作，問每次操作之後的逆序對數量。

思路：數字比較大，先離散化。然後先求一次總逆序對，每次交換兩個數字的時候用樹套樹維護一下逆序對的總數就可以了。。

好像樹套樹的常數略大，正解應該是分塊。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 20010
using namespace std;
#define QR QuickRead
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)
#define SIZE(a) ((a) == NULL ? 0:(a)->size)

namespace QuickRead{
	inline int GetChar() {
		static const int L = 1 << 15;
		static char buf[L],*S = buf,*T = buf;
		if(S == T) {
			T = (S = buf) + fread(buf,1,L,stdin);
			if(S == T)	return EOF;
		}
		return *S++;
	}
	template inline void Get(T &x) {
		static char c;
		while(!isdigit(c = GetChar()));
		x = c - '0';
		while(isdigit(c = GetChar()))
			x = (x << 1) + (x << 3) + c - '0';
	}
}

int cnt,asks,src[MAX];
pair xx[MAX];
int fenwick[MAX];

inline void Fix(int x)
{
	for(; x; x -= x&-x)
		++fenwick[x];
}

inline int GetSum(int x)
{
	int re = 0;
	for(; x < MAX; x += x&-x)
		re += fenwick[x];
	return re;
}

struct Treap{
	int val,random,cnt,size;
	Treap *son[2];

	Treap(int _) {
		val = _;
		random = rand();
		cnt = size = 1;
		son[0] = son[1] = NULL;
	}
	int Compare(int x) {
		if(x == val)	return -1;
		return x > val;
	}
	void Maintain() {
		size = cnt;
		if(son[0] != NULL)	size += son[0]->size;
		if(son[1] != NULL)	size += son[1]->size;	
	}
}*tree[MAX << 2];

inline void Rotate(Treap *&a,bool dir)
{
	Treap *k = a->son[!dir];
	a->son[!dir] = k->son[dir];
	k->son[dir] = a;
	a->Maintain(),k->Maintain();
	a = k;
}

void Insert(Treap *&a,int x)
{
	if(a == NULL) {
		a = new Treap(x);
		return ;
	}
	int dir = a->Compare(x);
	if(dir == -1)	++a->cnt;
	else {
		Insert(a->son[dir],x);
		if(a->son[dir]->random > a->random)
			Rotate(a,!dir);
	}
	a->Maintain();
}

void Delete(Treap *&a,int x)
{
	int dir = a->Compare(x);
	if(dir != -1)
		Delete(a->son[dir],x);
	else {
		if(a->cnt > 1)	--a->cnt;
		else {
			if(a->son[0] == NULL)	a = a->son[1];
			else if(a->son[1] == NULL)	a = a->son[0];
			else {
				int _dir = a->son[0]->random > a->son[1]->random;
				Rotate(a,_dir);
				Delete(a->son[_dir],x);
			}
		}
	}
	if(a != NULL)	a->Maintain();
}

int Lower(Treap *a,int x)
{
	if(a == NULL)	return 0;
	if(a->val >= x)	return Lower(a->son[0],x);
	return SIZE(a->son[0]) + a->cnt + Lower(a->son[1],x);
}

int Upper(Treap *a,int x)
{
	if(a == NULL)	return 0;
	if(a->val <= x)	return Upper(a->son[1],x);
	return SIZE(a->son[1]) + a->cnt + Upper(a->son[0],x);
}

inline void BuildTree(int l,int r,int pos)
{
	for(int i = l; i <= r; ++i)
		Insert(tree[pos],src[i]);
	if(l == r)	return ;
	int mid = (l + r) >> 1;
	BuildTree(l,mid,LEFT);
	BuildTree(mid + 1,r,RIGHT);
}

int Lower(int l,int r,int x,int y,int val,int pos)
{
	if(l == x && y == r)
		return Lower(tree[pos],val);
	int mid = (l + r) >> 1;
	if(y <= mid)	return Lower(l,mid,x,y,val,LEFT);
	if(x > mid)		return Lower(mid + 1,r,x,y,val,RIGHT);
	int left = Lower(l,mid,x,mid,val,LEFT);
	int right = Lower(mid + 1,r,mid + 1,y,val,RIGHT);
	return left + right;
}

int Upper(int l,int r,int x,int y,int val,int pos)
{
	if(l == x && y == r)
		return Upper(tree[pos],val);
	int mid = (l + r) >> 1;
	if(y <= mid)	return Upper(l,mid,x,y,val,LEFT);
	if(x > mid)		return Upper(mid + 1,r,x,y,val,RIGHT);
	int left = Upper(l,mid,x,mid,val,LEFT);
	int right = Upper(mid + 1,r,mid + 1,y,val,RIGHT);
	return left + right;
}

void Delete(int l,int r,int x,int val,int pos)
{
	Delete(tree[pos],val);
	if(l == r)	return ;
	int mid = (l + r) >> 1;
	if(x <= mid)	Delete(l,mid,x,val,LEFT);
	else	Delete(mid + 1,r,x,val,RIGHT);
}

void Insert(int l,int r,int x,int val,int pos)
{
	Insert(tree[pos],val);
	if(l == r)	return ;
	int mid = (l + r) >> 1;
	if(x <= mid)	Insert(l,mid,x,val,LEFT);
	else	Insert(mid + 1,r,x,val,RIGHT);
}

int main()
{
	cin >> cnt;
	for(int i = 1; i <= cnt; ++i) {
		QR::Get(xx[i].first);
		xx[i].second = &src[i];
	}
	sort(xx + 1,xx + cnt + 1);
	int t = 0;
	for(int i = 1; i <= cnt; ++i) {
		if(i == 1 || xx[i].first != xx[i - 1].first)
			++t;
		*xx[i].second = t;
	}
	int inv = 0;
	for(int i = 1; i <= cnt; ++i) {
		inv += GetSum(src[i] + 1);
		Fix(src[i]);
	}
	cout << inv << endl;

	BuildTree(1,cnt,1);

	int x,y;
	for(QR::Get(asks); asks--;) {
		QR::Get(x),QR::Get(y);
		if(x > y)	swap(x,y);
		if(x + 1 != y) {
			inv -= Lower(1,cnt,x + 1,y - 1,src[x],1);
			inv += Upper(1,cnt,x + 1,y - 1,src[x],1);
			inv -= Upper(1,cnt,x + 1,y - 1,src[y],1);
			inv += Lower(1,cnt,x + 1,y - 1,src[y],1);
		}
		Delete(1,cnt,x,src[x],1);
		Insert(1,cnt,x,src[y],1);
		Delete(1,cnt,y,src[y],1);
		Insert(1,cnt,y,src[x],1);
		if(src[x] < src[y])	++inv;
		if(src[x] > src[y])	--inv;
		swap(src[x],src[y]);
		printf("%d\n",inv);
	}
	return 0;
}