[数据结构与算法]P5046 Yuno loves sqrt technology I

P5046 Yuno loves sqrt technology I

给你一个长为 $n$ 的排列，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。

$1\le n,m\le 10^5$，时限 $750\text{ms}$，空限 $500\text{MB}$。

sol

静态查询逆序对数。

根据这题没有修改，容易想到直接预处理，$\mathcal{O}(\sqrt{n})$ 内回答询问即可。

考虑序列分块。

预处理方法一

类似于归并排序，需要预处理的信息有：

1. 每个元素到其块首这段区间的逆序对数。
2. 每个元素到其块尾这段区间的逆序对数。
3. 块 $i$ 到块 $j$ 这段区间的逆序对数。
4. 前 $i$ 个块中，小于等于 $j$ 的元素个数。

对于 $1,2$，用树状数组扫一遍即可，单块时间复杂度为 $\mathcal{O}(\sqrt{n}\log \sqrt{n})$，总时间复杂度为 $\mathcal{O}(n\log \sqrt{n})$，可过。

对于 $3$，设其为 $f[i][j]$，则有递推公式：
$$f[i][j]=f[i][j?1]+f[i+1][j]?f[i+1][j?1]+(i\text{所在块和}j\text{所在块产生的贡献})$$
时间复杂度为 $\mathcal{O}(n\sqrt{n})$，可过。

对于 $4$，对于每一个 $j$，先在每一个块内扫一遍，再计算前缀和即可，时间复杂度为 $\mathcal{O}(n\sqrt{n})$，可过。

预处理好了，接下来考虑怎么查询，对于一个询问 $l,r$：

• 若 $l,r$ 在同一块内，则答案为块首到 $r$ 的贡献和块首到 $l?1$ 的贡献之差，内部贡献用 $1$ 计算，两块贡献用归并求即可。

• 若 $l,r$ 不在同一块内，则分成两个散块和多个整块，先用 $3$ 计算好整块的内部贡献，然后根据 $4$ 求散块与整块的贡献，再归并求散块对散块的贡献，最后散块内部贡献用上面那种方法计算即可。

总时间复杂度为 $\mathcal{O}((n+m)\sqrt{n})$，总空间复杂度为 $\mathcal{O}(n\sqrt{n})$。

预处理方法二

记 $F[i][j]$ 表示 $[l,r]$ 这段区间与第 $j$ 块中的数产生的逆序对数，记为 $5$。

再把法一中的 $1,2,3$ 照搬过来。

考虑计算 $F$，对于每个块，对于每个块，归并记录每个数对块的贡献，然后算一遍前缀和即可，时间复杂度 $\mathcal{O}(n\sqrt{n})$，可过。

这样计算 $f$ 的时候可以省掉一个 $\mathcal{O}(\sqrt{n})$ 的归并。

对于询问 $l,r$：

• 若 $l,r$ 在同一块内，则答案为块首到 $r$ 的贡献和块首到 $l?1$ 的贡献之差，内部贡献用 $1$ 计算，两块贡献用归并求即可。
• 若 $l,r$ 不在同一块内，则分成两个散块和多个整块，先用 $3$ 计算好整块的内部贡献，然后根据 $5$ 差分求散块与整块的贡献，再归并求散块对散块的贡献，最后散块内部贡献用上面那种方法计算即可。

总时间复杂度为 $\mathcal{O}((n+m)\sqrt{n})$，总空间复杂度为 $\mathcal{O}(n\sqrt{n})$，但常数较法一更为优秀。

$\text{01-31?/?21:29:13?/?2.91s?/?132.38MB?/?4.00KB?C++98?O2}$。

#include <cstdio>
#include <algorithm>

