[vijos1459][车展]

题目链接

思路

首先可以证明当这个高度是中位数的时候耗费时间是最少了。所以可以(n^2log(n))用一个treap预处理出每个区间的中位数。
然后就是知道了中位数怎么计算答案的问题。
然后发现暴力n*m的扫能过而且跑的还不慢
但是作为一个正直善良的OIER我还是用(n^2log(n))做的。
发现用中位数减去比他小的在加上比中位数大的减去中位数，恰好可以把中位数给抵消掉(并不是都可以完全抵消掉，这个可以根据中位数的位置算一下)，然后发现其实就是用那些比中位数大的数减去比中位数小(或者等于)的数，要不要再加回来一个中位数要特判一下。

代码

//寻找每个区间内的中位数
/*
* @Author: wxyww
* @Date:   2018-12-02 10:36:55
* @Last Modified time: 2018-12-02 14:22:15
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
using namespace std;
typedef long long ll;
const int N = 2010;
ll read() {
   ll x = 0,f = 1;char c = getchar();
   while(c < '0' || c > '9') {
      if(c == '-') f = -1;
      c = getchar();
   }
   while(c >= '0' && c <= '9') {
      x = x * 10 + c - '0';
      c = getchar();
   }
   return x * f;
}
struct node {
   int ch[2],id,val,siz,cnt;
   ll VAL;
   void CLEAR() {
      ch[1] = ch[0] = id = val = siz = cnt = VAL = 0;
   }
}TR[N];
void up(int cur) {
   TR[cur].siz = TR[ls].siz + TR[rs].siz + TR[cur].cnt;
   TR[cur].VAL = TR[ls].VAL + TR[rs].VAL + TR[cur].val * TR[cur].cnt;
}
void rotate(int &cur,int f) {
   int son = TR[cur].ch[f];
   TR[cur].ch[f] = TR[son].ch[f ^ 1];
   TR[son].ch[f ^ 1] = cur;
   up(cur);cur = son;up(cur);
}
int tot;
void insert(int &cur,int val) {
   if(!cur) {
      cur = ++tot;
      TR[cur].val = val;
      TR[cur].id = rand();
      TR[cur].siz = TR[cur].cnt = 1;
      TR[cur].VAL = val;
      TR[cur].ch[1] = TR[cur].ch[0] = 0;
      return;
   }
   if(val == TR[cur].val) {TR[cur].cnt++;TR[cur].siz++;TR[cur].VAL += val;return;}
   int d = val > TR[cur].val;
   insert(TR[cur].ch[d],val);
   up(cur);
   if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);
}
int kth(int cur,int now) {
   while(1) {
      if(now > TR[ls].siz + TR[cur].cnt) now -= TR[ls].siz + TR[cur].cnt,cur = rs;
      else if(now <= TR[ls].siz) cur = ls;
      else return TR[cur].val;
   }
}
int rt,n,a[N];
ll sum[N],ans[N][N];
ll find(int cur,int val) {
   if(!cur) return 0;
   if(val >= TR[cur].val) return find(rs,val) + TR[ls].VAL + TR[cur].val * TR[cur].cnt;
   return find(ls,val);
}
int main() {
   n = read();
   int m = read();
   for(int i = 1;i <= n;++i) a[i] = read(),sum[i] = sum[i-1] + a[i];
   for(int i = 1;i <= n;++i) {
      rt = tot = 0;
      for(int j = i;j <= n;++j) {
         insert(rt,a[j]);
         int z = kth(rt,(j - i + 2) / 2);
         ll k = find(rt,z);
         if((j - i) & 1)   ans[i][j] = sum[j] - sum[i-1] - k * 2;
         else ans[i][j] = sum[j] - sum[i-1] - k * 2 + z;
      }
   }
   ll anss = 0;
   while(m--) anss += ans[read()][read()];
   cout<<anss;
   return 0;
}

一言

易碎的 骄傲着 那也曾是我的模样。