http://www.zybbs.org/JudgeOnline/problem.php?id=1145

R1……好高兴……

要求的是f[1324]-f[1243]-f[1432]。注意到：

f[1324]-f[1243]-f[1432]

=(f[1x2x]-f[1423])-(f[12xx]-f[1234])-(f[14xx]-f[1423])

=f[1x2x]+f[1234]+f[13xx]-f[1xxx]

这四个都可以用树状数组来解，其中f[13xx]和f[1x2x]比较难想，我的方法可能和另一些题解不同。

f[1x2y]是将所有数字从小到大放进数组并维护所有在它之前的数的个数。

考虑某个数是2的情况。此时1已经被插入，xy还未被插入。我们要查询的就是对于所有的1，在1到2之间所有的x的和，乘以y。y很好求，关键在于x。我们可以在插入1的时候将在1左边的数（包括1即1的位置）的个数插入，此时对于2，维护的前缀和就变成了所有的1左边的数的个数之和。再来看1的个数与2左边的数（包括2即2的位置）之积，这个积与x有什么关系呢？多算了两样东西，一个就是1左边的数的个数之和，这个刚才维护过了。第二个就是对于某个1，在1和2之间的另一个1（包括2）也要减掉。对于最右边那个1，要减掉1；对于倒数第二个1，要减掉2……总共要减掉x(x+1)/2个1。完毕。

f[13xx]是将所有数字从左到右放进数组并直接维护子段和。

对于3，1就不说了。两个x只要用2*4就可以，4也很好求，关键在于2。在插入1的时候将比小于等于1的数（即1的大小）也插入，这样对于3就可以得到对于所有1小于等于1的数的个数之和。观察在3左边比3小的数与小于等于3的数之积，与132比较也多算了两样东西，一个就是对于所有1小于等于1的数的个数之和，这个刚才算过了。另一个就是形如123的样子（2可能与3重合）。对于最右边那个1，要减掉1；对于倒数第二个1，要减掉2……总共要减掉x(x+1)/2个1。完毕。

#include <stdio.h>
int n,a[200001],p[200001],t[5][200001],ans=0,re;
__inline void Insert(i,x,y){for(;x;x-=x&-x)t[i][x]+=y;}
__inline Find(i,x){for(re=0;x<=n;x+=x&-x)re+=t[i][x];return re;}
__inline getint(){
	char ch=getchar();
	for(re=0;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}main(){
	int i,y,z;long long x;
	for(n=getint(),i=1;i<=n;i++){
		x=(z=Find(0,y=n+1-a[p[a[i]=getint()]=i]))+y-i;
		ans=ans+x*Find(1,y)-x*(x-1)*(x-2)/6+x*(z*a[i]-Find(2,y)-(z*(z+1)>>1))&16777215;
		Insert(0,y,1),Insert(1,y,z),Insert(2,y,a[i]);
	}for(i=1;i<=n;i++){
		x=Find(3,y=n+1-p[i]);
		ans=ans+(x*p[i]-Find(4,y)-((x*(x+1))>>1))*(x+y-i)&16777215;
		Insert(3,y,1),Insert(4,y,p[i]);
	}printf("%d\n",ans&16777215);
	return 0;
}

• inline
• block