bzoj1145[CTSC2008]图腾

传送门

虽然是远古时期的ctsc，但是果然还是ctsc啊

前置芝士：树状数组

这个题最开始的思路很好想，由于之前写过一个类似处理的题，所以这个题我一开始就想到了思路。

首先，我们可以尝试讲图腾表示为xxxx的形式

那么闪电就是：1324；高山是：1243和1432

ans=1324-1243-1432

然后应该容斥一下，但是我不会了。。

瞄一眼题解，我成功吧那个式子容斥出来了。

ans=1324-1243-1432

ans=(1x2x-1423)-(14xx-1423)-(12xx-1234)

ans=1x2x-14xx-12xx+1234

ans=1x2x-1xxx+13xx+1234

然后我就震惊的发现，我又不会了，这次变成仔细的研究题解了，各种讨论情况啊，nb啊，大佬们

下面的讨论情况还是看洛谷题解的吧，太难写了。题解传送门

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

void read(int &x) {

	char ch; bool ok;

	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

#define rg register

#define lowbit(i) (i&(-i))

#define ls (get(a[i]))

#define rs (a[i]-1-ls)

#define lb (i-1-l[i])

#define rb (n-i-r[i])

const int mod=16777216,maxn=2e5+1;

int n,ans,a[maxn],f[maxn],now,l[maxn],r[maxn];

void add(int x,int y){for(rg int i=x;i<=n;i+=lowbit(i))(f[i]+=y)%=mod;}

int get(int x){int ans=0;for(rg int i=x;i;i-=lowbit(i))ans+=f[i];return ans;}

int C(int n,int m){return 1ll*n*(n-1)*(n-2)/6%mod;}

int main()

{

	read(n);

	for(rg int i=1;i<=n;i++)read(a[i]),l[i]=ls,r[i]=a[i]-1-l[i],add(a[i],1);

	memset(f,0,sizeof f);

	for(rg int i=1;i<=n;i++)

	{

		ans=((ans+(l[i]*(i-1)-get(a[i])-l[i]*(l[i]-1)/2)*rb)%mod+mod)%mod,

		ans=((ans-C(rb,3))%mod+mod)%mod;

		add(a[i],i);

	}

	memset(f,0,sizeof f);

	for(rg int i=n;i;i--)ans=((ans+(1ll*get(a[i])-1ll*r[i]*(r[i]-1)/2)*rb)%mod+mod)%mod,add(a[i],a[i]-1);

	memset(f,0,sizeof f);now=0;

	for(rg int i=1;i<=n;i++)ans=(ans+1ll*rb*get(a[i]))%mod,add(a[i],l[i]);

	printf("%d\n",ans);

}

巴特西

bzoj1145[CTSC2008]图腾

传送门

前置芝士：树状数组

最新文章

热门文章