首页
关于
笔记
文章
友链

Solution -「洛谷 P5046」Yuno loves sqrt technology I

cirnovsky /

§ Description

Link.

无修改区间求逆序对。

§ Solution

首先有一个显然的 Θ(NNlog⁡2N)\Theta(N\sqrt{N}\log_{2}N) 做法，由于过不了所以我就不废话。

其实有了 Θ(NNlog⁡2N)\Theta(N\sqrt{N}\log_{2}N) 的过不去做法，我们就可以根据这个思路然后预处理解决问题。

我们需要处理的信息有：

  1. 散块的逆序对数量

  2. 以块为单位的区间逆序对数量

那么我们需要处理的数组就有以下几个：

  1. previous[i] 表示 ii 到 该块开头的逆序对数量。

  2. suffix[i] 同理。

  3. block[i][j] 表示前 ii 个块中 ≤j\leq j 元素个数。

  4. intervals[i][j] 表示以块为单位的区间 [i,j][i,j] 中的逆序对数量。

讲讲预处理方法。

  1. previous[i] 和 suffix[i] 的处理方法都很显然，可以一直扫着然后FWT扫就行。

  2. block[i][j] 可以递推，递推式为 block[i][j]=block[i+1][j]+block[i][j-1]-block[i+1][j-1]+cont(i,j)。其中 cont(i,j) 表示计算对应块的逆序对数。

  3. intervals[i][j] 每次循环到块的开头继承上一个块的贡献即可。

计算贡献的方法很简单，归并即可。mrsrz讲得也挺清楚的，我这里就不再赘述，主要讲讲怎么卡常。

首先我们可以把主函数里的所有循环全部展开，经过实践参数传8的时候跑得比较快。

然后八聚氧先加上，luogu O2也开着。

再其次快读fread快输fwrite，这些都是卡常的标配。

然后就把能拿出来的结构体拿出来，实在不能就不管了。

然后去STL，pair vector能去就去。

然后long long开在正确的地方，不要无脑replace。

函数inline，循环register。虽然可能作用不大但是可以先加上。

然后调块长，经过无数次实践发现取150~170较为优秀。

然后加了过后发现就算rp再好也只有60pts。

然后谷歌搜索硫酸的化学式H₂SO₄，给评测机喂硫酸（idea来自SyadouHayami）。

然后本来交了5页都过不了，这下再交两次就过了。

// 省略八聚氧
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int Maxn = 1e5 + 5;
const int Maxm = 650;
const int each = 160;
int n, m, blocks, Lp[Maxn], Rp[Maxn], isa[Maxn], head[Maxn], tail[Maxn], sorted[Maxn], belong[Maxn], previous[Maxn], suffix[Maxn], block[Maxm][Maxn];
long long intervals[Maxm][Maxn];
struct Holy_Pair
{
	int first, second;

	bool operator < (const Holy_Pair& rhs) const
	{
		return first < rhs.first;
	}
} current[Maxn];
struct Fenwick_Tree
{
	int fwt[Maxn];
	
	inline void Modify(int x, int v)
	{
		for (; x + 5 <= Maxn; x += x & -x)	fwt[x] += v;
	}

	inline int Query(int x)
	{
		int ret = 0;
		for (; x; x ^= x & -x)	ret += fwt[x];
		return ret;
	}
} FWT;

#define io_e '\0'
#define io_s ' '
#define io_l '\n'
namespace Fast_IO
{
... // 省略快读
}  // namespace Fast_IO

using Fast_IO::read;
using Fast_IO::write;

inline Holy_Pair make_pair(int first, int second)
{
	Holy_Pair ret;
	ret.first = first;
	ret.second = second;
	return ret;
}

inline int Merge_Vct(int rhs[], int shr[], int szl, int szr)
{
	int itl = 1, itr = 1;
	int ret = 0, ctr = 1;
	while (itl <= szl && itr <= szr)
	{
		if (rhs[itl] < shr[itr]) 	++itl, ++ctr;
		else
		{
			ret += szl - ctr + 1;
			++itr;
		}
	}
	return ret + szr - szr;
}

inline int Merge_Idx(int st1, int st2, int sz1, int sz2)
{
	int ret = 0, id1 = st1 + 1, id2 = st2 + 1;
	sz1 += st1, sz2 += st2;
	while (id1 <= sz1 && id2 <= sz2)
	{
		if (sorted[id1] < sorted[id2])		++id1;
		else
		{
			ret += sz1 - id1 + 1;
			++id2;
		}
	}
	return ret;
}

