题解 - Vijos

1

lxy8584099 LV 7 @ 2018-10-19 09:14:57

主席树查询k小值
然后暴力偏偏分

#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int N=1050;
int n,q,L[N<<2+5],R[N<<2+5],sum[N<<2+5];
int a[N+5],b[N+5],head[N+5],tot;
int build(int l,int r)
{
    int rt=++tot;
//  sum[rt]=0;
    if(l<r)
    {
        L[rt]=build(l,mid);
        R[rt]=build(mid+1,r);
    }
    return rt;
}
int add(int last,int l,int r,int k)
{
    int rt=++tot;
    L[rt]=L[last],R[rt]=R[last];
    sum[rt]=sum[last]+1;
    if(l<r)
    {
        if(k<=mid) L[rt]=add(L[last],l,mid,k);
        else R[rt]=add(R[last],mid+1,r,k);
    }
    return rt;
}
int find(int u,int v,int l,int r,int k)
{
    if(l>=r) return l;
    int x=sum[L[v]]-sum[L[u]];
    if(x>=k) return find(L[u],L[v],l,mid,k);
    else return find(R[u],R[v],mid+1,r,k-x);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    head[0]=build(1,m);
    for(int i=1;i<=n;i++)
    {
        int k=lower_bound(b+1,b+m+1,a[i])-b;
        head[i]=add(head[i-1],1,m,k);
    }
    ll all=0;
    while(q--)
    {
        int x,y,z;
        scanf("%d%d",&x,&y);
        z=b[find(head[x-1],head[y],1,m,(y-x+2)/2)];
        for(int i=x;i<=y;i++) all+=1LL*abs(z-a[i]);
    }
    printf("%lld\n",all);
    return 0;
}

1

sssSSSay LV 10 @ 2017-10-25 16:54:11

n ^ 2找中位数
用temp记录到当前位置比i位置的数多还是少，多多少，少多少。
i位置的数是某区间的中位数当且仅当整个区间比a[i]多的数等于比a[i]少的数。
记录一下前面的，去后面更新区间，vis[i][j]表示i到j的中位数。
思路参照楼下某大神

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

const int Maxn = 1010;

int n, m, t[Maxn][4], q[4][Maxn][Maxn];
ll a[Maxn], vis[Maxn][Maxn], ans;

ll Abs(ll a) {return a >= 0 ? a : -a;}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]), vis[i][i] = a[i];
    for(int i = 1; i <= n; ++i) {
        int temp = 0;
        memset(t, 0, sizeof t);
        for(int j = i; j >= 1; --j) {
            if(a[j] > a[i]) ++temp;
            else if(a[j] < a[i]) --temp;
            if(temp > 0) q[1][temp][++t[temp][1]] = j;
            else if(temp < 0) q[0][-temp][++t[-temp][0]] = j;
            else q[2][0][++t[0][2]] = j;
        }
        temp = 0;
        for(int j = i; j <= n; ++j) {
            if(a[j] > a[i]) ++temp;
            else if(a[j] < a[i]) --temp;
            if(temp > 0) for(int k = 1; k <= t[temp][0]; ++k) vis[q[0][temp][k]][j] = a[i]; 
            else if(temp < 0) for(int k = 1; k <= t[-temp][1]; ++k) vis[q[1][-temp][k]][j] = a[i];
            else for(int k = 1; k <= t[0][2]; ++k) vis[q[2][0][k]][j] = a[i];
        }
    }
    for(int i = 1; i <= m; ++i) {
        int x, y; ll mid; scanf("%d%d", &x, &y);
        if((y - x) & 1) mid = vis[x][y - 1];
        else mid = vis[x][y];
        for(int j = x; j <= y; ++j) ans += Abs(mid - a[j]);
    }
    cout << ans << endl;
    return 0;
}

0

Paul_Guderian LV 7 @ 2017-08-25 18:44:16

