1145: [CTSC2008]图腾totem - #include <Seter> - using namespace Orz;

1145: [CTSC2008]图腾totem

Seter posted @ 2011年7月28日 14:38 in BZOJ with tags SegTree CTSC , 2764 阅读

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

 

RunID User Problem Result Memory Time Language Code Length Submit Time
141607 testSeter 1145 Accepted 6224 kb 1020 ms C/Edit 837 B 2011-08-12 18:39:59

 

No. RunID User Memory Time Language Code Length Submit Time
1 141607(6) testSeter 6224 KB 1020 MS C 837 B 2011-08-12 18:39:59

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;
}

 

By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee