vijos1459 车展

treap求中位数。

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, rot, siz, uu, vv;
ll h[1005], all, num, tmp, ans[1005][1005], cnt;
struct Node{
	int l, r, rnd, sze, hav;
	ll val, sum;
}nd[1005];
void upd(int k){
	nd[k].sze = nd[nd[k].l].sze + nd[nd[k].r].sze + 1;
	nd[k].sum = nd[nd[k].l].sum + nd[nd[k].r].sum + nd[k].val;
}
void lRotate(int &k){
	int t=nd[k].r; nd[k].r = nd[t].l; nd[t].l = k;
	nd[t].sze = nd[k].sze; upd(k); upd(t); k = t;
}
void rRotate(int &k){
	int t=nd[k].l; nd[k].l = nd[t].r; nd[t].r = k;
	nd[t].sze = nd[k].sze; upd(k); upd(t); k = t;
}
void ins(int &k, ll x){
	if(!k){
		k = ++siz; nd[k].sze = nd[k].hav = 1;
		nd[k].val = nd[k].sum = x; nd[k].rnd = rand();
		nd[k].l = nd[k].r = 0;
		return ;
	}
	nd[k].sze++;
	nd[k].sum += x;
	if(nd[k].val==x)	nd[k].hav++;
	else if(nd[k].val<x){
		ins(nd[k].r, x);
		if(nd[nd[k].r].rnd<nd[k].rnd)	lRotate(k);
	}
	else{
		ins(nd[k].l, x);
		if(nd[nd[k].l].rnd<nd[k].rnd)	rRotate(k);
	}
}
ll queryNum(int k, int x){
	if(!k)	return 0;
	if(nd[nd[k].l].sze>=x)	return queryNum(nd[k].l, x);
	else if(nd[nd[k].l].sze+nd[k].hav<x){
		num += nd[nd[k].l].sze + nd[k].hav;
		tmp += nd[nd[k].l].sum + nd[k].val * nd[k].hav;
		return queryNum(nd[k].r, x-nd[nd[k].l].sze-nd[k].hav);
	}
	else{
		num += nd[nd[k].l].sze;
		tmp += nd[nd[k].l].sum;
		return nd[k].val;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++)	scanf("%lld", &h[i]);
	for(int i=1; i<=n; i++){
		rot = all = siz = 0;
		for(int j=i; j<=n; j++){
			all += h[j];
			ins(rot, h[j]);
			num = tmp = 0;
			ll zws=queryNum(rot, (j-i+2)/2);
			ans[i][j] += num * zws - tmp;
			ans[i][j] += all - tmp - (j-i+1-num) * zws;
		}
	}
	for(int i=1; i<=m; i++){
		scanf("%d %d", &uu, &vv);
		cnt += ans[uu][vv];
	}
	cout<<cnt<<endl;
	return 0;
}