树状数组Ⅱ

排序

由于指代不清(逆序对定义模糊)而变得十分坑人的一道题目,调了好久,更要命的是由于后来换用新定义且修改数据之后,题解区里所有代码都变得不具有参考价值了,这就很要命了……

闲言少叙。

这道题思路上和树状数组没太大关系,主要是逆序对那里要用一下树状数组,毕竟树状数组常数小【滑稽】……

首先可以发现一个看似无用却是整道题解题关键的结论,那就是随着询问次数增加,它的逆序对个数会越来越少,理由很简单,因为每一次操作都把这个数组向着完全有序的方向推动一点,逆序对自然就少了。

然后就想到找每次减少的这个量,找规律加上奇怪的推理就可以找出来。

还是调了两个小时,该死的定义。

#include<cstdio>
#include<algorithm>
//#define zczc
#define ll long long
using namespace std;
const int N=300010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}

int m,n,a[N],b[N];
ll an[N];
#define lowbit (wh&-wh)
ll t[N];
inline void change(int wh,ll val){
	for(;wh<=m;wh+=lowbit)t[wh]+=val;
	return;
}
inline ll work(int wh){
	ll an=0;
	for(;wh;wh-=lowbit)an+=t[wh];
	return an;
}
#undef lowbit

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);
	for(int i=1;i<=m;i++){
		read(a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+m+1);
	int num=unique(b+1,b+m+1)-b-1;
	for(int i=1;i<=m;i++){
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	}
	ll ans=0;
	for(int i=m;i;i--){
		an[a[i]]+=work(a[i]-1);
		ans+=work(a[i]-1);
		change(a[i],1);
	}
	
	printf("%lld\n",ans);
	int maxn=0,q;
	while(n--){
		read(q);
		if(a[q]>maxn){
			for(int i=maxn+1;i<=a[q];i++){
				ans-=an[i];
			}
			maxn=a[q];
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}
上一篇:大头照上传预览,并操作数据库和删除文件夹中存储的之前的图片;$_SERVER['DOCUMENT_ROOT']上传图片和删除图片的时候不要用绝对路径,可以用这个路径


下一篇:非线性整数规划模型(LINGO代码实现)