【bzoj2141】排队分块+树状数组

题目描述

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i<j且hi>hj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

输入

第一行为一个正整数n，表示小朋友的数量；第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；第三行为一个正整数m，表示交换操作的次数；以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。

输出

输出文件共m行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。

样例输入

3
130 150 140
2
2 3
1 3

样例输出

1
0
3

题解

分块+树状数组

题目描述不清，这里已补好，所求即逆序对的个数。

求逆序对我们可以使用树状数组。但是树状数组是离线的，也就是说每次交换都必须重新扫一遍，这样肯定会T。

由于每次交换时，除了这两个数及它们之间的数以外都是不需要改动的，只要找出中间的即可。

我们有分块大法。

把所有元素分成√n 个块，对每个块建立一个树状数组，就可以得出两个数之间所有整块的不同范围内数的个数。

然后对于多出来的那些数，直接暴力扫一下即可。由于它们都不是整块，所以不会有超过√n 个数。

这里偷了点懒没有if else，把符合条件加加减减直接变成加减条件成立性，应该不难理解。

时间复杂度O(n*√n*logn)。

需要注意的是两个数在同一个块内的处理，以及x>y的特判。

还有，题目中可能会出现相同的数，因此不能看作非小即大，需要分开处理。

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

struct data

{

	int h , p;

}a[20010];

int v[20010] , top , f[150][20010];

bool cmp1(data a , data b)

{

	return a.h < b.h;

}

bool cmp2(data a , data b)

{

	return a.p < b.p;

}

void update(int p , int x , int a)

{

	int i;

	for(i = x ; i <= top ; i += i & (-i))

		f[p][i] += a;

}

int query(int p , int x)

{

	int i , ans = 0;

	for(i = x ; i ; i -= i & (-i))

		ans += f[p][i];

	return ans;

}

int main()

{

	int n , m , i , j , si , ans = 0 , x , y;

	scanf("%d" , &n);

	si = (int)sqrt(n);

	for(i = 0 ; i < n ; i ++ )

		scanf("%d" , &a[i].h) , a[i].p = i;

	sort(a , a + n , cmp1);

	for(i = 0 ; i < n ; i ++ )

	{

		if(a[i].h != v[top]) v[++top] = a[i].h;

		a[i].h = top;

	}

	sort(a , a + n , cmp2);

	for(i = 0 ; i < n ; i ++ )

	{

		for(j = 0 ; j <= i / si ; j ++ ) ans -= query(j , a[i].h);

		ans += i;

		update(i / si , a[i].h , 1);

	}

	printf("%d\n" , ans);

	scanf("%d" , &m);

	while(m -- )

	{

		scanf("%d%d" , &x , &y);

		x -- ; y -- ;

		if(x > y) swap(x , y);

		if(x / si == y / si)

			for(i = x + 1 ; i < y ; i ++ )

				ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);

		else

		{

			for(i = x / si + 1 ; i < y / si ; i ++ )

				ans += (si - query(i , a[x].h)) + query(i , a[y].h - 1) - query(i , a[x].h - 1) - (si - query(i , a[y].h));

			for(i = x + 1 ; i < (x / si + 1) * si ; i ++ )

				ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);

			for(i = y / si * si ; i < y ; i ++ )

				ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);

		}

		ans += (a[x].h < a[y].h) - (a[x].h > a[y].h);

		update(x / si , a[x].h , -1) , update(y / si , a[y].h , -1);

		swap(a[x].h , a[y].h);

		update(x / si , a[x].h , 1) , update(y / si , a[y].h , 1);

		printf("%d\n" , ans);

	}

	return 0;

}

巴特西

【bzoj2141】排队分块+树状数组

最新文章

热门文章

巴特西

【bzoj2141】排队 分块+树状数组

最新文章

热门文章

【bzoj2141】排队分块+树状数组