luoguP5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

预处理不好想

Yuno loves sqrt technology I

思路

首先明确一个地方：对于两个长度为 $x$ 的区间（依次设为 $1, 2$ ），用归并排序可以 $O(x)$ 求出区间 $1$ 中的数与区间 $2$ 中的数形成的逆序对数（即区间 $1$ 对区间 $2$ 的贡献），具体方法是：将两个区间按权值排序，用双指针扫，若区间 $1$ 当前数小于区间 $2$ ，就不管；否则若区间 $1$ 当前数大于区间 $2$ ，说明区间 $1$ 当前数及后面所有数都会对 $2$ 当前数有贡献，记录即可，代码如下：

int merge(int x[], int y[], int nx, int ny) //归并求逆序对
{
    int res = 0;
    for (int ix = 1, iy = 1; ix <= nx && iy <= ny; )
        if (x[ix] < y[iy]) ++ix;
        else res += nx - ix + 1, ++iy;
    return res;
}

再看题，直接求当然死挂， 看 lxl 由于强制在线考虑分块，设块长为 $B$ ，考虑每个询问，分整块贡献、散点贡献、整块和散点的相互贡献讨论：

1. 整块贡献，记 as[i,j] 表示“块 $i$ 到块 $j$ 这段区间的逆序对数”，直接可得整块答案， $O(1)$
2. 散点贡献，记 pre[i]/suf[i] 表示“点 $i$ 到所在块的左/右端点这段区间的逆序对数”，于是两边的散点单独的贡献可以直接得答案；对于两边互相影响，归并排序求， $O(B)$
3. 整块和散点，记 cnt[j, i] （调转下标是为了卡常）为“点 $i$ 对第 $j$ 块的贡献”，对 cnt 怼一个前缀和即可枚举整块 $O(\frac{n}{B})$ 得答案

然后看如何预处理， pre/suf 可以用树状数组把每个块扫一遍，记录每个点贡献即可，一个技巧是先计算 pre ，再计算 suf 时从上一次计算的树状数组里面删数，卡常，时间为 $O(\frac{n}{B} * B \log B) = O(n \log B)$

cnt 就是直接把每个块和整个区间归并一下，注意考虑点在块前还是块后，记录每个点贡献即可， $O(n + B)$

as 用区间 dp 的思想处理，不难发现 $as[i, j] = as[i + 1, j] + as[i, j - 1] - as[i + 1, j - 1] + (第i块对第j块的贡献)$ ，我们发现第 $i$ 块对第 $j$ 块的贡献可以用 $cnt$ 查，而 $as$ 的初始化就是 $as[i, i] = pre[第i块的右端点]$ ，于是可以 $O(B^2)$ 解决

至此，时间复杂度为 $O(n \log B + n + B + B^2 + m (1 + B + \frac{n}{B}))$ ，我们无脑取 $B = \sqrt{n}$ ，时间大概就是 $O(n \sqrt{n})$ ，注意常数

代码

