【[Offer收割]编程练习赛11 D】排队接水

【题目链接】:http://hihocoder.com/problemset/problem/1488

【题意】



中文题

【题解】



莫队算法+树状数组;

首先贪心地知道,应该按照时间从小到大的顺序打水;

可以发现;

新增加一个人打水的话,对时间小于它的人打水没有影响;

只对时间大于它的人打水的时间有影响;

具体的;

对于时间大于它的打水的人的个数*这个人打水的时间;是新增加的打水时间;

然后同时还要加上这个人单独打水的时间;

即在它前面（时间比它小的打水的人）的所有打水时间总和+这个人的打水时间就是这个人的单独打水时间;

同样的道理

减去一个人也只会对它后面的人造成影响;

前面的人不受影响;

再减去它自身就可以了;

既然能够知道减少一个或者多一个人对答案的影响了;

则直接用莫队算法搞就好了



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 2e4+100;

struct abc

{

    int l,r,id;

};

int n,m,a[N],l,r,num;

LL bit[N],bit2[N],ans,out[N];

abc b[N];

int lowbit(int x)

{

    return x&(-x);

}

bool cmp(abc a,abc b)

{

    if (a.l/100==b.l/100)

        return a.r < b.r;

    else

        return a.l < b.l;

}

void add(int x,int key)

{

    if (key==1)

    {

        int y = x-1;

        LL sum = 0,cnt = 0;

        while (y>0)

        {

            sum+=bit[y];

            cnt+=bit2[y];

            y-=lowbit(y);

        }

        ans+=sum+x+(num-cnt)*x;

        y = x;

        while (y<N-10)

        {

            bit[y]+=x;

            bit2[y]++;

            y+=lowbit(y);

        }

        num++;

    }

    else

    {

        int y = x-1;

        LL sum = 0,cnt = 0;

        while (y>0)

        {

            sum+=bit[y];

            cnt+=bit2[y];

            y-=lowbit(y);

        }

        ans-=sum+x+(num-cnt-1)*x;

        y = x;

        while (y<N-10)

        {

            bit[y]-=x;

            bit2[y]--;

            y+=lowbit(y);

        }

        num--;

    }

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    int T;

    cin >> T;

    while (T--)

    {

        rep1(i,0,N-10)

            bit[i] = bit2[i] = 0;

        cin >> n >> m;

        rep1(i,1,n) cin >> a[i];

        rep1(i,1,m)

        {

            cin >> b[i].l >> b[i].r;

            b[i].id = i;

        }

        sort(b+1,b+1+m,cmp);

        l = 1,r = 1,ans = 0,num = 0;

        add(a[l],1);

        rep1(i,1,m)

        {

            while (r<b[i].r) add(a[++r],1);

            while (l>b[i].l) add(a[--l],1);

            while (r>b[i].r) add(a[r--],-1);

            while (l<b[i].l) add(a[l++],-1);

            out[b[i].id] = ans;

        }

        rep1(i,1,m) cout << out[i] << endl;

    }

    return 0;

}