hihoCoder1488

﹏ヽ暗。殇╰゛Y 2023-08-17 16:37 105阅读 0赞

t题意略。

思路：（本题居然被人当成贪心，我真是醉了）

本题如若采用在线应答，则会很费时间。因此采用离线算法来解决。

这里又是区间查询，当然是采用莫队来解决了。

首先，在一个区间中，如果要使所有人的运转时间总和最小，肯定要让数字从小到大来排列。

在一个从小到大排列的数列中(有n项)，如果我们插入一个数(在a中下标为idx)，那么当前数列中总运转时间的增益是：

1.插入数字的运行时间part1 = a\[idx\] + 在数列中排在该数字前面的数的总和

2.后面数字的增益part2 = a\[idx\] \* (n - 排在我前面有多少个数字)

“在数列中排在该数字前面的数的总和” 与 “排在我前面有多少个数字” 用树状数组来统计。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 20005;
    const int before = 0;
    const int after = 1;
    typedef long long LL;
    
    struct seg{
        int l,r,idx;
        seg(int l = 0,int r = 0,int idx = 0){
            this->l = l,this->r = r,this->idx = 0;
        }
    };
    
    LL BIT[2][maxn],ans[maxn];
    int a[maxn],unit,T,n,m;
    seg store[maxn];
    
    LL lowbit(int k){
        return k & (-k);
    }
    void add(int dim,int idx,LL x){
        while(idx < maxn){
            BIT[dim][idx] += x;
            idx += lowbit(idx);
        }
    }
    LL sum(int dim,int idx){
        LL ret = 0;
        while(idx > 0){
            ret += BIT[dim][idx];
            idx -= lowbit(idx);
        }
        return ret;
    }
    void captainMo(){
        LL temp = 0,total = 0;
        int lft = 1,rht = 0;
        for(int i = 0;i < m;++i){
            while(rht < store[i].r){
                ++rht;
                temp += ((LL)a[rht] + sum(before,a[rht]));
                temp += (LL)a[rht] * (total - sum(after,a[rht]));
                ++total;
                add(before,a[rht],a[rht]);
                add(after,a[rht],1);
            }
            while(rht > store[i].r){
                int keep = rht--;
                temp -= sum(before,a[keep]);
                temp -= (LL)a[keep] * (total - sum(after,a[keep]));
                --total;
                add(before,a[keep],-a[keep]);
                add(after,a[keep],-1);
            }
            while(lft < store[i].l){
                int keep = lft++;
                temp -= sum(before,a[keep]);
                temp -= (LL)a[keep] * (total - sum(after,a[keep]));
                --total;
                add(before,a[keep],-a[keep]);
                add(after,a[keep],-1);
            }
            while(lft > store[i].l){
                --lft;
                temp += ((LL)a[lft] + sum(before,a[lft]));
                temp += (LL)a[lft] * (total - sum(after,a[lft]));
                ++total;
                add(before,a[lft],a[lft]);
                add(after,a[lft],1);
            }
            ans[store[i].idx] = temp;
        }
    }
    void init(){
        memset(BIT,0,sizeof(BIT));
    }
    
    bool cmp(const seg& s0,const seg& s1){
        if(s0.l / unit != s1.l / unit) return s0.l / unit < s1.l / unit;
        return s0.r / unit < s1.r / unit;
    }
    
    int main(){
        scanf("%d",&T);
        while(T--){
            init();
            scanf("%d%d",&n,&m);
            for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
            for(int i = 0;i < m;++i){
                scanf("%d%d",&store[i].l,&store[i].r);
                store[i].idx = i;
            } 
            
            unit = int(sqrt(n));
            sort(store,store + m,cmp);
            
            captainMo();
            
            for(int i = 0;i < m;++i) printf("%lld\n",ans[i]);
        }
        return 0;
    }
    
    /*
    3
    10 3
    2 1 4 7 4 8 3 6 4 7
    1 3
    4 6
    2 6
    
    4 2
    1 2 3 4
    1 2
    2 4
    
    10 1
    2 1 4 7 4 8 3 6 4 7
    2 7
    
    1
    1 1
    1
    1 1
    */

转载于:https://www.cnblogs.com/tiberius/p/11509748.html