用Treap维护一下就好啦
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define ro(i,a,b) for(int i=a;i>=b;i--)
#define fo(i,a,x) for(int i=a[x];i;i=e[i].next)
#define mem(a,b) memset(a,b,Sizeof(a))
#define ll long long
using namespace std;
const int N=1003;
int n,m,root,sz=0,v,ch[N][2],Siz[N],P[N];
ll h[N],val[N],Mid,Sum[N],S[2],Time[N][N];
void Rotate(int &u,int d){ch[u][d]=ch[v=ch[u][d]][d^1];ch[v][d^1]=u;u=v;}
void Keep(int u)
{
Siz[u]=Siz[ch[u][0]]+Siz[ch[u][1]]+1;
Sum[u]=Sum[ch[u][0]]+Sum[ch[u][1]]+val[u];
}
void Insert(int &u,int V)
{
if(!u)
{

Siz[u=++sz]=1;
ch[u][0]=ch[u][1]=0;
Sum[u]=V;val[u]=V;P[u]=rand();return;
}
Siz[u]++;Sum[u]+=V;int d=val[u]<V;Insert(ch[u][d],V);
if(P[u]<P[ch[u][d]])Rotate(u,d),Keep(ch[u][d^1]),Keep(u);
}
void find(int u,int pos)
{
if(pos==Siz[ch[u][0]]+1)
{
S[1]+=Sum[ch[u][1]];
S[0]+=Sum[ch[u][0]];
Mid=val[u];
return;
}
int d=pos>Siz[ch[u][0]]+1;
S[d^1]+=Sum[ch[u][d^1]]+val[u];
find(ch[u][d],d?pos-Siz[ch[u][0]]-1:pos);
}
int main()
{

scanf("%d%d",&n,&m);
go(i,1,n)scanf("%d",&h[i]);
go(i,1,n)
{

go(j,i,n)
{
S[1]=S[0]=0;int l=1,r=j-i+1;
Insert(root,h[j]);int mid=l+r>>1;
find(root,mid);
Time[i][j]=(mid-l)*Mid-S[0]+S[1]-(r-mid)*Mid;

}
root=sz=0;
}
ll ans=0;int l,r;
while(m--&&scanf("%d%d",&l,&r))ans+=Time[l][r];
printf("%lld\n",ans);
return 0;
}//Paul_Guderian

0

lijun1025 LV 4 @ 2017-04-27 12:21:41

import java.util.Scanner;

public class CarShou{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int[] arr=new int[n];
int[] L=new int[m];
int[] R=new int[m];
int ki=0;

for(int i=0;i<n;i++){
arr[i]=input.nextInt();
if(arr[i]>ki)
ki=arr[i];
}

for(int i=0;i<m;i++){
L[i]=input.nextInt();
R[i]=input.nextInt();
}
int summin=0;
int min=1024;
int sum=0;
for(int i=0;i<m;i++){
if(L[i]==R[i]){
min=0;
break;
}else
for(int k=0;k<=ki;k++){
for(int t=L[i];t<=R[i];t++){
if(arr[t-1]-k>0)
sum+=(arr[t-1]-k);
else
sum-=(arr[t-1]-k);
}
if(sum<min)min=sum;

}

summin+=min;
}
System.out.println(summin);
}
}
//不知道错在哪里输出比答案多

0

WeiSama LV 8 @ 2017-01-19 17:48:39

1）long long
2）输入优化
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}

struct Node {
Node *ch[2];
int r, v, s, w;
long long sum;
Node(int v):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = w = 1; sum = v; }
int cmp(int x) {
if (x == v) return -1;
return x < v ? 0 : 1;
}
void push_up() {
s = w;
sum = w * v;
if (ch[0] != NULL) { s += ch[0]->s; sum += ch[0]->sum; }
if (ch[1] != NULL) { s += ch[1]->s; sum += ch[1]->sum; }
}
};

inline void rotate(Node* &rt, int d) {
Node* k = rt->ch[d ^ 1];
rt->ch[d ^ 1] = k->ch[d];
k->ch[d] = rt;
rt->push_up();
k->push_up();
rt = k;
}

void insert(Node* &rt, int x) {
if (rt == NULL) rt = new Node(x);
else {
int d = rt->cmp(x);
if (d == -1) (rt->w)++;
else {
insert(rt->ch[d], x);
if (rt->ch[d]->r > rt->r) rotate(rt, d ^ 1);
}
}
rt->push_up();
}

long long left_num, left_sum;