inline void Behavior(int l, int r, long long &ans)
{
	int itl = 0, itr = 0;
	if (belong[l] == belong[r])
	{
		for (int i = head[belong[l]]; i <= tail[belong[r]]; ++i)
		{
			if (current[i].second >= l && current[i].second <= r)	Rp[++itr] = sorted[i];
			else if (current[i].second < l)		Lp[++itl] = sorted[i];
		}
		if (l == head[belong[l]])	ans = previous[r] - Merge_Vct(Lp, Rp, itl, itr);
		else 	ans = previous[r] - previous[l - 1] - Merge_Vct(Lp, Rp, itl, itr);
	}
	else
	{
		ans = intervals[belong[l] + 1][belong[r] - 1] + previous[r] + suffix[l];
		for (int i = head[belong[l]]; i <= tail[belong[l]]; ++i)
		{
			if (current[i].second >= l)
			{
				Lp[++itl] = sorted[i];
				ans += block[belong[r] - 1][1] - block[belong[r] - 1][sorted[i]] - block[belong[l]][1] + block[belong[l]][sorted[i]];
			}
		}
		for (int i = head[belong[r]]; i <= tail[belong[r]]; ++i)
		{
			if (current[i].second <= r)
			{
				Rp[++itr] = sorted[i];
				ans += block[belong[r] - 1][sorted[i] + 1] - block[belong[l]][sorted[i] + 1];
			}
		}
		ans += Merge_Vct(Lp, Rp, itl, itr);
	}
	write(io_l, ans);
}

signed main()
{
	read(n, m), blocks = (n - 1) / each + 1;
	if (n <= 8)
	{
		for (int i = 1; i <= n; ++i)
		{
			read(isa[i]);
			current[i] = make_pair(isa[i], i);
		}
	}
	else
	{
		#pragma unroll 8
		for (int i = 1; i <= n; ++i)
		{
			read(isa[i]);
			current[i] = make_pair(isa[i], i);
		}
	}
	if (blocks <= 8)
	{
		for (int i = 1; i <= blocks; ++i)
		{
			head[i] = tail[i - 1] + 1;
			tail[i] = tail[i - 1] + each;
			if (i == blocks) 	tail[i] = n;
		}
	}
	else
	{
		#pragma unroll 8
		for (int i = 1; i <= blocks; ++i)
		{
			head[i] = tail[i - 1] + 1;
			tail[i] = tail[i - 1] + each;
			if (i == blocks) 	tail[i] = n;
		}
	}
	if (blocks <= 8)
	{
		for (int i = 1; i <= blocks; ++i)
		{
			memcpy(block[i], block[i - 1], sizeof(block[0]));
			sort(current + head[i], current + 1 + tail[i]);
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				++block[i][isa[j]];
				belong[j] = i;
				sorted[j] = current[j].first;
			}
			int satisfy = 0;
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				FWT.Modify(isa[j], 1);
				satisfy += FWT.Query(n) - FWT.Query(isa[j]);
				previous[j] = satisfy;
			}
			intervals[i][i] = satisfy;
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				suffix[j] = satisfy;
				FWT.Modify(isa[j], -1);
				satisfy -= FWT.Query(isa[j] - 1);
			}
		}
	}
	else
	{
		#pragma unroll 8
		for (int i = 1; i <= blocks; ++i)
		{
			memcpy(block[i], block[i - 1], sizeof(block[0]));
			sort(current + head[i], current + 1 + tail[i]);
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				++block[i][isa[j]];
				belong[j] = i;
				sorted[j] = current[j].first;
			}
			int satisfy = 0;
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				FWT.Modify(isa[j], 1);
				satisfy += FWT.Query(n) - FWT.Query(isa[j]);
				previous[j] = satisfy;
			}
			intervals[i][i] = satisfy;
			for (int j = head[i]; j <= tail[i]; ++j)
			{
				suffix[j] = satisfy;
				FWT.Modify(isa[j], -1);
				satisfy -= FWT.Query(isa[j] - 1);
			}
		}
	}
	if (blocks <= 8)
	{
		for (int dis = 1; dis <= blocks; ++dis)
		{
			for (int i = n - 1; i; --i)		block[dis][i] += block[dis][i + 1];
			for (int l = 1, r = dis + 1; r <= blocks + 1; ++l, ++r)
				intervals[l][r] = intervals[l + 1][r] + intervals[l][r - 1] - intervals[l + 1][r - 1] +
									Merge_Idx(head[l] - 1, head[r] - 1, tail[l] - head[l] + 1, tail[r] - head[r] + 1);
		}
	}
	else
	{
		#pragma unroll 8
		for (int dis = 1; dis <= blocks; ++dis)
		{
			for (int i = n - 1; i; --i)		block[dis][i] += block[dis][i + 1];
			for (int l = 1, r = dis + 1; r <= blocks + 1; ++l, ++r)
				intervals[l][r] = intervals[l + 1][r] + intervals[l][r - 1] - intervals[l + 1][r - 1] +
									Merge_Idx(head[l] - 1, head[r] - 1, tail[l] - head[l] + 1, tail[r] - head[r] + 1);
		}
	}

	if (m <= 8)
	{
		long long lastans = 0;
		for (int i = 0; i < m; ++i)
		{
			long long l, r;
			read(l, r);
			l ^= lastans;
			r ^= lastans;
			Behavior(l, r, lastans);
		}
	}
	else
	{
		long long lastans = 0;
		#pragma unroll 8
		for (int i = 0; i < m; ++i)
		{
			long long l, r;
			read(l, r);
			l ^= lastans;
			r ^= lastans;
			Behavior(l, r, lastans);
		}
	}
	return 0;
}