namespace Fread
{
    const int SIZE = 1 << 23;
    char buf[SIZE], *S, *T;
    inline char getchar()
    {
        if (S == T)
        {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return '\n';
        }
        return *S++;
    }
}
namespace Fwrite
{
    const int SIZE = 1 << 23;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush()
    {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c)
    {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct NTR
    {
        ~NTR()
        {
            flush();
        }
    } ztr;
}

#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void write(long long x)
{
	if(x < 0)
	{
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int _ = 1e5 + 7, M = 320, siz = 317;

int n, m, a[_], L[M], R[M], bel[_], blo, pre[_], suf[_], f[M][_];

long long F[M][M], ans;

int x[M], y[M], lx, ly, c[_], d[_];

struct Pair
{
	int fi, se;
	inline bool operator < (const Pair & tmp) const
	{
		return fi < tmp.fi;
	}
} b[_];

struct BIT
{
	int b[_];
	inline void add(int x, int val)
	{
		for(int i = x; i < _; i += i & -i) b[i] += val;
	}
	inline int ask(int x)
	{
		int res = 0;
		for(int i = x; i; i -= i & -i) res += b[i];
		return res;
	}
} t;

inline int merge(int *a, int *b, int la, int lb)
{
	int ia = 1, ib = 1, res = 0;
	while(ia <= la && ib <= lb)
		if(a[ia] < b[ib]) ++ia;
		else
		{
			res += la - ia + 1;
			++ib;
		}
	return res;
}

inline void init()
{
	blo = (n - 1) / siz + 1;
	for(int i = 1; i <= blo; ++i)
	{
		L[i] = R[i - 1] + 1;
		R[i] = i * siz;
	}
	R[blo] = n;
	for(int i = 1; i <= n; ++i)
		b[i] = (Pair)
	{
		a[i], i
	};
	for(int i = 1; i <= blo; ++i)
	{
		std::sort(b + L[i], b + R[i] + 1);
		for(int j = L[i]; j <= R[i]; ++j)
		{
			bel[j] = i;
			c[j] = b[j].fi;
			d[j] = b[j].se;
		}
		int x = 0;
		for(int j = L[i]; j <= R[i]; ++j)
		{
			t.add(a[j], 1);
			x += t.ask(n) - t.ask(a[j]);
			pre[j] = x;
		}
		F[i][i] = x;
		for(int j = L[i]; j <= R[i]; ++j)
		{
			suf[j] = x;
			t.add(a[j], -1);
			x -= t.ask(a[j] - 1);
		}
	}
	std::sort(b + 1, b + n + 1);
	for(int j = 1; j <= blo; ++j)
		for(int i = 1, k = L[j]; i <= n; ++i)
		{
			const int id = b[i].se;
			while(k <= R[j] && b[i].fi > c[k]) ++k;
			if(id < L[j]) f[j][id] = k - L[j];
			else if(id > R[j]) f[j][id] = R[j] - k - (k <= R[j] && b[i].fi == c[k]) + 1;
		}
	for(int i = 1; i <= blo; ++i)
		for(int j = 2; j <= n; ++j) f[i][j] += f[i][j - 1];
	for(int len = 1; len <= blo; ++len)
		for(int i = 1; i <= blo; ++i)
		{
			if(len + i > blo) break;
			const int j = i + len;
			F[i][j] = F[i + 1][j] + F[i][j - 1] - F[i + 1][j - 1] + f[j][R[i]] - f[j][L[i] - 1];
		}
}

signed main()
{
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	init();
	while(m--)
	{
		int l = read() ^ ans, r = read() ^ ans, bl = bel[l], br = bel[r];
		lx = ly = 0;
		if(bl == br)
		{
			for(int i = L[bl]; i <= R[bl]; ++i)
			{
				if(l <= d[i] && d[i] <= r) y[++ly] = c[i];
				else if(d[i] < l) x[++lx] = c[i];
				ans = pre[r] - ((l == L[bl]) ? 0 : pre[l - 1]) - merge(x, y, lx, ly);
			}
		}
		else
		{
			ans = F[bl + 1][br - 1] + pre[r] + suf[l];
			for(int i = bl + 1; i <= br - 1; ++i)
				ans += f[i][R[bl]] - f[i][l - 1] + f[i][r] - f[i][L[br] - 1];
			for(int i = L[bl]; i <= R[bl]; ++i)
				if(d[i] >= l) x[++lx] = c[i];
			for(int i = L[br]; i <= R[br]; ++i)
				if(d[i] <= r) y[++ly] = c[i];
			ans += merge(x, y, lx, ly);
		}
		write(ans), putchar('\n');
	}
}