poj1990两个树状数组

垃圾poj交不上去

/*
按权值从小到大排序,
两个树状数组维护权值小于等于并且在i左边的点的个数和权值
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 20005
#define ll long long
struct node{
int w,x;
bool operator<(const node & a)const {
return w<a.w;
}
}a[maxn];
int n;
ll bitcnt[maxn],bittot[maxn],sum;
void add1(int x,int val){//bitcnt
for(int i=x;i<=;i+=i&-i)
bitcnt[i]+=val;
}
void add2(int x,int val){//bittot
for(int i=x;i<=;i+=i&-i)
bittot[i]+=val;
}
ll query1(int x){
ll res=;
for(int i=x;i;i-=i&-i)
res+=bitcnt[i];
return res;
}
ll query2(int x){
ll res=;
for(int i=x;i;i-=i&-i)
res+=bittot[i];
return res;
} int main(){
while(scanf("%d",&n)==){
memset(bitcnt,,sizeof bitcnt);
memset(bittot,,sizeof bittot);
sum=; for(int i=;i<n;i++) scanf("%d%d",&a[i].w,&a[i].x);
sort(a,a+n); ll ans=;
for(int i=;i<n;i++){
ll left_node=query1(a[i].x);
ll left_total=query2(a[i].x); ans+=a[i].w*(left_node*a[i].x-left_total);
ans+=a[i].w*((sum-left_total-(i-left_node)*a[i].x));
sum+=a[i].x;
add1(a[i].x,);
add2(a[i].x,a[i].x);
}
printf("%lld\n",ans);
}
return ;
}
上一篇:EC笔记:第三部分:17、使用独立的语句将newed对象放入智能指针


下一篇:Android中ListView放入PopupWindow产生问题解决