int kth(Node *rt, int k) {
int d = (rt->ch[0] == NULL ? 0 : rt->ch[0]->s);
if (k <= d) return kth(rt->ch[0], k);
else if (rt->ch[1] != NULL && k > d + rt->w) {
left_num += d + rt->w;
left_sum += (d == 0 ? 0 : rt->ch[0]->sum) + rt->w * rt->v;
return kth(rt->ch[1], k - d - rt->w);
} else {
if (d) left_sum += rt->ch[0]->sum;
left_num += d;
return rt->v;
}
}

const int N = 1000 + 5;

int n, m, h[N], ans[N][N];

int main() {
#ifdef LOCAL
freopen("C:\Users\Administrator\Desktop\in.txt", "r", stdin);
freopen("C:\Users\Administrator\Desktop\out.txt", "w", stdout);
#endif
n = read(); m = read();
for (int i = 1; i <= n; i++) h[i] = read();
for (int l = 1; l <= n; l++) {
Node* root = NULL;
long long tot = 0;
for (int r = l; r <= n; r++) {
tot += h[r];
insert(root, h[r]);
left_sum = left_num = 0;
int ave = kth(root, (r - l + 2) / 2);
ans[l][r] = left_num * ave - left_sum;
ans[l][r] += tot - left_sum - (r - l - left_num + 1) * ave;
}
delete root;
}
int l, r;
long long res = 0;
while (m--) {
l = read(); r = read();
res += ans[l][r];
}
printf("%lld\n", res);
return 0;
}

0

ljt12138 LV 10 @ 2016-12-24 17:01:22

测试数据 0: Accepted, time = 0 ms, mem = 1848 KiB, score = 10
测试数据 1: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 2: Accepted, time = 0 ms, mem = 1844 KiB, score = 10
测试数据 3: Accepted, time = 0 ms, mem = 1844 KiB, score = 10
测试数据 4: Accepted, time = 0 ms, mem = 1848 KiB, score = 10
测试数据 5: Accepted, time = 31 ms, mem = 1844 KiB, score = 10
测试数据 6: Accepted, time = 62 ms, mem = 1852 KiB, score = 10
测试数据 7: Accepted, time = 62 ms, mem = 1848 KiB, score = 10
测试数据 8: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 9: Accepted, time = 109 ms, mem = 1848 KiB, score = 10
Accepted, time = 294 ms, mem = 1852 KiB, score = 100

少见的数据结构题1AC。。

思路是可持久化线段树，维护一个sum(原始数字和)和num_sum(离散后的和)。离散后的和用来找中位数，sum用于计算。复杂度O(mlgn)。

// 可持久化线段树
// 维护两个值
#include <bits/stdc++.h>
using namespace std;

#define maxn 1005
struct node {
    int l, r, lc, rc;
    long long sum;
    int num_sum;
    node(){l = r = lc = rc = sum = num_sum = 0; }
}tree[15*maxn];
int root[200005], top = 0;
int n, m;

inline long long read()
{
    long long a = 0; int c;
    do c = getchar(); while(!isdigit(c));
    while (isdigit(c)) {
        a = a*10 + c - '0';
        c = getchar();
    }
    return a;
}

int sorted[1005]; // 离散化
int dat[1005]; // 原始数据

inline void update(int i) {
    tree[i].sum = tree[tree[i].lc].sum + tree[tree[i].rc].sum;
    tree[i].num_sum = tree[tree[i].lc].num_sum + tree[tree[i].rc].num_sum;
}

inline int new_node(int l, int r) {
    tree[++top].l = l;
    tree[top].r = r;
    return top;
}

void build(int &nd, int l, int r) {
    if (l > r) return;
    if (l == r) {nd = new_node(l, r);return;}
    int mid = (l+r)>>1;
    nd = new_node(l, r);
    build(tree[nd].lc, l, mid);
    build(tree[nd].rc, mid+1, r);
}

void insert(int pre, int &now, int k, long long dat) {
    if (tree[pre].l == tree[pre].r) {
        now = new_node(k, k);
        tree[now].sum = dat;
        tree[now].num_sum = 1;
    } else {
        now = new_node(tree[pre].l, tree[pre].r);
        tree[now] = tree[pre];
        if (k <= tree[tree[pre].lc].r) insert(tree[pre].lc, tree[now].lc, k, dat);
        else insert(tree[pre].rc, tree[now].rc, k, dat);
        update(now);
    }
}

