10.29 T2 magic 逆序对+前缀和

思路

1. 先特判掉-1，-2
2. 如何？？ 对a和b分别求一下前缀和，如果sum[i]==sum[i+k]则说明这个区间（i-k）和为0
3. 考虑修改其实就是把a的前缀和相邻两个元素交换顺序
4. 那么问题转化为把1-n的排列a通过最少的交换次数得到给定的排列b，求最少方案数
5. 这个问题用树状数组求（或归并排序）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll read()
{
	char ch=' ';
	ll f=1;ll x=0;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=x*10+ch-'0';ch=getchar();
	}
	return x*f;
}
const ll N=1e5+100;
ll a[N],b[N],s1[N],s2[N],s3[N],s4[N];
ll x[N],y[N];
ll c[N];
ll lb(ll x)
{
	return x&(-x);
}
void modify(ll x)
{
	for(ll i=x;i<=N;i+=lb(i))
	{
		c[i]++;
	}
}
ll query(ll x)
{
	ll ret=0;
	for(ll i=x;i>=1;i-=lb(i))
	{
		ret+=c[i];
	}
	return ret;
}
int main()
{
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	ll n;
	n=read();
	ll i,j;
	s1[0]=0;
	for(i=1;i<=n;i++)
	{
		a[i]=read();
		s1[i]=s1[i-1]+a[i];
	}
	for(i=1;i<=n;i++)
	{
		b[i]=read();
		s2[i]=s2[i-1]+b[i];
	}
	sort(s1+1,s1+1+n);
	sort(s2+1,s2+1+n);
	bool flag1=0;
	bool flag2=0;
	for(i=1;i<=n;i++)
	{
		if(s1[i-1]==s1[i]||s2[i-1]==s2[i])
		{
			flag1=true;
		}
		if(s1[i]!=s2[i])
		{
			flag2=true;
		}
		if(flag1&&flag2)
		{
			break;
		}
	}
	if(flag1)
	{
		cout<<"-1"<<endl;
		return 0;	
	}
	if(flag2)
	{
		cout<<"-2"<<endl;
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		s3[i]=s3[i-1]+a[i];
	}
	for(i=1;i<=n;i++)
	{
		s4[i]=s4[i-1]+b[i];
	} 
	for(i=1;i<=n;i++)
	{
		ll pos=lower_bound(s1+1,s1+1+n,s3[i])-s1;
		x[pos]=i;
	}
	for(i=1;i<=n;i++)
	{
		ll pos=lower_bound(s2+1,s2+1+n,s4[i])-s2;
		y[i]=x[pos];
	}
	ll cnt=0;
	for(i=1;i<=n;i++)
	{
		ll tmp=n-y[i]+1;
		modify(tmp);
		cnt+=query(tmp-1);
	}
	cout<<cnt<<endl;
	return 0;
}