POJ1990 MooFest
USACO U S Openの問題。数直線上に点がN点与えられ、それらの2点の間のコストが(その間の距離)*(2点の持つ値の大きい方)で定められているので、すべての2点間のコストの総和を求める。
BITを2個持っておいてやって、"座標の合計"と"そこまでにある点の数"を持っておくと通る。
long long トラップが存在して…
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll bit[32769]; ll bit2[32769]; void add(ll a,ll b) { for(;;) { bit[a]+=b; a+=a&-a; if(a>32768) { break; } } } ll sum(ll a) { ll ret=0; for(;;) { ret+=bit[a]; a-=a&-a; if(a==0) { break; } } return ret; } void add2(ll a,ll b) { for(;;) { bit2[a]+=b; a+=a&-a; if(a>32768) { break; } } } ll sum2(ll a) { ll ret=0; for(;;) { ret+=bit2[a]; a-=a&-a; if(a==0) { break; } } return ret; } typedef pair<ll,ll>pii; int main() { int num; scanf("%d",&num); vector<pii>vec; for(int i=0;i<num;i++) { ll za,zb; scanf("%lld%lld",&za,&zb); vec.push_back(make_pair(za,zb)); add(zb,zb); add2(zb,1); } sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); ll ret=0; for(int i=0;i<num;i++) { ll now=0; now+=sum2(vec[i].second-1)*vec[i].second-sum(vec[i].second-1); now+=(sum(32768)-sum(vec[i].second))-(sum2(32768)-sum2(vec[i].second))*vec[i].second; ret+=now*vec[i].first; add(vec[i].second,-vec[i].second); add2(vec[i].second,-1); } printf("%lld\n",ret); }