离线算法

在线算法：进行一次操作之后立刻回复答案
离线算法：可以读入所有操作之后再回复答案

在线
输入一个询问，回答一个询问
往往预处理相关

离线
先读入所有询问，排序……分组……处理这些询问
最后一起回答

如果一个题目在线可以做，离线一定可以做
有的题目在线的做法比离线的做法麻烦非常多
有一些题目强制在线

有的题目离线的做法比在线的做法简单很多

CDQ分治

莫队算法

整体二分

参考题目

P1972 [SDOI2009] HH的项链

https://www.luogu.com.cn/problem/P1972

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 $n$ ，表示项链长度。
第二行 $n$ 个正整数 $a_i$ ，表示项链中第 $i$ 个贝壳的种类。

第三行一个整数 $m$ ，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$ ，表示询问的区间。

输出格式

输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

样例 #1

样例输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出 #1

2
2
4

提示

【数据范围】

对于 $20\%$ 的数据， $1\le n,m\leq 5000$ ；
对于 $40\%$ 的数据， $1\le n,m\leq 10^5$ ；
对于 $60\%$ 的数据， $1\le n,m\leq 5\times 10^5$ ；
对于 $100\%$ 的数据， $1\le n,m,a_i \leq 10^6$ ， $1\le l \le r \le n$ 。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB

参考代码

#include<stdio.h>
#define BUFSIZE 40000000
char buf[BUFSIZE],*pt=buf;
#define scan(t)\
{\
	t=0;\
	while(*pt<'0'||*pt>'9')\
		 pt++;\
	while(*pt>='0'&&*pt<='9')\
		t=t*10+(*pt++)-'0';\
}
int c[1000020];
int l[1000020];
int p[1000020];
int h[1000020];
int a[1000020][2];
int z[1000020];
int x,n,m,u;
void R(int x,int y)
{
	for(u+=y;x<=n;x+=x&-x)
		c[x]+=y;
}
int G(int x)
{
	int re=0;
	for(;x;x-=x&-x)
		re+=c[x];
	return re;
}
int main()
{
	fread(buf,1,BUFSIZE,stdin);
	scan(n)
	for(int i=1;i<=n;i++)
	{
		scan(x)
		p[i]=l[x];
		l[x]=i;
	}
	scan(m)
	for(int i=1;i<=m;i++)
	{
		scan(a[i][1])
		scan(x)
		a[i][0]=h[x];
		h[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(p[i])
			R(p[i],-1);
		R(i,1);
		for(int j=h[i];j;j=a[j][0])
			z[j]=u-G(a[j][1]-1);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",z[i]);
	return 0;
}

题解

离线树状数组

直接用 sort
vector 或者链表将所有询问按照右端点分组

P4113 [HEOI2012]采花

https://www.luogu.com.cn/problem/P4113

题目描述

萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。

花园足够大，容纳了 $n$ 朵花，共有 $c$ 种颜色，用整数 $1 \sim c$ 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。

由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 $m$ 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。

输入格式

输入的第一行是三个用空格隔开的整数，分别代表花的个数 $n$ ，花的颜色数 $c$ ，以及行程数 $m$ 。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 朵花的颜色 $x_i$ 。

第 $3$ 行到第 $(m + 2)$ 行，每行两个整数 $l, r$ ，第 $(i + 2)$ 行的数字代表第 $i$ 次行程为第 $l$ 到第 $r$ 朵花。

输出格式

共输出 $m$ 行，每行一个整数。第 $i$ 行的整数代表第 $i$ 次行程公主能采到的花共有几种不同的颜色。

样例 #1

样例输入 #1

样例输出 #1

提示

输入输出样例 $1$ 解释

共有五朵花，颜色分别为 $1,~2,~2,~3,~1$ 。

对于第一次行程，公主采花的区间为 $[1, 5]$ ，可以采位置 $1,~2,~3,~5$ 处的花，共有 $1$ 和 $2$ 两种不同的颜色。

对于第二次行程，公主采花的区间为 $[1, 2]$ ，但是颜色为 $1$ 和 $2$ 的花都只出现了一次，因此公主无花可采。

对于第三次行程，公主采花的区间为 $[2, 2]$ ，但是颜色为 $2$ 的花只出现了一次，公主无花可采。

对于第四次行程，公主采花的区间为 $[2, 3]$ ，可以采 $2,~3$ 位置的花，只有 $2$ 这一种颜色。

对于第五次行程，公主采花的区间为 $[3,5]$ ，但是颜色为 $1, 2, 3$ 的花都只出现了一次，因此公主无花可采。

数据范围与约定

本题采用多测试点捆绑测试，共有两个子任务。

对于子任务 $1$ ，分值为 $100$ 分，保证 $1 \leq n, c, m \leq 3 \times 10^5$ 。

对于子任务 $2$ ，分值为 $100$ 分，保证 $1 \leq n, c, m \leq 2 \times 10^6$ 。

对于全部的测试点，保证 $1 \leq x_i \leq c$ ， $1 \leq l \leq r \leq n$ 。

参考代码

#include<stdio.h>
#define BUFSIZE 100000000
char buf[BUFSIZE],*pt=buf;
#define scan(t)\
{\
	t=0;\
	while(*pt<'0'||*pt>'9')\
		 pt++;\
	while(*pt>='0'&&*pt<='9')\
		t=t*10+(*pt++)-'0';\
}
int c[2000020];
int l[2000020];
int p[2000020];
int h[2000020];
int a[2000020][2];
int z[2000020];
int x,n,m,u;
void R(int x,int y)
{
	for(u+=y;x<=n;x+=x&-x)
		c[x]+=y;
}
int G(int x)
{
	int re=0;
	for(;x;x-=x&-x)
		re+=c[x];
	return re;
}
int main()
{
	fread(buf,1,BUFSIZE,stdin);
	scan(n)scan(m)scan(m)
	for(int i=1;i<=n;i++)
	{
		scan(x)
		p[i]=l[x];
		l[x]=i;
	}
	for(int i=1;i<=m;i++)
	{
		scan(a[i][1])
		scan(x)
		a[i][0]=h[x];
		h[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(p[p[i]])
			R(p[p[i]],-1);
		if(p[i])
			R(p[i],1);
		for(int j=h[i];j;j=a[j][0])
			z[j]=u-G(a[j][1]-1);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",z[i]);
	return 0;
}