MooFest

考验你对于树状数组单点修改区间查询的理解...

for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            ans+=abs(a[i].x-a[j].x)*max(a[i].v,a[j].v);
        }
    }

题目的要求是你对于这个表达式子的优化,我们先尝试去掉max,就将结构体的式子按v进行排序即可.然后我们用树状数组来维护x,具体怎么维护呢,我们肯定是要快速求出,假如我当前这个位子是a[i].x,我们肯定要快速求出a[i].x前面有多少个是小于它的,且还要知道前面那些数的和,同理我们也得知道后面有多少个是大于他的,至于后面的个数之和就是i-前面的和-1.emmm/具体看代码.

/*
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e4+5;
struct vv{
    int v,x;
}a[N];
int bit[N+5][2];//0统计个数,1统计权值...
bool cmp(vv a,vv b)
{
    return a.v<b.v;
}

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

void insert(int pos,int val,int op)
{
    while(pos<=2e4)
    {
        bit[pos][op]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos,int op)
{
    int res=0;
    while(pos>0)
    {
        res+=bit[pos][op];
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].v,&a[i].x);
    }
    long long ans=0;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        long long  cnt,val;
        cnt=query(a[i].x,0);
        val=query(a[i].x,1);
        ans+=a[i].v*(cnt*a[i].x-val);
        //比它小的答案.
        cnt=i-1-cnt;
        val=query(20000,1)-val;
        ans+=a[i].v*(val-cnt*a[i].x);
        //比它大的答案.
        insert(a[i].x,1,0);
        insert(a[i].x,a[i].x,1);
        //处理当前位子.
    }
    cout<<ans<<endl;
    return 0;
}

最后说一下,那个poj编译是真的emmmm,把我这50多行的头文件全没了...注意数据要开long long不然会wa的...