5222. 【GDOI2018模拟7.12】A

Description

Input

Output

Sample Input

3 2
2 3 1
1
1      

Sample Output

2
1
1      

Data Constraint

Hint

 Solution

  這道題要用到逆序對和權值線段樹的知識。                                                                                                                                                 首先，我們可以發現一個重要的性質：因為一個數的逆序對個數是在它後面且比它要小的數，是以當我們對一個數進行操作時，所有在它後面且比它大的數對逆序對總數的貢獻是不變的，而在它後面且比它小的數的逆序對的數量就永遠是0了，因為這些數已經被排過序了，而這些數後面的數要麼是排過序的(是以比它大)要麼是大于被操作的數的(而被排序的這些數一定是小于被操作數)。是以我們就可以找出每個位置最早對答案沒有貢獻的時刻，就可以統計每個時刻的逆序對數量了。怎麼做呢？令t[i]表示第i個位置最早被操作的時間(重複操作對答案沒有像影響)，一個位置i的逆序對的貢獻變為0的最早的時刻就是它或它前面比它大的點中最早被操作的時刻。是以我們可以從左到右掃一遍整個數列，插入目前的點的被操作時間并查找它即比它大的數的最早被操作時間，即目前點的貢獻變為0的時刻，time，這個可以用權值線段樹來維護。最後設sum[i]表示在所有第i個時刻貢獻變為0的數的逆序對個數(即它與它後面的數的逆序對個數)，每次sum[time]就加上第i個點的逆序對個數，再統計出逆序對總個數tot，1到m枚舉時刻每個時刻i就将tot-sum[i]輸出就行了。注意：每個位置的逆序對個數可在歸并求整個數列的逆序對總數時一并統計。

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define N 100010
#define ll long long
ll n,m,ma,q[N],a[N],b[N],c[N],d[N],t[N],s[N],iq[N],f[N*19],id[N],tm,ans[N],cnt,tot;
using namespace std;
void nxd(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	nxd(l,mid);nxd(mid+1,r);
	int i=l,j=mid+1,k=i;
	while(i<=mid||j<=r){
		if(a[i]<=a[j]&&i<=mid||j>r){
			ans[c[i]]+=j-mid-1;
			ans[0]+=j-mid-1;
			b[k]=a[i];d[k]=c[i];k++;i++;
		}
		else{b[k]=a[j];d[k]=c[j];k++;j++;}
	}
	for(int i=l;i<=r;i++){a[i]=b[i];c[i]=d[i];}
}
void add(int x,int l,int r,int k,ll p){
	if(l==r){f[x]=min(f[x],p);return;}
	int mid=(l+r)>>1;
	if(k<=mid) add(x*2,l,mid,k,p);
	else add(x*2+1,mid+1,r,k,p);
	f[x]=min(f[x*2],f[x*2+1]);
}
void find(int x,int l,int r,int l1,int r1){
	if(l==l1&&r==r1){tm=min(tm,f[x]);return;}
	int mid=(l+r)>>1;
	if(r1<=mid) find(x*2,l,mid,l1,r1);
	else if(l1>mid) find(x*2+1,mid+1,r,l1,r1);
	else{find(x*2,l,mid,l1,mid);find(x*2+1,mid+1,r,mid+1,r1);}
}
int main(){
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++){
		scanf("%lld",&a[c[i]=i]);
		ma=max(ma,iq[i]=a[i]);
	} 
	nxd(1,n);
	for(i=1;i<=n;i++){if(a[i]!=a[i-1]) id[c[i]]=++cnt;else id[c[i]]=cnt;}
	memset(f,127,sizeof(f));
	memset(t,127,sizeof(t));
	for(i=1;i<=m;i++){
		scanf("%lld",&q[i]);
		if(t[q[i]]==t[0]) t[q[i]]=i;
	}
	for(i=1;i<=n;i++){
		tm=m+1;
		add(1,1,n+1,id[i]+1,t[i]);
		find(1,1,n+1,id[i]+1,n+1);
		s[tm]+=ans[i];
	}
	printf("%lld\n",ans[0]);
	for(i=1;i<=m;i++){
		ans[0]-=s[i];
		printf("%lld\n",ans[0]);
	}
	return 0;
}
           

作者：zsjzliziyang 

QQ:1634151125 

轉載及修改請注明 

本文位址: https://blog.csdn.net/zsjzliziyang/article/details/84887133