[bzoj5055]-膜法师

发布于 2018-02-27  133 次阅读



题目(BZOJ) *权限
题面(vjudge)
 
这题其实很水......
只需要锁定aj,在前面找小于aj的总和,在后面找大于aj的总和,乘起来就可以了。
这个过程需要树状数组维护。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const ll mod=19260817;
const int N=300050;
int n;
ll a[N],c[N];int b[N];
ll ans;
ll c1[N],c2[N];
inline int lowbit(int x){return x&(-x);}
inline void ins1(int x,ll v){while(x<=n){c1[x]+=v;c1[x
inline void ins2(int x,ll v){while(x<=n){c2[x]+=v;c2[x
inline ll q1(int x){ll ret=0;while(x){ret+=c1[x];re
inline ll q2(int x){ll ret=0;while(x){ret+=c2[x];re
int main(){
	read(n);
	for(int i=1;i<=n;++i)read(a[i]),c[i]=a[i];
	sort(c+1,c+n+1);
	for(int i=1;i<=n;++i)b[i]=lower_bound(c+1,c+n+1,a[i])-c;
	for(int i=1;i<=n;++i)ins1(n-b[i]+1,a[i]);
	for(int i=1;i<=n;++i){
		ins1(n-b[i]+1,-a[i]);
		ans+=q1(n-b[i]
		an
		ins2(b[i],a[i]);
	}
	printf(
	return 0;
}