/ Vijos / 题库 / 车展 /

题解

58 条题解

  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2016-01-22 14:16:49

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

  • 0
    @ 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
    @ 2014-07-14 12:50:39

    一遍AC好高兴

  • 0
    @ 2009-10-06 10:43:23

    线段树= =。

    n^2*logN的。

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

    汗,只好用线段树了。

  • 0
    @ 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
    @ 2009-09-21 19:33:45

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

  • 0
    @ 2009-07-25 23:55:49

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

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 2009-07-08 15:45:31

    终于做出来了...

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

信息

ID
1459
难度
6
分类
数据结构 | 平衡树数据结构 | 点击显示
标签
递交数
851
已通过
208
通过率
24%
上传者