【[CQOI2011]动态逆序对】

这是我的第一个数据结构套数据结构

不是线段树套\(Splay\)，而是非常蛇皮的块状链表套树状数组

如果这里按照\(\sqrt{n}\)的大小来分块，那么就需要\(n\sqrt{n}\)的空间，可能开不下，于是我们按照\(1000\)分块，也就只会分出\(100\)个块，就能开下空间了

之后每一次查询的时候直接查询树状数组就好了，每次修改则非常的块，直接找到对应的块改动这个块的树状数组就好了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define lowbit(x) ((x)&(-x))

#define re register

#define maxn 100005

#define LL long long

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

int a[maxn],b[maxn];

int l[1005],r[1005],sz[1005];

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int c[maxn];

int bit[101][maxn];

int n,m,tot,len;

LL ans;

int to[maxn],vis[maxn];

inline void add(int x)

{

	for(re int i=x;i<=n;i+=lowbit(i))

		c[i]++;

}

inline int ask(int x)

{

	int now=0;

	for(re int i=x;i;i-=lowbit(i))

		now+=c[i];

	return now;

}

inline void get_pair()

{

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

	{

		ans+=ask(n)-ask(a[i]);

		add(a[i]);

	}

}

inline void B_add(int o,int x,int val)

{

	for(re int i=x;i<=n;i+=lowbit(i)) bit[o][i]+=val;

}

inline int B_ask(int o,int x)

{

	int now=0;

	for(re int i=x;i;i-=lowbit(i)) now+=bit[o][i];

	return now;

}

inline void build_block()

{

	len=1000;

	int k=1;

	while(k<=n)

	{

		l[++tot]=k;

		r[tot]=min(n,k+len-1);

		k=r[tot]+1;

		for(re int i=l[tot];i<=r[tot];i++)

			B_add(tot,a[i],1);

	}

}

inline int get_num(int x)

{

	if(x%len==0) return x/len;

	return x/len+1;

}

inline void BL_change(int x)

{

	vis[to[x]]=1;

	int now=get_num(to[x]);

	B_add(now,x,-1);

}

inline int BL_find_less(int x,int y,int val)

{

	int num=0;

	for(re int i=x;i<=y;i++)

		if(!vis[i]&&a[i]<val) num++;

	return num;

}

inline int BL_find_more(int x,int y,int val)

{

	int num=0;

	for(re int i=x;i<=y;i++)

		if(!vis[i]&&a[i]>val) num++;

	return num;

}

inline int find_less(int x,int y,int val)

{

	int num=0;

	for(re int i=1;i<=tot;i++)

	{

		if(x>l[i]&&y<r[i]) return BL_find_less(x,y,val);

		if(x<=l[i]&&y>=r[i]) num+=B_ask(i,val);

			else if(x<=l[i]&&y<r[i]) num+=BL_find_less(l[i],y,val);

				else if(y>=r[i]&&x>l[i]) num+=BL_find_less(x,r[i],val);

	}

	return num;

}

inline int find_more(int x,int y,int val)

{

	int num=0;

	for(re int i=1;i<=tot;i++)

	{

		if(x>l[i]&&y<r[i]) return BL_find_more(x,y,val);

		if(x<=l[i]&&y>=r[i]) num+=B_ask(i,n)-B_ask(i,val);

			else if(x<=l[i]&&y<r[i]) num+=BL_find_more(l[i],y,val);

				else if(y>=r[i]&&x>l[i]) num+=BL_find_more(x,r[i],val);

	}

	return num;

}

int main()

{

	n=read(),m=read();

	for(re int i=1;i<=n;i++) a[i]=read(),to[a[i]]=i;

	get_pair(),build_block();

	int x;

	while(m--)

	{

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

		x=read();

		if(to[x]!=1) ans-=find_more(1,to[x]-1,x);

		if(to[x]!=n) ans-=find_less(to[x]+1,n,x);

		BL_change(x);

	}

	return 0;

}

巴特西

【[CQOI2011]动态逆序对】

最新文章

热门文章