离线思想基础

离线思想是指将整道题的所有询问全部输入好存储下来，并对其进行一定的操作（通常为按某种顺序排序）后，更高效地回答查询。但只能解决不强制在线的题目。~~这不是废话么~~

下面用一道最经典的例题引入离线思想。

P1972

给定数列，不带修，多次查询区间内有几种不同的数。

其实我们只需要保留每种数字各一个即可，比较容易实现的方式是选取最右边的。对于每种数，只关心它最后一次出现的位置。这样就把原序列转换成了一个

01

序列，表示该数是不是最后一次出现。

如果询问能保证右端点单调递增，就只需要用树状数组在新的

01

序列上进行区间查询即可。于是使用离线思想，询问存储下来后对右端点排序，同时提前记录每个询问的 id 方便按原顺序输出。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e6 + 10;
int n,q;
int a[N],ans[N],lst[N],id[N];
struct xxx
{
	int l;
	int r;
	int id;
	bool operator<(const xxx& xx) { return r < xx.r; }
} b[N];
class fenwick
{
	int a[N];
	inline int lowbit(int x) { return x & (-x); }
	int sum(int x)
	{
		int ans = 0;
		rep4(i,x,1,lowbit(i))
			ans += a[i];
		return ans;
	}
	public:
		fenwick() { cl(a); }
		void modify(int k,int x)
		{
			rep3(i,k,N - 1,lowbit(i))
				a[i] += x;
		}
		int query(int l,int r) { return sum(r) - sum(l - 1); }
} t;
void solve()
{
	cin >> n;
	rep1(i,1,n)
		cin >> a[i];
  cin >> q;
	rep1(i,1,q)
	{
		cin >> b[i].l >> b[i].r;
		b[i].id = i;
	}
	sort(b + 1,b + q + 1);
	rep1(i,1,n)
	{
		lst[i] = id[a[i]];
		id[a[i]] = i;
	}
	int j = 1;
	rep1(i,1,n)
	{
		t.modify(i,1);
		if (lst[i])
			t.modify(lst[i],-1);
		for (;j <= q && b[j].r == i;j++)
			ans[b[j].id] = t.query(b[j].l,b[j].r);
	}
	rep1(i,1,q)
		cout << ans[i] << '\n';
}
signed main()
{
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

CDQ 分治

CDQ 分治是一类特殊的分治，核心思想为：计算一个子问题对另一个子问题的贡献。

先按照正常的分治三部曲，递归处理左右子问题，再将左半部分视为修改，右半部分视为查询，用数据结构维护。

例题

首先是 CDQ 分治的最经典应用：

n

维偏序问题。

二维偏序

有

n

个物品，每个两种属性

a_i,b_i

，求最长不下降子序列。

可以直接用树状数组之类数据结构，但也可以 CDQ 分治。

设当前分治区间为

[l,r]

，我们递归求完了

[l,mid]

和

[mid+1,r]

的答案，接下来要算这两部分之间的答案。

把

[l,mid]

的点看做修改操作（即插入），

[mid+1,r]

的点看做查询，把整个区间按照

a_i

排序，直接双指针即可。

时间复杂度

\Theta(n\log n)

。需要注意的是，每次内部直接排会导致复杂度多一只

\log

，因此需要归并排序。

三维偏序：P3810

比上面多一个

c_i

属性。

先 CDQ 分治一次，变为二维偏序问题。上面提到可以直接树状数组（如果你不想写 CDQ 嵌套的话）。

CDQ 分治本来就需要一只

\log

，树状数组还带来了另外一只

\log

，因此总时间复杂度

\Theta(n\log^2n)

。

本题还要记得去重及其他一些细节。

代码：

CPP

#include <bits/stdc++.h>
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
using namespace std;
const int N = 2e5 + 10;
int n,k,cnt;
int ans[N];
struct xxx
{
	int a;
	int b;
	int c;
	int ans;
	int cnt;
	bool operator<(const xxx& xx) { return a < xx.a || (a == xx.a && (b < xx.b || (b == xx.b && c < xx.c))); }
} a[N],tmp[N];
class fenwick
{
	int c[N];
	inline int lowbit(int x) { return x & (-x); }
	int sum(int x)
	{
		int ans = 0;
		for (;x > 0;x -= lowbit(x))
			ans += c[x];
		return ans;
	}
	public:
		fenwick() { memset(c,0,sizeof c); }
		int query(int l,int r) { return sum(r) - sum(l - 1); }
		void modify(int k,int x)
		{
			for (;k < N;k += lowbit(k))
				c[k] += x;
		}
} fen;
void cdq(int l,int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	cdq(l,mid);
	cdq(mid + 1,r);
	int x = l;
	int y = mid + 1;
	int len = 0;
	while (x <= mid && y <= r)
		if (a[x].b <= a[y].b)
		{
			fen.modify(a[x].c,a[x].cnt);
			tmp[++len] = a[x++];
		}
		else
		{
			a[y].ans += fen.query(1,a[y].c);
			tmp[++len] = a[y++];
		}
	while (x <= mid)
	{
		fen.modify(a[x].c,a[x].cnt);
		tmp[++len] = a[x++];
	}
	while (y <= r)
	{
		a[y].ans += fen.query(1,a[y].c);
		tmp[++len] = a[y++];
	}
	rep1(i,l,mid)
		fen.modify(a[i].c,-a[i].cnt);
	rep1(i,1,len)
		a[i + l - 1] = tmp[i];
}
void solve()
{
	cin >> n >> k;
	rep1(i,1,n)
	{
		cin >> a[i].a >> a[i].b >> a[i].c;
		a[i].cnt = 1;
	}
	sort(a + 1,a + n + 1);
	cnt = 1;
	rep1(i,2,n)
		if (a[i].a == a[cnt].a && a[i].b == a[cnt].b && a[i].c == a[cnt].c)
			a[cnt].cnt++;
		else
			a[++cnt] = a[i];
	cdq(1,cnt);
	rep1(i,1,cnt)
		ans[a[i].ans + a[i].cnt - 1] += a[i].cnt;
	rep1(i,0,n - 1)
		cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

四维偏序

再加了一个

d_i

属性。

这里就需要 CDQ 分治的嵌套技巧了。写一个 CDQ 分治可以干掉一个维度，在 CDQ 分治中套另一个 CDQ 分治解三维偏序即可。时间复杂度

\Theta(n\log^3n)

。

可以发现，每进行一次 CDQ 分治即可以多一只

\log

的时间代价解决一个维度的偏序，不过

\Theta(n\log^4n)

及以上实际跟平方做法已经跑得差不多了，所以更高维的偏序 CDQ 分治其实并不具有优势。（当然也不可能有出题人出这种无聊题）

更多例题：

P4514 加强版

给定一个矩阵，初始所有元素为

0

，支持子矩阵加和子矩阵求和查询。

原题的数据范围直接用二维树状数组就能过。但其实可以用 CDQ 分治解决该题

n,m\le 2\times10^5

的强化版。

考虑一个俗称“Super BIT”的 trick：设差分数组

d_{x,y}=a_{x,y}-a_{x-1,y}-a_{x,y-1}+a_{x-1,y-1}

，前缀和数组

sum_{x,y}=\sum_{i=1}^x\sum_{j=1}^y a_{i,j}

，推式子可得

sum_{x,y}=\sum_{i=1}^x\sum_{j=1}^y d_{i,j}\times((x+1)\times(y+1)-(x+1)\times j-(y+1)\times i+i\times j)

。

把这个式子拆成

4

部分累加求解。我们相当于只需解决一个三个维度分别为时间、

x

坐标、

y

坐标的三维偏序问题，CDQ 分治求解即可。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define y1 __y1__
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 2050;
const int M = 2e5 + 10;
char ch;
int n,m,qcnt,x1,y1,x2,y2,delta;
struct query
{
	int id;
	int x;
	int y;
	int val;
	int op;
} q[M << 2],tmp[M << 2];
int f[N],fi[N],fj[N],fij[N],ans[M];
bool isquery[M];
inline int lowbit(int x) { return x & (-x); }
void modify(int a[],int k,int x)
{
	for (;k < N;k += lowbit(k))
		a[k] += x;
}
int query(int a[],int k)
{
	int ans = 0;
	for (;k > 0;k -= lowbit(k))
		ans += a[k];
	return ans;
}
inline void rmodify(int x,int y,int val)
{
	modify(f,y,val);
	modify(fi,y,val * x);
	modify(fj,y,val * y);
	modify(fij,y,val * x * y);
}
inline int rquery(int x,int y) { return query(f,y) * (x + 1) * (y + 1) - query(fi,y) * (y + 1) - query(fj,y) * (x + 1) + query(fij,y); }
void cdq(int l,int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	cdq(l,mid);
	cdq(mid + 1,r);
	int x = l;
	int y = mid + 1;
	int len = 0;
	for (;y <= r;y++)
	{
		for (;x <= mid && q[x].x <= q[y].x;x++)
		{
			tmp[++len] = q[x];
			if (q[x].op == 0)
				rmodify(q[x].x,q[x].y,q[x].val);
		}
		tmp[++len] = q[y];
		if (q[y].op == 1)
			ans[q[y].id] += q[y].val * rquery(q[y].x,q[y].y);
	}
	for (;x <= mid;x++)
		tmp[++len] = q[x];
	for (x = l;x <= mid && q[x].x <= q[r].x;x++)
		if (q[x].op == 0)
			rmodify(q[x].x,q[x].y,-q[x].val);
	rep1(i,1,len)
		q[l + i - 1] = tmp[i];
}
void solve()
{
	cin >> ch >> n >> m;
	int qaq = 0;
	while (cin >> ch >> x1 >> y1 >> x2 >> y2)
	{
		qaq++;
		if (ch == 'L')
		{
			cin >> delta;
			q[++qcnt] = {qaq,x1,y1,delta,0};
			if (x2 < n && y2 < m)
				q[++qcnt] = {qaq,x2 + 1,y2 + 1,delta,0};
			if (x2 < n)
				q[++qcnt] = {qaq,x2 + 1,y1,-delta,0};
			if (y2 < m)
				q[++qcnt] = {qaq,x1,y2 + 1,-delta,0};
		}
		else
		{
			q[++qcnt] = {qaq,x2,y2,1,1};
			if (x1 > 1 && x2 > 1)
				q[++qcnt] = {qaq,x1 - 1,y1 - 1,1,1};
			if (x1 > 1)
				q[++qcnt] = {qaq,x1 - 1,y2,-1,1};
			if (y1 > 1)
				q[++qcnt] = {qaq,x2,y1 - 1,-1,1};
			isquery[qaq] = true;
		}
	}
	cdq(1,qcnt);
	rep1(i,1,qaq)
		if (isquery[i])
			cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

P3157

给定序列，每次删除一个元素，求出删除前序列总逆序对数量。

先求出原始逆序对，然后考虑如何计算每次减少的逆序对数量。

对于每次删的元素，消失的逆序对为以下两者之一：

在它前面，权值比他大，且删去时间比他晚
在它后面，权值比他小，且删去时间比他晚

每个点有权值、位置、删除时间三个量，就是三维偏序，CDQ 分治求解。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e5 + 10;
int n,q,tp,ans;
struct xxx
{
	int val;
	int del;
	int ans;
	bool operator<(const xxx& xx) { return val < xx.val; }
} a[N],tmp[N];
bool cmp(const xxx& xx,const xxx& yy) { return xx.del < yy.del; }
int rev[N];
class fenwick
{
	int c[N];
	inline int lowbit(int x) { return x & (-x); }
	int sum(int x)
	{
		int ans = 0;
		for (;x > 0;x -= lowbit(x))
			ans += c[x];
		return ans;
	}
	public:
		void clr() { cl(c); }
		int query(int l,int r) { return sum(r) - sum(l - 1); }
		void modify(int k,int x)
		{
			for (;k <= n + 1;k += lowbit(k))
				c[k] += x;
		}
} fen;
void cdq(int l,int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	cdq(l,mid);
	cdq(mid + 1,r);
	int x = l;
	int y = mid + 1;
	while (x <= mid)
	{
		while (a[x].val > a[y].val && y <= r)
			fen.modify(a[y++].del,1);
		a[x].ans += fen.query(a[x].del + 1,q + 1);
		x++;
	}
	x = l;
	y = mid + 1;
	while (x <= mid)
	{
		while (a[x].val > a[y].val && y <= r)
			fen.modify(a[y++].del,-1);
		x++;
	}
	x = mid;
	y = r;
	while (y > mid)
	{
		while (a[y].val < a[x].val && x >= l)
			fen.modify(a[x--].del,1);
		a[y].ans += fen.query(a[y].del + 1,q + 1);
		y--;
	}
	x = mid;
	y = r;
	while (y > mid)
	{
		while (a[y].val < a[x].val && x >= l)
			fen.modify(a[x--].del,-1);
		y--;
	}
	sort(a + l,a + r + 1);
}
void solve()
{
	cin >> n >> q;
	rep1(i,1,n)
	{
		cin >> a[i].val;
		rev[a[i].val] = i;
		a[i].del = q + 1;
	}
	rep1(i,1,q)
	{
		cin >> tp;
		a[rev[tp]].del = i;
	}
	fen.clr();
	rep1(i,1,n)
	{
		ans += fen.query(a[i].val + 1,n + 1);
		fen.modify(a[i].val,1);
	}
	fen.clr();
	cdq(1,n);
	sort(a + 1,a + n + 1,cmp);
	rep1(i,1,q)
	{
		cout << ans << '\n';
		ans -= a[i].ans;
	}
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

P4169

初始平面上有一些点。支持添加一个点，和查询距离某个位置最近的点。此处距离指曼哈顿距离。

\operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|

。显然这个东西硬做搞不了，直接

4

次分类讨论把绝对值拆了。为了方便代码实现，可以把所有点坐标统一变换后套同一个函数。

于是可以钦定回忆出来的点都在询问点左下方。令

A

为询问的点，

B

为另一个点，此时

\operatorname{dist}(A,B)=(A_x+A_y)-(B_x+B_y)

，由于

A_x+A_y

是常数，只需最大化

B_x+B_y

。

问题转化为：对于询问

(x,y)

，求出

\max_{x_i\le x,y_i\le y}(x_i+y_i)

每个操作有三维：时间、

x

、

y

，这就是一个三维偏序，CDQ 分治即可。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e7 + 10;
int n,q,len,cnt;
struct xxx
{
	int id;
	int op;
	int x;
	int y;
	int ans;
} a[N],b[N],tmp[N];
inline void fix(int& x,int y) { x = min(x,y); }
inline void fix2(int& x,int y) { x = max(x,y); }
class fenwick
{
	int c[N];
	inline int lowbit(int x) { return x & (-x); }
	public:
		fenwick() { cl(c); }
		int query(int x)
		{
			int ans = 0;
			for (;x > 0;x -= lowbit(x))
				fix2(ans,c[x]);
			if (ans)
				return ans;
			else
				return -1e9;
		}
		void modify(int k,int x)
		{
			for (;k < len;k += lowbit(k))
				fix2(c[k],x);
		}
		void clr(int x)
		{
			for (;c[x] > 0;x += lowbit(x))
				c[x] = 0;
		}
} fen;
void cdq(int l,int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	cdq(l,mid);
	cdq(mid + 1,r);
	int x = l;
	int y = mid + 1;
	cnt = 0;
	while (y <= r)
	{
		while (x <= mid && b[x].x <= b[y].x)
		{
			if (b[x].op == 1)
				fen.modify(b[x].y,b[x].x + b[x].y);
			tmp[++cnt] = b[x++];
		}
		if (b[y].op == 2)
			fix(a[b[y].id].ans,b[y].x + b[y].y - fen.query(b[y].y));
		tmp[++cnt] = b[y++];
	}
	rep1(i,l,x - 1)
		if (b[i].op == 1)
			fen.clr(b[i].y);
	while (x <= mid)
		tmp[++cnt] = b[x++];
	rep1(i,1,cnt)
		b[i + l - 1] = tmp[i];
}
void solv(bool rx,bool ry)
{
	rep1(i,1,n + q)
	{
		b[i] = a[i];
		if (rx)
			b[i].x = len - b[i].x;
		if (ry)
			b[i].y = len - b[i].y;
	}
	cdq(1,n + q);
}
void solve()
{
	cin >> n >> q;
	rep1(i,1,n)
	{
		cin >> a[i].x >> a[i].y;
		a[i].x++;
		a[i].y++;
		a[i].op = 1;
		a[i].id = i;
		len = max(len,max(a[i].x,a[i].y));
	}
	rep1(i,n + 1,n + q)
	{
		cin >> a[i].op >> a[i].x >> a[i].y;
		a[i].x++;
		a[i].y++;
		a[i].id = i;
		a[i].ans = 1e9;
		len = max(len,max(a[i].x,a[i].y));
	}
	len++;
	rep1(i,0,1)
		rep1(j,0,1)
			solv(i,j);
	rep1(i,n + 1,n + q)
		if (a[i].op == 2)
			cout << a[i].ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

整体二分

许多最优化问题都可以通过二分解决。但当查询次数很多时，每次分别二分就无能为力了。这是我们就可以运用整体二分，将所有询问一起二分处理，便能高效解决问题。

P3834

多次查询静态数组区间第

k

小。

考虑询问与值域中点

mid

的关系：若询问区间内小于等于

mid

的数有

t

个，询问区间第

k

小数，则当

k\le t

时，答案应小于等于

mid

；否则，答案应大于

mid

。

我们还需要快速查询区间内小于一个数的数的数量，用树状数组即可快速实现。

具体实现：用 solve(l,r,ql,qr) 表示求解值域区间为

[l,r]

，询问编号区间为

[ql,qr]

的询问。当

l=r

时二分结束，解得所有询问答案均为当前

l

（或者

r

也行，两者等价）。然后按照元素与

\lfloor\dfrac{l+r}{2}\rfloor

的大小关系，分别放入两个临时数组中，并用树状数组处理询问。最后还原数组，继续递归即可。

代码去 OI-Wiki 看即可。

P3527

给定一个环，每次在环的某一段上加数，对每个元素，求什么时候该点总和大于等于给定阈值。

套路地断环为链。答案具有单调性，因此考虑整体二分。假设

[l,mid]

的陨石全部下了。对该操作区间按照是否满足条件（即下了足够多陨石）分为两类，合并后递归即可。还是用树状数组实现，但是需要搭配差分。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 6e5 + 10;
int n,m,k,tmp;
struct qaq
{
	int ned;
	int id;
} p[N],p1[N],p2[N];
struct query
{
	int l;
	int r;
	int a;
	int id;
} q[N];
int c[N],ans[N];
vector<int> v[N];
inline int lowbit(int x) { return x & (-x); }
void modify(int k,int x)
{
	for (;k <= 2 * m;k += lowbit(k))
		c[k] += x;
}
int query(int k)
{
	int ans = 0;
	for (;k > 0;k -= lowbit(k))
		ans += c[k];
	return ans;
}
int findmin(int k)
{
	int ans = 0;
	for (auto u : v[p[k].id])
	{
		ans += query(u) + query(u + m);
		if (ans >= p[k].ned)
			return ans;
	}
	return ans;
}
void solv(int l,int r,int ql,int qr)
{
	if (ql > qr)
		return;
	if (l == r)
	{
		rep1(i,ql,qr)
			ans[p[i].id] = l;
		return;
	}
	int mid = (l + r) >> 1;
	int cnt1 = 0;
	int cnt2 = 0;
	rep1(i,l,mid)
	{
		modify(q[i].l,q[i].a);
		modify(q[i].r + 1,-q[i].a);
	}
	rep1(i,ql,qr)
	{
		int tmp = findmin(i);
		if (tmp >= p[i].ned)
			p1[++cnt1] = p[i];
		else
		{
			p[i].ned -= tmp;
			p2[++cnt2] = p[i];
		}
	}
	rep1(i,l,mid)
	{
		modify(q[i].l,-q[i].a);
		modify(q[i].r + 1,q[i].a);
	}
	rep1(i,ql,ql + cnt1 - 1)
		p[i] = p1[i - ql + 1];
	rep1(i,ql + cnt1,qr)
		p[i] = p2[i - ql - cnt1 + 1];
	solv(l,mid,ql,ql + cnt1 - 1);
	solv(mid + 1,r,ql + cnt1,qr);
}
void solve()
{
	cin >> n >> m;
	rep1(i,1,m)
	{
		cin >> tmp;
		v[tmp].push_back(i);
	}
	rep1(i,1,n)
	{
		cin >> p[i].ned;
		p[i].id = i;
	}
	cin >> k;
	rep1(i,1,k)
	{
		cin >> q[i].l >> q[i].r >> q[i].a;
		if (q[i].r < q[i].l)
			q[i].r += m;
		q[i].id = i;
	}
	k++;
	q[k] = {1,2 * m,(int)1e9,k};
	solv(1,k,1,n);
	rep1(i,1,n)
		if (ans[i] == k)
			cout << "NIE\n";
		else
			cout << ans[i] << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

P1527

多次查询静态矩阵中子矩阵第

k

小值。

对于当前二分的值

mid

，如果该点元素

\ge mid

则将其赋值为

1

，否则为

0

。则我们其实只需要快速实现单点加、矩阵求和，用二维树状数组即可。剩下的就是整体二分板子。

因为树状数组每次都要清空，所以需要一个辅助数组记录以前的累加值，在代码中是 cur。

复杂度

3

只

\log

。听说可以用二维数点做到两只

\log

，但是不会。

可以发现这个复杂度在数据范围下是岌岌可危的，所以需要注意常数优化：

把所有数组元素存下来并排序，这样避免了对 $[0,10^9]$ 的区间进行二分，改为 $[1,n^2]$ 。
把元素从辅助数组移到原数组的过程不要硬移，可以只移下标。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define y1 __FLORRIO_y1__
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 510;
const int M = 6e4 + 10;
int n,m,cnt,tmp;
int ans[M],id[M],cur[M],q1[M],q2[M];
struct element
{
	int x;
	int y;
	int val;
	bool operator<(const element& xx) const { return val < xx.val; }
} a[N * N];
class fenwick
{
	int c[N][N];
	inline int lowbit(int x) { return x & (-x); }
	int sum(int x,int y)
	{
		int ans = 0;
		for (;x > 0;x -= lowbit(x))
			rep4(j,y,1,lowbit(j))
				ans += c[x][j];
		return ans;
	}
	public:
		fenwick() { cl(c); }
		void modify(int x,int y,int k)
		{
			for (;x <= n;x += lowbit(x))
				rep3(j,y,n,lowbit(j))
					c[x][j] += k;
		}
		int query(int x1,int y1,int x2,int y2) { return sum(x2,y2) - sum(x1 - 1,y2) - sum(x2,y1 - 1) + sum(x1 - 1,y1 - 1); }
} tr;
struct qry
{
	int x1;
	int y1;
	int x2;
	int y2;
	int k;
	inline int query() { return tr.query(x1,y1,x2,y2); }
} q[M];
void solv(int l,int r,int ql,int qr)
{
	if (ql > qr)
		return;
	if (l == r)
	{
		rep1(i,ql,qr)
			ans[id[i]] = a[l].val;
		return;
	}
	int mid = (l + r) >> 1;
	int cnt1 = 0;
	int cnt2 = 0;
	rep1(i,l,mid)
		tr.modify(a[i].x,a[i].y,1);
	rep1(i,ql,qr)
	{
		int u = id[i];
		int s = cur[u] + q[u].query();
		if (s >= q[u].k)
			q1[++cnt1] = u;
		else
		{
			q2[++cnt2] = u;
			cur[u] = s;
		}
	}
	rep1(i,ql,ql + cnt1 - 1)
		id[i] = q1[i - ql + 1];
	rep1(i,ql + cnt1,qr)
		id[i] = q2[i - ql - cnt1 + 1];
	rep1(i,l,mid)
		tr.modify(a[i].x,a[i].y,-1);
	solv(l,mid,ql,ql + cnt1 - 1);
	solv(mid + 1,r,ql + cnt1,qr);
}
void solve()
{
	cin >> n >> m;
	rep1(i,1,n)
		rep1(j,1,n)
		{
			cin >> tmp;
			a[++cnt] = {i,j,tmp};
		}
	sort(a + 1,a + cnt + 1);
	rep1(i,1,m)
	{
		cin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2 >> q[i].k;
		id[i] = i;
	}
	solv(1,cnt,1,m);
	rep1(i,1,m)
		cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

莫队

莫队这个名字是用于纪念它的发明者莫涛队长。

莫队通过对询问进行特殊地排序，并

\Theta(1)

移动查询区间左右端点，能够在优于平方的时间内解决问题。

莫队有许多种变形。

普通莫队：P1494

多次查询静态数组，求出每次随机从区间里抽两个数有多大概率相同。

先简单地推一波式子，可以发现从一个区间 $[l,r]$ 转移到 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$ 都是可以 $\Theta(1)$ 维护的，开一个桶即可。

接下来就是最重要的排序方式：按 $B$ 为块长分块，按照 $l$ 所在块为第一关键字， $r$ 本身为第二关键字排序。

下推导

B

的取值：

对于两个同一块内的询问，转移距离为

n

，共

\dfrac{n}{B}

个块，复杂度

\dfrac{n^2}{B}

；不同块的询问，每个都要走

B

，共

m

个，复杂度

mB

。

因此总复杂度

\dfrac{n^2}{B}+mB

。根据均值不等式，该式在

B=\dfrac{n}{\sqrt m}

时取

\min

，为

n\sqrt m

。

此外还有一个常数优化：排序时分

l

的奇偶性，这样可以减少块内所需代价。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 5e4 + 10;
const int B = 223;
int n,m,ans;
int c[N],in[N],buc[N],ans1[N],ans2[N];
struct query
{
	int l;
	int r;
	int len;
	int id;
	bool operator<(const query& xx) const
	{
		if (in[l] == in[xx.l])
		{
            if (in[l] & 1)
                return r < xx.r;
            return r > xx.r;
        }
		return in[l] < in[xx.l];
	}
} q[N];
inline void add(int x)
{
	ans += (buc[c[x]] << 1) | 1;
	buc[c[x]]++;
}
inline void del(int x)
{
	ans += 1 - (buc[c[x]] << 1);
	buc[c[x]]--;
}
inline int _(int x) { return (x * (x - 1)); }
void solve()
{
	cin >> n >> m;
	rep1(i,1,n)
	{
		cin >> c[i];
		in[i] = (i - 1) / B + 1;
	}
	rep1(i,1,m)
	{
		cin >> q[i].l >> q[i].r;
		q[i].len = q[i].r - q[i].l + 1;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1);
	int l = q[1].l;
	int r = q[1].r;
	rep1(i,l,r)
		add(i);
	if (ans != q[1].len)
	{
		int tmp = ans - q[1].len;
		int tmp2 = _(q[1].len);
		int g = __gcd(tmp,tmp2);
		ans1[q[1].id] = tmp / g;
		ans2[q[1].id] = tmp2 / g;
	}
	rep1(i,2,m)
	{
		while (l > q[i].l)
			add(--l);
		while (r < q[i].r)
			add(++r);
		while (l < q[i].l)
			del(l++);
		while (r > q[i].r)
			del(r--);
		if (ans != q[i].len)
		{
			int tmp = ans - q[i].len;
			int tmp2 = _(q[i].len);
			int g = __gcd(tmp,tmp2);
			ans1[q[i].id] = tmp / g;
			ans2[q[i].id] = tmp2 / g;
		}
	}
	rep1(i,1,m)
		if (ans1[i] == 0)
			cout << "0/1\n";
		else
			cout << ans1[i] << '/' << ans2[i] << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

回滚莫队：P5906

多次查询静态数组，求出区间里最远的两个相同数的距离。

我们发现，此题中转移只能从短区间向长区间转移，反过来不行。因为

\max

支持添加但不支持撤销。

这时就需要回滚莫队：每次只从短区间向长区间转移，一次处理完之后暴力回撤，回到原始状态。

具体地说，每次处理左端点在同一个块内的一组询问。令左指针停留在这组询问左端点所在块的右端点，右指针向右移动处理询问。随后令左指针向左移动处理询问，使用临时数组，并记得清空即可。

最后一个问题：如果开始时左指针在某次询问右端点的左边怎么办？这种情况相当于询问

l,r

在同一块内，暴力即可。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 2e5 + 10;
const int B = 447;
int n,m,l,r,block,tmp;
int a[N],tmpp[N],ans[N],in[N],rb[N],fst[N],lst[N],lst2[N];
struct query
{
	int l;
	int r;
	int id;
	bool operator<(const query& xx) const
	{
		if (in[l] == in[xx.l])
			return r < xx.r;
		return in[l] < in[xx.l];
	}
} q[N];
void solve()
{
	cin >> n;
	rep1(i,1,n)	
	{
		cin >> a[i];
		tmpp[i] = a[i];
		in[i] = (i - 1) / B + 1;
	}
	rep1(i,1,in[n])
		rb[i] = min(n,i * B);
	sort(tmpp + 1,tmpp + n + 1);
	int len = unique(tmpp + 1,tmpp + n + 1) - tmpp - 1;
	rep1(i,1,n)
		a[i] = lower_bound(tmpp + 1,tmpp + len + 1,a[i]) - tmpp;
	cin >> m;
	rep1(i,1,m)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1);
	rep1(i,1,m)
	{
		if (in[q[i].l] == in[q[i].r])
		{
			rep1(j,q[i].l,q[i].r)
				fst[a[j]] = 0;
			tmp = 0;
			rep1(j,q[i].l,q[i].r)
			{
				if (fst[a[j]] == 0)
					fst[a[j]] = j;
				tmp = max(tmp,j - fst[a[j]]);
			}
			rep1(j,q[i].l,q[i].r)
				fst[a[j]] = 0;
			ans[q[i].id] = tmp;
		}
		else
		{
			int now = in[q[i].l];
			if (block != now)
			{
				tmp = 0;
				rep1(j,l,r)
					fst[a[j]] = lst[a[j]] = 0;
				l = rb[now];
				r = l - 1;
				block = now;
			}
			while (r < q[i].r)
			{
				r++;
				if (fst[a[r]] == 0)
					fst[a[r]] = r;
				lst[a[r]] = r;
				tmp = max(tmp,r - fst[a[r]]);
			}
			int p = l;
			int tmp2 = 0;
			while (p > q[i].l)
			{
				p--;
				if (lst2[a[p]] == 0)
					lst2[a[p]] = p;
				tmp2 = max(tmp2,max(lst[a[p]],lst2[a[p]]) - p);
			}
			while (p < l)
			{
				lst2[a[p]] = 0;
				p++;
			}
			ans[q[i].id] = max(tmp,tmp2);
		}
	}
	rep1(i,1,m)
		cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

树上莫队：SP10707

给定一棵树，点带权，不带修，每次查询一条路径上有几种不同的数。

核心思想：用欧拉序把树拍到序列上。

设查询

u\rightarrow v(u\ne v)

的路径。记录每个节点进栈和出栈的时间戳

\operatorname{fst}_i,\operatorname{lst}_i

，然后分类讨论：

首先钦定 $\operatorname{fst}_u<\operatorname{fst}_v$ 。
若 $\operatorname{LCA}(u,v)=u$ ，此时 $u,v$ 在同一条链上。那么由欧拉序的性质，对于 $[\operatorname{fst}_u,\operatorname{fst}_v]$ 这个区间，有且只有恰好出现 $1$ 次的点对答案产生贡献。
否则，变为 $[\operatorname{lst}_u,\operatorname{fst}_v]$ 这个区间，拼上 $\operatorname{LCA}$ 本身。

使用树剖辅助维护，莫队离线处理即可。需要记录每个点是否被加入。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e5 + 10;
const int B = 126;
int n,m,u,v,dfncnt,anss;
int w[N],tmpw[N],fst[N],lst[N],rev[N],dep[N],fa[N],siz[N],son[N],top[N],ans[N],buc[N];
bool use[N];
vector<int> graph[N];
struct query
{
	int l;
	int r;
	int lx;
	int rx;
	int id;
	int lca;
	bool operator<(const query& xx) const
	{
		if (lx == xx.lx)
		{
			if (lx & 1)
				return r < xx.r;
			return r > xx.r;
		}
		return l < xx.l;
	}
} q[N];
void dfs1(int u,int faa)
{
	fa[u] = faa;
	siz[u] = 1;
	dep[u] = dep[faa] + 1;
	fst[u] = ++dfncnt;
	rev[dfncnt] = u;
	for (auto v : graph[u])
		if (v != faa)
		{
			dfs1(v,u);
			siz[u] += siz[v];
			if (siz[v] > siz[son[u]])
				son[u] = v;
		}
	lst[u] = ++dfncnt;
	rev[dfncnt] = u;
}
void dfs2(int u,int to)
{
	top[u] = to;
	if (son[u])
		dfs2(son[u],to);
	for (auto v : graph[u])
		if (v != fa[u] && v != son[u])
			dfs2(v,v);
}
int lca(int u,int v)
{
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]])
			swap(u,v);
		u = fa[top[u]];
	}
	if (dep[u] > dep[v])
		swap(u,v);
	return u;
}
void process(int x)
{
	if (use[x])
		anss -= (--buc[w[x]] == 0);
	else
		anss += (++buc[w[x]] == 1);
	use[x] ^= 1;
}
void solve()
{
	cin >> n >> m;
	rep1(i,1,n)	
	{
		cin >> w[i];
		tmpw[i] = w[i];
	}
	sort(tmpw + 1,tmpw + n + 1);
	int len = unique(tmpw + 1,tmpw + n + 1) - tmpw - 1;
	rep1(i,1,n)
		w[i] = lower_bound(tmpw + 1,tmpw + len + 1,w[i]) - tmpw;
	rep1(i,1,n - 1)
	{
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	rep1(i,1,m)
	{
		cin >> u >> v;
		if (fst[u] > fst[v])
			swap(u,v);
		q[i].id = i;
		q[i].lca = lca(u,v);
		if (q[i].lca == u)
		{
			q[i].l = fst[u];
			q[i].r = fst[v];
			q[i].lca = 0;
		}
		else
		{
			q[i].l = lst[u];
			q[i].r = fst[v];
		}
		q[i].lx = q[i].l / B;
		q[i].rx = q[i].r / B;
	}
	sort(q + 1,q + m + 1);
	int l = 1;
	int r = 0;
	rep1(i,1,m)
	{
		while (l > q[i].l)
			process(rev[--l]);
		while (r < q[i].r)
			process(rev[++r]);
		while (l < q[i].l)
			process(rev[l++]);
		while (r > q[i].r)
			process(rev[r--]);
		if (q[i].lca)
			process(q[i].lca);
		ans[q[i].id] = anss;
		if (q[i].lca)
			process(q[i].lca);
	}
	rep1(i,1,m)
		cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

带修莫队：P1903

给定数列，维护单点修改、区间查询不同数字个数。

普通莫队是静态的，无法支持修改。所以需要在普通莫队的基础上加一个时间维，表示这次操作的时间。这样在移动时，不仅需要移动

l,r

，还需要移动时间

t

。

那么原来的排序方式已经不起作用了。依然考虑分块，分为

B

个块，新的排序方式：以 $l$ 所在块为第一关键字， $r$ 所在块为第二关键字， $t$ 为第三关键字。因为如果还是像原版一样对

r

排序（而不是对其所在块）排序，就会带来乱序的时间维，复杂度随便卡就爆。

前方高能预警：推导比普通莫队复杂很多。

设序列长为

n

，有

m_1

个查询，

m_2

个修改。下推导

B

的取值：

考察左指针 $l$ ：每次移动 $B$ 距离，需要 $m_1$ 次移动，共 $m_1B$
考察右指针 $r$ ：对于每个块都要跑一遍整个序列，共 $n\times\dfrac{n}{B}=\dfrac{n^2}{B}$
考察时间 $t$ ：对于每对左右端点，时间戳都可能从 $0$ 跑到 $m_2$ ，共 $(\dfrac{n}{B})^2\times m_2=\dfrac{m_2n^2}{B^2}$

而题目中几乎不可能分别保证

m_1,m_2

的范围，因此可以假定

m_1,m_2

同阶。设

m=m_1=m_2

，总复杂度为

\Theta(mB+\dfrac{n^2}{B}+\dfrac{mn^2}{B^2})

。

如果不假定

n,m

同阶，这个东西貌似也能做，但是极其复杂，推出来的柿子很丑。所以假定

n,m

同阶，复杂度为

\Theta(nB+\dfrac{n^2}{B}+\dfrac{n^3}{B^2})

。

因为

B<n

，所以

\dfrac{n^2}{B}<\dfrac{n^3}{B}

，因此原式

=\Theta(nB+\dfrac{n^3}{B^2})

。

法一：该式的导数是 $n-\dfrac{2n^3}{B^3}$ 。令其 $=0$ ，此时 $B=\sqrt[3]{2n^2}=\Theta(n^{\frac{2}{3}})$ 。带回原式得 $n^{\frac{5}{3}}$ 。
法二：（感谢@Sunrise_beforeglow 指出）可以用把式子拆了之后用三元均值不等式，原式 $=\dfrac{nB}{2}+\dfrac{nB}{2}+\dfrac{n^3}{B^2}\ge3\times\sqrt[3]{\dfrac{nB}{2}\times\dfrac{nB}{2}\times\dfrac{n^3}{B^2}}=\Theta(n^{\frac{5}{3}})$ 。

至此，我们终于推导出了当 $B=n^{\frac{2}{3}}$ 时，取得最优复杂度 $n^{\frac{5}{3}}$ 。

代码：

CPP

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e6 + 10;
const int B = 2610;
int n,m,x,y,cnt1,cnt2,anss;
char ch;
int a[N],in[N],ans[N],buc[N];
struct query
{
	int l;
	int r;
	int t;
	int id;
	bool operator<(const query& xx) const
	{
		if (in[l] != in[xx.l])
			return in[l] < in[xx.l];
		if (in[r] != in[xx.r])
			return in[r] < in[xx.r];
		return t < xx.t;
	}
} q[N];
struct modify
{
	int pos;
	int val;
} c[N];
inline void add(int x) { anss += (++buc[x] == 1); }
inline void del(int x) { anss -= (--buc[x] == 0); }
inline void work(int now,int i)
{
	if (c[now].pos >= q[i].l && c[now].pos <= q[i].r)
	{
		add(c[now].val);
		del(a[c[now].pos]);
	}
	swap(c[now].val,a[c[now].pos]);
}
void solve()
{
	cin >> n >> m;
	rep1(i,1,n)
	{
		cin >> a[i];
		in[i] = (i - 1) / B + 1;
	}
	rep1(i,1,m)
	{
		cin >> ch >> x >> y;
		if (ch == 'Q')
			q[++cnt1] = {x,y,cnt2,cnt1};
		else
			c[++cnt2] = {x,y};
	}
	sort(q + 1,q + cnt1 + 1);
	int l = 1;
	int r = 0;
	int t = 0;
	rep1(i,1,cnt1)
	{
		while (l > q[i].l)
			add(a[--l]);
		while (r < q[i].r)
			add(a[++r]);
		while (l < q[i].l)
			del(a[l++]);
		while (r > q[i].r)
			del(a[r--]);
		while (t < q[i].t)
			work(++t,i);
		while (t > q[i].t)
			work(t--,i);
		ans[q[i].id] = anss;
	}
	rep1(i,1,cnt1)
		cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

离线算法学习笔记

文章操作