萌新刚学1msOI求卡常

#include <bits/stdc++.h>
using namespace std;

namespace IO
{
    char ch;
    inline void read() {}
    template<class T1, class... T2>
    inline void read(T1& num1, T2&... num2)
    {
        num1 = 0; ch = getchar();
        for (; !isdigit(ch); ch = getchar());
        for (; isdigit(ch); ch = getchar())
            num1 = num1 * 10 + (ch ^ '0');
        read(num2...);
    }
}
using IO::read;

typedef long long ll;

const int N = 5e5 + 5;
const int Q = 5e5 + 5;
//const int B = 500;
int B;

int n, q, a[N], pos[N];
int bl[N], br[N], bid[N], m;

ll ans[N], crt, bck;
int bckl, bckr, l, r;

struct listnode
{
    int prev, next;
}arr[N];

int top;
struct history
{
    int node; listnode val;
}stk[N];

struct operation
{
    int l, r, id;
    bool operator<(const operation& mem) const
    {
        if (bid[l] != bid[mem.l])
            return bid[l] < bid[mem.l];
        return r > mem.r;
    }
}oper[N];

inline void erase(int x)
{
    stk[++top] = {x, arr[x]};
    if (arr[x].prev)
    {
        crt -= abs(pos[x] - pos[arr[x].prev]);
        arr[arr[x].prev].next = arr[x].next;
    }
    if (arr[x].next)
    {
        crt -= abs(pos[x] - pos[arr[x].next]);
        arr[arr[x].next].prev = arr[x].prev;
    }
    if (arr[x].prev && arr[x].next)
    {
        crt += abs(pos[arr[x].prev] - pos[arr[x].next]);
    }
}

inline void brute(int l, int r)
{
    bck = 0;
    bckl = l; bckr = r;
    for (int i = 1; i <= n; ++i)
    {
        arr[i].prev = i - 1;
        arr[i].next = i + 1;
        bck += abs(pos[i] - pos[i + 1]);
    }
    bck -= abs(pos[n] - pos[n + 1]);
    arr[1].prev = arr[n].next = 0;
    crt = bck;
    for (int i = 1; i < l; ++i)
    {
        erase(a[i]);
    }
    for (int i = r + 1; i <= n; ++i)
    {
        erase(a[i]);
    }
    bck = crt;
    top = 0;
}

inline void backup()
{
    top = 0; bck = crt;
    bckl = l; bckr = r;
}

inline void recover()
{
    int x;
    crt = bck;
    l = bckl; r = bckr;
    while (top)
    {
        arr[x = stk[top].node] = stk[top].val;
        arr[arr[x].prev].next = x;
        arr[arr[x].next].prev = x;
        --top;
    }
}

int main()
{
    read(n, q); B = sqrt(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
        bid[i] = (i - 1) / B + 1;
        pos[a[i]] = i;
    }
    m = bid[n];
    for (int i = 1; i <= m; ++i)
    {
        bl[i] = br[i - 1] + 1;
        br[i] = br[i - 1] + B;
    }
    br[m] = n;
    for (int i = 1; i <= q; ++i)
    {
        read(l, r);
        oper[i] = {l, r, i};
    }
    sort(oper + 1, oper + 1 + q);
    for (int i = 1; i <= q; ++i)
    {
        if (bid[oper[i].l] != bid[oper[i - 1].l])
            brute(bl[bid[oper[i].l]], oper[i].r);

        recover();

        while (r > oper[i].r)
            erase(a[r--]);

        backup();

        while (l < oper[i].l)
            erase(a[l++]);

        ans[oper[i].id] = crt;
    }
    for (int i = 1; i <= q; ++i)
    {
        printf("%lld\n", ans[i]);
    }
    return 0;
}