// 查找区间和(sum)
long long get_sum(int pre, int now, int l, int r)
{
    if (l > r || !pre || !now) return 0;
    if (l == tree[pre].l && r == tree[now].r) return tree[now].sum - tree[pre].sum;
    return get_sum(tree[pre].lc, tree[now].lc, l, min(r, tree[tree[pre].lc].r)) +
           get_sum(tree[pre].rc, tree[now].rc, max(tree[tree[pre].rc].l, l), r);
}

// 区间内数字个数的和
int get_num_sum(int pre, int now, int l, int r)
{
    if (l > r || !pre || !now) return 0;
    if (l == tree[pre].l && r == tree[now].r) return tree[now].num_sum - tree[pre].num_sum;
    return get_num_sum(tree[pre].lc, tree[now].lc, l, min(r, tree[tree[pre].lc].r)) +
           get_num_sum(tree[pre].rc, tree[now].rc, max(tree[tree[pre].rc].l, l), r);
}

int find_mid(int pre, int now, int k) // 查找中位数(第k个数)的位置
{
    if (tree[now].l == tree[now].r) return tree[now].l;
    if (tree[tree[now].lc].num_sum - tree[tree[pre].lc].num_sum >= k)
        return find_mid(tree[pre].lc, tree[now].lc, k);
    else
        return find_mid(tree[pre].rc, tree[now].rc, k-(tree[tree[now].lc].num_sum - tree[tree[pre].lc].num_sum));
}

// 查询区间
long long query(int l, int r) {
    int pos = find_mid(root[l-1], root[r], ((l+r)>>1)-l+1);
    long long lft = get_sum(root[l-1], root[r], 1, pos);int ln = get_num_sum(root[l-1], root[r], 1, pos);
    long long rgt = get_sum(root[l-1], root[r], pos+1, n);int rn = get_num_sum(root[l-1], root[r], pos+1, n);
    return rgt - rn*sorted[pos] + ln*sorted[pos] - lft;
}

void dfs(int rt, int tab = 0) {
    if (rt) {
        for (size_t i = 0; i < tab; i++) putchar(' ');
        cout << tree[rt].l << "->" << tree[rt].r << " " << tree[rt].sum << " " << tree[rt].num_sum << endl;
        dfs(tree[rt].lc, tab+2);
        dfs(tree[rt].rc, tab+2);
    }
}

int main()
{
    n = read(); m = read();
    build(root[0], 1, n);
    long long a, l, r;
    for (size_t i = 1; i <= n; i++)
        sorted[i] = dat[i] = read();
    sort(sorted+1, sorted+n+1);
    for (size_t i = 1; i <= n; i++) {
        insert(root[i-1], root[i], lower_bound(sorted+1, sorted+n+1, dat[i])-sorted, dat[i]);
    }
    long long ans = 0;
    for (size_t i = 1; i <= m; i++) {
        l = read(); r = read();
        ans += query(l, r);
    }
    cout << ans << endl;
    return 0;
}

0

everforever LV 10 @ 2016-06-02 19:31:34

1549的提升版。。。然而需要输入优化。。。
#include<cstdio>
#include<iostream>
#define MAXN 2005
#define LL long long
using namespace std;

LL use[MAXN][MAXN];
int n,m;
LL ans=0;
LL h[MAXN];
int f[MAXN];
int num[MAXN][2][MAXN];
int q[MAXN][2];

inline LL ab(LL x){return x>0 ? x:-x;}

LL into()
{
char tmp=getchar();
int re=0;
while(tmp<'0'||tmp>'9')tmp=getchar();
while(tmp>='0'&&tmp<='9')re=re*10+(tmp-'0'),tmp=getchar();
return re;
}