#include <bits/stdc++.h>
#define STC static
#define fi first
#define se second
#define IL inline
namespace FIO
{
    const int L = (1 << 20) + 5;
    char *E, *S, buf[L], out[L];
    int l = 0;
    #define gh() (E == S ? E = (S = buf) + fread(buf, 1, L, stdin), (E == S ? EOF : *S++) : *S++)
    template<class T>
    IL void read(T &x)
    {
        char ch = gh(), t = 0;
        for ( ; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
        for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
        if (t) x = -x;
    }
    IL void flus(){ fwrite(out, 1, l, stdout), l = 0; }
    IL void check(){ if (l >= L - 5) flus(); }
    IL void putc(char x){ out[l++] = x, check(); }
    template<class T>
    IL void write(T x)
    {
        if (x < 0) putc('-'), x = -x;
        if (x > 9) write(x / 10);
        out[l++] = x % 10 + 48, check();
    }
}
using FIO::read;
using FIO::flus;
using FIO::putc;
using FIO::write;
using PII = std::pair<int, int>;
using LL = long long;
const int N = 1e5 + 100, B = 320, NB = 320;
/*
cnt[j,i]:点i与块j中的数形成的逆序对数的前缀和(点在块内没有意义)
pre[i]/suf[i]:每个点到所在块前/后缀逆序对数
*/
int n, m, a[N], num = 0, bl[N], cnt[NB][N], pre[N], suf[N]; 
PII a2[N], a3[N]; //排序用，a2给块,a3给整个序列
LL as[NB][NB], ans; //as[i][j]:块i到块j的逆序对数
struct Block{ int l, r; } b[NB];
namespace BIT
{
    #define lb(x) ((x) & (-(x)))
    int ct[N];
    IL void add(int x, int d){ for (; x <= n; x += lb(x)) ct[x] += d; }
    IL int ask(int x)
    {
        int res = 0;
        for (; x; x ^= lb(x)) res += ct[x];
        return res;
    }
    #undef lb
}
IL int merge(int x[], int y[], int nx, int ny) //归并求逆序对
{
    int res = 0;
    for (int ix = 1, iy = 1; ix <= nx && iy <= ny; )
        if (x[ix] < y[iy]) ++ix;
        else res += nx - ix + 1, ++iy;
    return res;
}
IL void ready(int id) //计算每个块内前后缀信息
{
    
    Block *x = &b[id];
    int t = 0;
    for (int i = x->l; i <= x->r; ++i) bl[i] = id;
    for (int i = x->l; i <= x->r; ++i)
    {
        BIT::add(a[i], 1);
        t += BIT::ask(n) - BIT::ask(a[i]);
        pre[i] = t;
    }
    as[id][id] = t;
    for (int i = x->l; i <= x->r; ++i)
    {
        suf[i] = t;
        BIT::add(a[i], -1);
        t -= BIT::ask(a[i] - 1);
    }
    std::sort(a2 + x->l, a2 + x->r + 1);
    for (int i = 1, j = x->l; i <= n; ++i)
    {
        while (j <= x->r && a3[i].fi > a2[j].fi) ++j;
        if (a3[i].se < x->l) cnt[id][a3[i].se] = j - x->l;
        else if (a3[i].se > x->r) cnt[id][a3[i].se] = x->r - j + 1;
    }
    for (int i = 2; i <= n; ++i) cnt[id][i] += cnt[id][i - 1];
}
IL int get(int l, int r, int id){ return cnt[id][r] - cnt[id][l - 1]; }
IL void ready2() //计算as
{
    for (int len = 2; len <= num; ++len)
        for (int i = 1, j; (j = i + len - 1) <= num; ++i) as[i][j] = as[i + 1][j] + as[i][j - 1] - as[i + 1][j - 1] + get(b[i].l, b[i].r, j);
}
IL void ask(int l, int r)
{
    STC int tp1[N], tp2[N], ct1, ct2, ll, rr;
    ct1 = ct2 = 0;
    if ((ll = bl[l]) == (rr = bl[r]))
    {
        Block *x = &b[bl[l]];
        for (int i = x->l; i <= x->r; ++i)
            if (l <= a2[i].se && r >= a2[i].se) tp2[++ct2] = a2[i].fi;
            else if (a2[i].se < l) tp1[++ct1] = a2[i].fi;
        ans = pre[r] - (l == x->l ? 0 : pre[l - 1]) - merge(tp1, tp2, ct1, ct2);
    }
    else
    {
        ans = as[ll + 1][rr - 1] + suf[l] + pre[r];
        for (int i = ll + 1; i < rr; ++i) ans = ans + get(l, b[ll].r, i) + get(b[rr].l, r, i);
        for (int i = b[ll].l; i <= b[ll].r; ++i) if (a2[i].se >= l) tp1[++ct1] = a2[i].fi;
        for (int i = b[rr].l; i <= b[rr].r; ++i) if (a2[i].se <= r) tp2[++ct2] = a2[i].fi;
        ans = ans + merge(tp1, tp2, ct1, ct2);
    }
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]), a2[i] = a3[i] = {a[i], i};
    std::sort(a3 + 1, a3 + 1 + n);
    for (int i = 1; i <= n; i += B) b[++num].l = i, b[num].r = i + B - 1;
    b[num].r = n;
    for (int i = 1; i <= num; ++i) ready(i);
    ready2();
    for (int l, r; m--; write(ans), putc('\n')) read(l), read(r), ask(l ^ ans, r ^ ans);
    return flus(), 0;
}