题解 | #区间与绝对值#

考虑莫队，需要看看对于一个窗口，加窗口，和出窗口信息如何维护，下面只介绍如何维护信息：

对于绝对值不等式，对于数组 ，需要求加入后产生的贡献，需要拆绝对值式子，对于小于的，计算方式为，其中sum为比小的总和，为个数。对于大于的数同理。

维护和可以考虑用两个树状数组分别维护即可。

关于莫队的内容，可以自行搜索学习

#include <bits/stdc++.h>
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int M = 1e5 + 7;
int n,m;
//树状数组部分
struct Tree{
    int c[N];
    void add(int x,int v){
        for(; x < N; x += x&-x) c[x] += v;
    }
    int query(int x){
        int ret = 0;
        for(; x > 0; x -= x&-x) ret += c[x];
        return ret;
    }
    int query(int l,int r){
        if(l > r) return 0;
        return query(r) - query(l-1);
    }
}trsum,trcnt;
//分块和初始化部分
int a[N],res[M];
int blen,bnum,bid[N];
struct Query{
    int l,r,id;
    bool operator < (const Query &oth){
        return bid[l] == bid[oth.l] ? r < oth.r : bid[l] < bid[oth.l];
    }
}queries[M];
void init(){
    blen = sqrt(n);
    bnum = (n + blen - 1) / blen;
    for(int i = 1;i <= n;i++){
        bid[i] = (i - 1) / blen + 1;
    }
    sort(queries + 1,queries + m + 1);
}
//莫队维护信息
int sum = 0;
void add(int x){
    int cnt = trcnt.query(1,x - 1);
    sum += x * cnt - trsum.query(1,x - 1);
    cnt = trcnt.query(x+1,N - 1);
    sum += trsum.query(x+1,N - 1) - x * cnt;
    trsum.add(x,x);
    trcnt.add(x,1);
}
void del(int x){
    int cnt = trcnt.query(1,x - 1);
    sum -= x * cnt - trsum.query(1,x - 1);
    cnt = trcnt.query(x+1,N - 1);
    sum -= trsum.query(x+1,N - 1) - x * cnt;
    trsum.add(x,-x);
    trcnt.add(x,-1);
}
void mo(){
    int wl = 1,wr = 0;
    for(int i = 1;i <= m;i++){
        auto [l,r,id] = queries[i];
        // l wl wr r
        while(wl > l) add(a[--wl]);
        while(wr < r) add(a[++wr]);
        while(wl < l) del(a[wl++]);
        while(wr > r) del(a[wr--]);
        res[id] = sum * 2;
    }
    
}


void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= m;i++){
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    init();
    mo();
    for(int i = 1;i <= m;i++){
        cout << res[i] << endl;
    }
    
}
signed main() {
    close;
    int T = 1;//cin >> T;
    while(T--){
        solve();
    }
    
    return 0;
}