T1

假设交换了 \(a[i]\) 和 \(a[i+1]\) ，那么 \(a[1...i-1]\) ， \(a[i+2...n]\) 与这两个数构成的逆序对不变。只有 \(a[i]\) 和 \(a[i+1]\) 两个数构成的逆序对可能发生改变。

如果 \(a[i]<a[i+1]\) ，那么逆序对个数加\(+1\)；如果 \(a[i]=a[i+1]\) ，那么逆序对个数不变；如果 \(a[i]>a[i+1]\) ，那么逆序对个数\(-1\)。

另外，此题需要特别注意：当 \(n=1e6\) 时，逆序对个数最多可能为 \(n\times (n-1)/2\) ，需要用\(long\) \(long\)。

\(code:\)

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,c,ans,x,a[1000005];
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&c);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	for(int i=1;i<=m;++i){
		scanf("%lld",&x);
		if(a[x]<a[x+1])
			++c;
		else if(a[x]>a[x+1])
			--c;
		ans^=c;
		swap(a[x],a[x+1]);
	}
	printf("%lld\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}

T2

不难发现，如果存在逆序对，那么最近的逆序对距离一定是1。所以只需要检查这个数列是否存在逆序对，即是否不单调递增即可。

\(code:\)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,a[5];
int read(){
	char g;int w=0,f=1;bool ok=0;
	while(1){
		g=getchar();
		if(g=='-')
			ok=1,f=-1;
		else if(g>='0'&&g<='9')
			ok=1,w=w*10+f*(int)(g-'0');
		else if(ok) break;
	}
	return w;
}
int main(){
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int ok=0;
		for(int i=1;i<=n;++i){
			a[i&1]=read();
			if(i!=1&&a[i&1]<a[(i-1)&1])
				ok=1;
		}
		printf("%d\n",ok);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}

T3

对于一个数 \(a[i]\) ，设 \(a[j](j>i)\) 是整个数列中最靠后的小于 \(a[i]\) 的数。此时 \(a[i]\) 与 \(a[j]\) 能够连边。对于任意的 \(k(i<k<j)\) ：① \(a[k]<a[j]<a[i]\) ，此时 \(i\) 和 \(k\) 能连边；② \(a[j]<a[k]\) ，此时 \(j\) 和 \(k\) 能连边。综上，我们发现： \([i,j]\) 中的所有数一定处在一个联通块中。

首先预处理一个数组 \(minn[i]\) ，表示 \([i,n]\) 中所有数的最小值。

接下来扫描这个序列。设当前的数下标为 \(i\) ， \(t\) 为当前数所在联通块的右端点。

当 \(i>t\) 时，说明当前的数已经离开了上一个联通块，出现了一个新联通块。

之后从 \(t\) 开始扫描后面的数，设扫描的数为 \(j\) ，直到 \(minn[j]<=a[i]\&\&minn[j+1]>a[i]\) 时停止循环，并用 \(j\) 更新 \(t\) 。因为此时 \(a[j]\) 是整个数列中最靠后的小于 \(a[i]\) 的数，\([i,j]\) 中的所有数一定处在一个联通块中，导致 \(i\) 所处的联通块得以扩充。

\(code:\)

#include<iostream>
#include<ctime>
#include<cstdio>
using namespace std;
int n,a[5000005],ans,t,minn[5000005],st=clock();
int read() {
    int s=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')	{if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
    return s*f;
}
int main(){
	//freopen("block.in","r",stdin);
	//freopen("block.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		a[i]=read();
	minn[n]=a[n];
	if(minn[n]<=a[1])
		printf("1\n");
	else{
		for(int i=n-1;i>=1;--i){
			minn[i]=min(minn[i+1],a[i]);
			if(!t&&minn[i]<=a[1]&&minn[i+1]>a[1])
				t=i;
		}
		ans=1;
		for(int i=2;i<=n;++i){
			if(i>t){
				++ans;t=i;
			}
			for(int j=t;j<=n;++j){
				if(j==t&&minn[j]>a[i])
					break;
				if((minn[j]<=a[i]&&minn[j+1]>a[i])||(j==n&&minn[j]<=a[i])){
					t=j;break;
				}
			}
		}
		printf("%d\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}

T4(50pts)

首先不难想到朴素的DP：设 \(f[i][j]\) 表示前 \(i\) 个数，逆序对个数为 \(j\) 的方案数。对于第 \(i\) 个数，它与前面的数可以构成 \(0\) 或 \(1\) 或 \(2\) ...或 \(i-1\) 个逆序对。因此 \(f[i][j]\) 可以由 \(f[i-1][k](max(j-i+1,0)<=k<=j)\) 转移而来。状态转移方程：\(f[i][j]= \sum f[i-1][k](max(j-i+1,0)<=k<=j)\)。时间复杂度\(O(n^3)\)。

接下来考虑优化。设当\(for\) 循环到 \(j\) 时， \(s= \sum f[i-1][k](max(j-i+1,0)<=k<=j)\)。那么当\(for\) 循环到 \(j-1\) 时， \(s= \sum f[i-1][k](max(j-i,0)<=k<=j-1)\) ，只需令此时的 \(s\) 加上 \(f[i-1][j]-f[i-1][j-i]\) ，即可得到 \(j\) 时的 \(s\) ，然后直接用 \(s\) 更新 \(f[i][j]\) 。时间复杂度\(O(n^2)\)。

\(code:\)

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,f[2][1000005],s;
const long long mod=1e9+7;
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		s=0;
		for(int j=0;j<=m;++j){
			if(j-i>=0)
				s=(s-f[(i-1)&1][j-i]+mod)%mod;
			s=(s+f[(i-1)&1][j])%mod;
			f[i&1][j]=s%mod;
		}
  	}
	printf("%lld\n",f[n&1][m]%mod);
	fclose(stdin);fclose(stdout);
	return 0;
}