hiho一下第246周《排队接水》题目分析

5
2

《排队接水》题目分析

本题是一道比较难的数据结构题目。

首先我们根据排序不等式可以知道,对于一个连续区间[l, r]的小朋友接水问题,一定是将用时短的排在前面、用时长的排在后面。

于是我们有个暴力算法,就是对于每一个询问,将a[l] .. a[r]进行排序,然后直接计算结果。这样的复杂度是O(Tnm)的,会超时。

要解决这道题目,我们需要先了解“莫队算法”。莫队算法对于这类区间上的询问问题,给出了一个解决的算法框架。

关于莫队算法,大家可以参考莫队算法良心讲解莫队算法初探

余下的问题是,当我们增加一个数,或者减少一个数时,结果会如何变化。

比如当前区间从小到大排序后是B[1], B[2], ... B[N],当新插入一个X时,假设排序后是B[1], B[2], ... B[K-1], X, B[K], B[K+1], ... B[N]。

则B[1], B[2], ... B[K-1]等待时间没有增加。

X等待时间是B[1]+B[2]+ ...+B[K-1]+X,即一个前缀和+X。

B[K], B[K+1], ... B[N]的等待时间都增加X。

所以我们需要数据结构维护一个有序数组,知道新增加的元素在数组中排第几大,并且知道有序数组的前缀和。可以用树状数组搞定。

当删除一个数时,处理也是类似的,不再赘述。

1 answer(s)

0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 20005;
const ll mod=1e9+7;
ll a[maxn];
ll s[2][maxn];
ll ans[maxn];
struct note{
    int l,r,i,yuan;
    bool operator < (const note & x) 
    {
        if (i!=x.i)
        return i<x.i;
        return r<x.r;
    }
}sem[maxn];
void add(int i,int pos,int val)
{
    for (int q=pos;q<=maxn-5;q+=q&-q)
    s[i][q]+=val;
}
ll gets(int i,int pos)
{
    ll sum=0;
    for (int q=pos;q;q-=q&-q) sum+=s[i][q];
    return sum;
}

int main()
{
    int T;
    cin>>T;

    int n,m;
    while (T--)
    {
        memset(s,0,sizeof s);
        memset(ans,0,sizeof ans);

        scanf("%d%d",&n,&m);
        for (int q=1;q<=n;q++) scanf("%d",&a[q]);

        int t1,t2;
        int block = sqrt(n);
        for (int q=1;q<=m;q++)
        {
            scanf("%d%d",&sem[q].l,&sem[q].r);
            sem[q].i=sem[q].r/block;
            sem[q].yuan=q;
        }

        sort(sem+1,sem+1+m);

        int l=1,r=0;
        ll temp=0;
        for (int q=1;q<=m;q++)
        {
            while (r<sem[q].r)
            {
                r++;
                add(0,a[r],1);
                add(1,a[r],a[r]);
                temp+=a[r]*(r-l+1-gets(0,a[r]))+gets(1,a[r]);
            }
            while (r>sem[q].r)
            {
                temp-=a[r]*(r-l+1-gets(0,a[r]))+gets(1,a[r]);
                add(0,a[r],-1);
                add(1,a[r],-a[r]);
                r--;
            }
            while (l<sem[q].l)
            {
                temp-=a[l]*(r-l+1-gets(0,a[l]))+gets(1,a[l]);
                add(0,a[l],-1);
                add(1,a[l],-a[l]);
                l++;
            }

            while (l>sem[q].l)
            {
                l--;
                add(0,a[l],-1);
                add(1,a[l],-a[l]);
                temp-=a[l]*(r-l+1-gets(0,a[l]))+gets(1,a[l]);
            }
            ans[sem[q].yuan]=temp;
        }
        for (int q=1;q<=m;q++)
        printf("%lld\n",ans[q]);
    }

    return 0;
}

得分0分。。。。。,已经改到崩溃了,求巨巨看一下!!

  • 已解决。。。。区间左端修改时写错 了。。。,结构体里面重载的< 手残也写错了, 打扰各位了

  • 666.

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享