P5046 Yuno loves sqrt technology I

P5046 Yuno loves sqrt technology I

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

\(1 \leq n,m\leq 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');
	}
}
上一篇:win32汇编-窗口 对话框 (三)


下一篇:ansible的相关命令