BZOJ2141：排队

浅谈分块：https://www.cnblogs.com/AKMer/p/10369816.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2141

第一次的答案可以直接用树状数组求。

如果交换\(pos_1\)和\(pos_2\)，那么显然我不需要管\([1,pos_1-1]\)和\([pos_2+1,n]\)。

对于\([pos_1+1,pos_2-1]\)之间的每个数\(v_i\)

\(v_i<v_{pos_1}\)，答案减一；\(v_i>v_{pos_1}\)，答案加一；\(v_i<v_{pos_2}\)，答案加一，\(v_i>v_{pos_2}\)，答案减一。

对于每个块我用一个树状数组维护块内权值个数。整个的块直接查找有多少小于或者大于某个值的数的个数，零散的直接暴力扫。

时间复杂度：\(O(NlogN+M\sqrt{N}logN)\)

空间复杂度：\(O(N\sqrt{n})\)

代码如下：

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

#define low(i) ((i)&(-(i)))

const int maxn=2e4+5;

int L[145],R[145];

int n,m,cnt,block,ans;

int tmp[maxn],v[maxn],bel[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct Tree_array {

	int c[maxn];

	void add(int pos,int num) {

		for(int i=pos;i<=cnt;i+=low(i))

			c[i]+=num;

	}

	int query(int pos) {

		int res=0;

		for(int i=pos;i;i-=low(i))

			res+=c[i];

		return res;

	}

}T[145];

void check(int i,int l,int r) {

	if(v[i]<v[l])ans--;

	if(v[i]>v[l])ans++;

	if(v[i]<v[r])ans++;

	if(v[i]>v[r])ans--;

}

int main() {

	n=read(),block=sqrt(n);

	for(int i=1;i<=n;i++) {

		v[i]=tmp[i]=read(),bel[i]=(i-1)/block+1;

		if(bel[i]!=bel[i-1])R[bel[i-1]]=i-1,L[bel[i]]=i;

	}R[bel[n]]=n;

	sort(tmp+1,tmp+n+1);

	cnt=unique(tmp+1,tmp+n+1)-tmp-1;

	for(int i=1;i<=n;i++)

		v[i]=lower_bound(tmp+1,tmp+cnt+1,v[i])-tmp;

	for(int i=n;i;i--) {

		ans+=T[0].query(v[i]-1);

		T[0].add(v[i],1);

		T[bel[i]].add(v[i],1);

	}

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

	m=read();

	while(m--) {

		int l=read(),r=read();

		if(r<l)swap(l,r);

		if(bel[l]==bel[r]) {

			for(int i=l+1;i<r;i++)

				check(i,l,r);

		}

		else {

			for(int i=l+1;i<=R[bel[l]];i++)

				check(i,l,r);

			for(int i=L[bel[r]];i<r;i++)

				check(i,l,r);

			for(int i=bel[l]+1;i<bel[r];i++) {

				ans-=T[i].query(v[l]-1);

				ans+=T[i].query(cnt)-T[i].query(v[l]);

				ans+=T[i].query(v[r]-1);

				ans-=T[i].query(cnt)-T[i].query(v[r]);

			}

			T[bel[l]].add(v[l],-1),T[bel[l]].add(v[r],1);

			T[bel[r]].add(v[l],1),T[bel[r]].add(v[r],-1);

		}

		if(v[l]>v[r])ans--;

		if(v[l]<v[r])ans++;

		swap(v[l],v[r]);

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

	}

	return 0;

}

巴特西

BZOJ2141：排队

最新文章

热门文章