int main()
{
n=into();m=into();
int i,j,g;
for(i=1;i<=n;i++)
h[i]=into();
int mid,t1,t2,tmp;
for(i=1;i<=n;i++)
{
mid=h[i];
q[0][0]=0;
for(j=1;j<=n;j++)
{
if(h[j]>mid)f[j]=f[j-1]+1;
else if(h[j]<mid)f[j]=f[j-1]-1;
else f[j]=f[j-1];
q[j][0]=q[j][1]=0;
}
for(j=0;j<i;j++)
{
tmp=f[i]-f[j];
if(tmp>0)t1=tmp,t2=1;
else if(tmp<0)t1=-tmp,t2=0;
else t1=0,t2=0;
num[t1][t2][++q[t1][t2]]=j+1;
}
for(j=i;j<=n;j++)
{
tmp=f[j]-f[i];
if(tmp>0)t1=tmp,t2=0;
else if(tmp<0)t1=-tmp,t2=1;
else t1=0,t2=0;
for(g=1;g<=q[t1][t2];g++)
use[num[t1][t2][g]][j]=mid;
}
}
for(i=1;i<=m;i++)
{
t1=into();t2=into();
if((t2-t1)%2==1)mid=use[t1][t2-1];
else mid=use[t1][t2];
for(j=t1;j<=t2;j++)
ans+=ab(h[j]-mid);
}
printf("%lld\n",ans);
return 0;
}

0

Onlynagesha LV 9 @ 2016-03-19 11:41:23

测试数据 #0: Accepted, time = 0 ms, mem = 2124 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2120 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 2124 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2132 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 2140 KiB, score = 10

测试数据 #5: Accepted, time = 171 ms, mem = 2176 KiB, score = 10

测试数据 #6: Accepted, time = 203 ms, mem = 2176 KiB, score = 10

测试数据 #7: Accepted, time = 250 ms, mem = 2172 KiB, score = 10

测试数据 #8: Accepted, time = 750 ms, mem = 2172 KiB, score = 10

测试数据 #9: Accepted, time = 421 ms, mem = 2176 KiB, score = 10

Accepted, time = 1810 ms, mem = 2176 KiB, score = 100

#include <cstdio>
#include <cstring>
#include <algorithm>

#include "oi/Functor.h"
#include "oi/AvlTree.h"

#include "stdint.h"

struct Range
{
int l,r;
struct CmpL
{
bool operator () (Range A,Range B) const
{
return A.l<B.l || (A.l==B.l && A.r<B.r);
}
};
};

int64_t h[1005];
uint64_t ans=0;
Range rg[200005];

int n,m;

template <class T>
T t_abs(T x)
{
return x>0?x:-x;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
rg[0].l = rg[0].r = 0;
for(int i=1;i<=m;i++) scanf("%d%d",&rg[i].l,&rg[i].r);
std::sort(rg,rg+m+1,Range::CmpL());

oi::AvlTree<int64_t,Less<int64_t> > tree;
for(int i=1;i<=m;i++)
{
//printf("%d %d\n",rg[i].l,rg[i].r);
if(rg[i].l>rg[i-1].r)
{
tree.clear();
for(int j=rg[i].l;j<=rg[i].r;j++) tree.insert(h[j]);
}
else
{
for(int j=rg[i-1].l;j<rg[i].l;j++) tree.lazyErase(h[j]);
if(rg[i].r>rg[i-1].r)
{
for(int j=rg[i-1].r+1;j<=rg[i].r;j++) tree.insert(h[j]);
}
else for(int j=rg[i].r+1;j<=rg[i-1].r;j++) tree.lazyErase(h[j]);
}
int64_t median=tree.kth(1+((rg[i].r-rg[i].l)>>1));
for(int j=rg[i].l;j<=rg[i].r;j++) ans+=t_abs(h[j]-median);
}
printf("%llu",ans);
return 0;
}

大致就是这个思路

0

RexxarKay LV 5 @ 2016-01-22 14:16:49

为什么堆就这一题。。。。

0

nevermorezjh LV 8 @ 2015-06-06 18:28:16

测试数据 #0: Accepted, time = 15 ms, mem = 4480 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 4480 KiB, score = 10

测试数据 #2: Accepted, time = 17 ms, mem = 4480 KiB, score = 10

测试数据 #3: Accepted, time = 19 ms, mem = 4476 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 4476 KiB, score = 10

