COGS1871 [国家集训队2011]排队(魏铭)

bzoj:http://www.lydsy.com/JudgeOnline/problem.php?id=2141

cogs:http://cogs.pro:8080/cogs/problem/problem.php?pid=1871

这题和动态逆序对有点像

这题有些小卡常

首先用树套树维护值域，然后求出初始逆序对数，修改只需修改被影响的

当然可以每次减去与a,b构成的逆序对再修改再加回去，但显然常数飞起

修改操作分类讨论

交换\(h_a,h_b(a<b)\):

\(h_a=h_b\)：

你在逗我。

\(h_a<h_b\)：

两边的不用管。
首先a和b会产生1个逆序对
不在区间\([a,b]\)里的和在区间里的没有变动。
再讨论\(h\)：
\(h_i=h_a\) ：原来没有，之后与\(h_b\)产生了一个。对于此类的++ans。
\(h_i=h_b\) ：原来没有，之后与\(h_a\)产生了一个。对于此类的++ans。
\(h_i\in(h_a,h_b)\) ：原来没有，之后与\(h_a\)和\(h_b\)都产生了一个。对于此类的ans+=2。
剩下的：没变化。

\(h_a>h_b\)：

与上一种情况类似，自己YY把，懒得写了。

直接上代码吧：

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define il inline

#define rg register

#define vd void

#define sta static

#define lb(o) ((o)&-(o))

typedef long long ll;

il int gi(){

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

	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

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

	return x*f;

}

const int maxn=20001;

int h[maxn],H[maxn];

int root[maxn],ls[2333333],rs[2333333],sum[2333333],id;

#define mid ((l+r)>>1)

il vd Update(int&x,int l,int r,const int&p,const int&k){

	if(!x)x=++id;sum[x]+=k;

	if(l==r)return;

	if(p<=mid)Update(ls[x],l,mid,p,k);

	else Update(rs[x],mid+1,r,p,k);

	sum[x]=sum[ls[x]]+sum[rs[x]];

}

il int Query(const int&x,int l,int r,const int&L,const int&R){

	if(L<=l&&r<=R)return sum[x];

	if(!x||R<l||r<L||!sum[x]||L>R)return 0;

	return Query(ls[x],l,mid,L,R)+Query(rs[x],mid+1,r,L,R);

}

int main(){

	freopen("nt2011_queue.in","r",stdin);

	freopen("nt2011_queue.out","w",stdout);

	int n=gi(),m,q,a,b;

	for(rg int i=1;i<=n;++i)h[i]=H[i]=gi();

	std::sort(H+1,H+n+1);m=std::unique(H+1,H+n+1)-H-1;

	for(rg int i=1;i<=n;++i)h[i]=std::lower_bound(H+1,H+m+1,h[i])-H;

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

		for(rg int j=i;j<=n;j+=lb(j))

			Update(root[j],1,m,h[i],1);

	long long ans=0;

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

		for(rg int j=i-1;j;j-=lb(j))

			ans+=Query(root[j],1,m,h[i]+1,m);

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

	q=gi();while(q--){

		a=gi(),b=gi();

		if(a>b)std::swap(a,b);

		if(h[a]<h[b]){

			++ans;

			for(rg int j=b-1;j;j-=lb(j))ans+=Query(root[j],1,m,h[a],h[b])+Query(root[j],1,m,h[a]+1,h[b]-1);

			for(rg int j= a ;j;j-=lb(j))ans-=Query(root[j],1,m,h[a],h[b])+Query(root[j],1,m,h[a]+1,h[b]-1);

		}else if(h[a]>h[b]){

			--ans;

			for(rg int j=b-1;j;j-=lb(j))ans-=Query(root[j],1,m,h[b],h[a])+Query(root[j],1,m,h[b]+1,h[a]-1);

			for(rg int j= a ;j;j-=lb(j))ans+=Query(root[j],1,m,h[b],h[a])+Query(root[j],1,m,h[b]+1,h[a]-1);

		}

		for(rg int j=a;j<=n;j+=lb(j))Update(root[j],1,m,h[a],-1),Update(root[j],1,m,h[b],1);

		for(rg int j=b;j<=n;j+=lb(j))Update(root[j],1,m,h[b],-1),Update(root[j],1,m,h[a],1);

		std::swap(h[a],h[b]);

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

	}

	return 0;

}

巴特西

COGS1871 [国家集训队2011]排队(魏铭)

最新文章

热门文章