膜法师

wjh15101051's space

卧薪尝胆，厚积薄发。

膜法师

Date: Wed Oct 10 14:04:56 CST 2018

In Category: NoCategory

Description：

求出所有满足 $i<j<k$ 且 $a_i<a_j<a_k$ 的 $a_i\times a_j\times a_k$ 的和。

$1\leqslant n\leqslant 300000$

Solution：

先用树状数组统计一下每个 $a_j$ 的 $a_i\times a_j$ ，然后再统计一遍就好了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 300010

int a[MAXN];

int s[MAXN];

int v[MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

int tot = 0;

int lowbit(int x){return x & (-x);}

#define MOD 19260817

long long c[MAXN];

void add(int p,long long x){for(int i = p;i <= tot;i += lowbit(i))c[i] = (c[i] + x) % MOD;return;}

long long query(int p){long long res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = (res + c[i]) % MOD;return res;}

long long f[MAXN],g[MAXN];

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i]);

		s[i] = i;

	}

	sort(s + 1,s + 1 + n,cmp);

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

	{

		if(i == 1 || a[s[i]] != a[s[i - 1]])

			v[s[i]] = ++tot;

		else v[s[i]] = tot;

	}

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

	{

		f[i] = a[i] * query(v[i] - 1) % MOD;

		add(v[i],a[i]);

	}

	memset(c,0,sizeof(c));

	int ans = 0;

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

	{

		g[i] = a[i] * query(v[i] - 1) % MOD;

		add(v[i],f[i]);

		ans = (ans + g[i]) % MOD;

	}

	cout << ans << endl;

	return 0;

}

In tag: 数据结构-树状数组

wjh15101051