测试数据 #5: Accepted, time = 140 ms, mem = 4480 KiB, score = 10

测试数据 #6: Accepted, time = 156 ms, mem = 4480 KiB, score = 10

测试数据 #7: Accepted, time = 156 ms, mem = 4480 KiB, score = 10

测试数据 #8: Accepted, time = 203 ms, mem = 4480 KiB, score = 10

测试数据 #9: Accepted, time = 203 ms, mem = 4480 KiB, score = 10

Accepted, time = 940 ms, mem = 4480 KiB, score = 100

大顶堆小顶堆N^2LOGN。。久违的1A

0

tigertang LV 10 @ 2014-07-14 12:50:39

一遍AC好高兴

0

chen199277 LV 10 @ 2009-10-06 10:43:23

线段树= =。

n^2*logN的。

n*n算法。。怎么打，都错误答案一个。

汗，只好用线段树了。

0

陈亮宇 LV 10 @ 2009-10-03 11:06:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 197ms

├ 测试数据 08：答案正确... 197ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：985ms

treap! treap! treap! treap! treap! treap! treap!

ps:第一次样例都没过就交了 10分 o(╯□╰)o

0

lc_jack LV 9 @ 2009-09-21 19:33:45

n^2的算法比较有借鉴意义。还是多掌握几种为好的~！

0

唐钰小宝 LV 10 @ 2009-07-25 23:55:49

Accepted 有效得分：100 有效耗时：1453ms

只会用(n^2logn)的线段树……比较慢了

0

340508965 LV 10 @ 2009-07-23 16:45:44

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

不错( ^_^ )不错嘛

费了我一下午

先去研究什么大根堆小根堆

然后看看sbt

最后实在无奈只能去看传说中的o(n^2)找中位数算法

最后终于在离开机房之前干掉了这道题目

噢耶(^o^)/

方法：

如果f表示1~j的每个数与a[i]的绝对值差的和。

s=中位数的地方

这时候ans=f-f

这个预处理很重要

a是读入的高度

首先，枚举每个数a。向左向右扫描，那么这个数是中位数的充要条件是比它大的数的个数与比它小的个数相差不超过一。所以向左向右求出，

h[j]（ji时) 表示中不大于a（小于等于）的个数减中比a大的个数

那么,a为[l,r]的中位数的充要条件是

( [L,R]中有奇数个数,且h[R]-h[L]=1 ) 或 ( [L,R]中有偶数个数,且h[R]-h[L]=0 )

对于每个l(1a[i] then inc(big) else inc(small);

k:=small-big;

l:=g[k];

while l>0 do

begin

if (j-l)mod 2=1 then mid[l,j]:=i;

l:=pre[l];

end;

l:=g[k-1];

while l>0 do

begin

if (j-l)mod 2=0 then mid[l,j]:=i;

l:=pre[l];

end;

end;

end;

fillchar(sum,sizeof(sum),0);

for i:=1 to n do

for j:=1 to n do

sum:=sum+abs(a[i]-a[j]);

ans:=0;

for h:=1 to m do

begin

read(i,j);

ans:=ans+sum[mid,j]-sum[mid,i-1];

end;

writeln(ans);

end.

0

吴潇岛 LV 10 @ 2009-07-23 16:12:46

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

感谢此人的题解：http://hi.baidu.com/cloudygoose/blog/item/a6cb08195db21a0f34fa41f7.html

0

tobright LV 10 @ 2009-07-22 10:14:29

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 884ms

├ 测试数据 07：答案正确... 931ms

├ 测试数据 08：答案正确... 931ms

├ 测试数据 09：答案正确... 947ms

├ 测试数据 10：答案正确... 962ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4696ms

我的堆龟速啊

还是堆最好写

0

cgy4ever LV 10 @ 2009-07-08 15:45:31

终于做出来了...

用的O(n^2)的,把所有都求出来的.

0

LV 0 @ 2009-05-24 20:28:18

http://hi.baidu.com/cloudygoose/blog/item/a6cb08195db21a0f34fa41f7.html 我把程序放进去了。

题解

58 条题解

车展

信息

状态

开发

支持

题解

58 条题解

车展

信息

状态

开发

支持

还没有账户？

登录