洛谷 5501. 「LnOI2019」来者不拒，去者不追

此题的数据范围有误导性啊……
不管怎么样反正考虑莫队（

设莫队当前转移到的区间为，转移时新加入一个位置。
则除了本身的贡献以外，它会导致所有比它大的数排名升一位，即贡献加一。
于是其影响为

计算贡献时将两边差分成前缀相减的形式即可，然后套用二次离线的套路。
注注注注注意里面那个，它不能乱差分的，别把算成了啊……
~~（我才不会说我就是这样子调了半天的）~~

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 5e5;
const int V = 1e5;
const int BLK = 318;
const int CNT = 318;
int n,m,block,a[N + 5],pos[N + 5];
int vblock = BLK,vpos[V + 5];
struct s_query
{
    int l,r,id;
    long long ans;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
    }
} qry[N + 5];
struct s_contrib
{
    int l,r,id,w;
};
long long c[2][V + 5];
inline void update(int op,int x,int k)
{
    if(!op)
        for(;x <= V;x += lowbit(x))
            c[op][x] += k;
    else
        for(;x;x -= lowbit(x))
            c[op][x] += k;
}
inline long long query(int op,int x)
{
    long long ret = 0;
    if(!op)
        for(;x;x -= lowbit(x))
            ret += c[op][x];
    else
        for(;x <= V;x += lowbit(x))
            ret += c[op][x];
    return ret;
}
long long cnt[2][CNT + 5],pre[2][V + 5];
inline void add(int op,int x,int k)
{
    if(!op)
    {
        for(register int i = vpos[x] + 1;i <= vpos[V];++i)
            cnt[op][i] += k;
        for(register int i = x;i <= min(vpos[x] * vblock,V);++i)
            pre[op][i] += k;
    }
    else
    {
        for(register int i = vpos[x] - 1;i;--i)
            cnt[op][i] += k;
        for(register int i = x;i > (vpos[x] - 1) * vblock;--i)
            pre[op][i] += k;
    }
}
inline long long ask(int op,int x)
{
    return cnt[op][vpos[x]] + pre[op][x];
}
vector<s_contrib> vec[N + 5];
long long sum[2][N + 5],ans[N + 5];
int main()
{
    for(register int i = 1;i <= V;++i)
        vpos[i] = (i - 1) / vblock + 1;
    read(n),read(m),block = sqrt(n);
    for(register int i = 1;i <= n;++i)
        read(a[i]),pos[i] = (i - 1) / block + 1;
    for(register int i = 1;i <= n;++i)
    {
        int c = query(0,a[i] - 1);
        long long s = query(1,a[i] + 1);
        sum[0][i] = sum[0][i - 1] + (long long)a[i] * (c + 1) + s,
        sum[1][i] = sum[1][i - 1] + (long long)a[i] * (c - 1) + s,
        update(0,a[i],1),update(1,a[i],a[i]);
    }
    for(register int i = 1;i <= m;++i)
        read(qry[i].l),read(qry[i].r),qry[i].id = i;
    sort(qry + 1,qry + m + 1);
    for(register int i = 1,l = 1,r = 0;i <= m;++i)
    {
        qry[i].ans = sum[0][qry[i].r] - sum[0][r] + sum[1][qry[i].l - 1] - sum[1][l - 1];
        l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
        l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
        l = qry[i].l;
        r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
        r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
        r = qry[i].r;
    }
    for(register int i = 1;i <= n;++i)
    {
        add(0,a[i],1),add(1,a[i],a[i]);
        for(register vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
            for(register int j = it->l;j <= it->r;++j)
                qry[it->id].ans += it->w * (a[j] * ask(0,a[j] - 1) + ask(1,a[j] + 1));
    }
    for(register int i = 1;i <= m;++i)
        ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans);
    for(register int i = 1;i <= m;++i)
        printf("%lld\n",ans[i]);
}

『My guiding star.』

洛谷 5501 「LnOI2019」来者不拒，去者不追