集训Day1下午并查集

## 1. 并查集
正常并查集不够优秀所以通常和路径压缩一起用，如下.
```cpp
int to[maxn];//to[i] 代表i的箭头指向谁

int go(int p)//从p点出发 看最后会走到哪里
{
	if (p == to[p]) return p;
	else 
	{
		to[p] = go(to[p]);
		return to[p];
	}
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		to[i] = i;
	
	//合并
	to[go(p1)] = go(p2);
	
	//查询
	go(p1) == go(p2); 
}
```
## 2. 分块
参考deepseek
线段树和分块是两种常用的处理区间查询与更新的数据结构，各有其特点和适用场景。

> - 结构：将数组划分为大小为$\sqrt n$的块，预处理块内信息（如和、最值）。
>
> - 时间复杂度：查询/更新：单次操作$O(\sqrt n)$。
>
> - 优点：
> > 1. 实现简单，无需复杂递归。
> > 2. 灵活支持多种操作（如块内维护哈希表统计频率）。
> >3. 空间效率高$O(n+\sqrt n)$.

- 缺点：时间复杂度较高，大数据量时性能劣于线段树。

```cpp
int belong[maxn];//belong[i] 代表第i个数属于第几块 
int sum[maxn];//sum[i] 代表第i块的和是多少 
int daxiao[maxn];//daxiao[i] 代表第i块的大小是多少 
int col[maxn];//col[i] 代表第i块被整体加了col[i] 
int main()
{
	cin >> n >> m;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	int s = sqrt(n);//每块的大小 
	for (int i=1;i<=n;i++)
		belong[i] = i/s+1;
	for (int i=1;i<=n;i++)
	{
		sum[belong[i]] += a[i];
		daxiao[belong[i]] ++;
	}
		
	for (int x=1;x<=m;x++)
	{
		int opt;
		cin >> opt;
		if (opt == 1)//询问操作
		{
			int l,r;
			cin >> l >> r;
			int ans=0;
			if (belong[l] == belong[r])
				for (int i=l;i<=r;i++)
					ans += a[i] + col[belong[i]];
			else
			{
				for (int i=l;belong[i] == belong[l]; i++)
					ans += a[i] + col[belong[i]];
				for (int i=r;belong[i] == belong[r]; i--)
					ans += a[i] + col[belong[i]];
				for (int i=belong[l] + 1; i < belong[r]; i++)
					ans += sum[i];
			}
			cout << ans << "\n";
		} 
		else
		{
			int l,r,v;
			cin >> l >> r >> v;
			if (belong[l] == belong[r])
				for (int i=l;i<=r;i++)
					a[i] += v;
			else
			{
				for (int i=l;belong[i] == belong[l]; i++)
					a[i] += v,sum[belong[i]] += v;
				for (int i=r;belong[i] == belong[r]; i--)
					a[i] += v,sum[belong[i]] += v;
				for (int i=belong[l] + 1; i < belong[r]; i++)
				{
					sum[i] += v * daxiao[i];
					col[i] += v; 
				}
			}
		}
	}
	
	return 0;
}
```

## 3. 莫队

莫队，是莫涛发明的一种解决区间查询等问题的离线算法，基于分块思想，复杂度为 $O（n \sqrt n)$主要用于解决无需修改的区间查询问题。

**莫队思想及过程**

>‌1. 分块排序优化‌
>
>>将区间划分为 n 个块，对所有查询按左端点所在块排序（同块按右端点排序），并通过奇偶性优化减少指针移动次数.
>
>‌2. 双指针暴力转移
>
>>维护两个指针L和R，通过逐步移动到目标区间边界，利用相邻区间答案的$O(1)$转移特性更新结果，例如统计区间内不同元素数量时增减计数器即可.
>
>3. 离线处理限制
>
>>需预先读取所有查询并排序，无法处理动态修改或强制在线场景，但编码复杂度显著低于线段树等在线数据结构.

Better解释请见[这里](https://www.luogu.com.cn/article/qp27w36c).

```cpp
struct query
{
	int l,r,id,ans;
}q[maxn];

bool cmp1(const query &q1, const query &q2)
{
	if (belong[q1.l] != belong[q2.l]) return belong[q1.l] < belong[q2.l];
	else return q1.r < q2.r;
}

bool cmp2(const query &q1, const query &q2)
{
	return q1.id < q2.id;
}

void ins(int x)
{
	cnt[x] ++;
	if (cnt[x] % 2 == 0) ans++;
	else if (cnt[x] != 1) ans--;
}

void del(int x)
{
	cnt[x] --;
	if (cnt[x] != 0)
	{
		if (cnt[x] % 2 == 0) ans++;
		else ans--;
	}
}

int main()
{
	cin >> n >> m;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	for (int i=1;i<=m;i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	int s = sqrt(n);
	for (int i=1;i<=n;i++)
		belong[i] = i/s+1;
	sort(q+1,q+m+1,cmp1);	
		
	for (int i=q[1].l;i<=q[1].r;i++)
		ins(a[i]);
	q[1].ans = ans;
	for (int i=2;i<=m;i++)//O(Nsqrt(N))
	{
		int l1=q[i-1].l,r1=q[i-1].r;
		int l2=q[i].l,r2=q[i].r;
		
		if (l1 < l2)
			for (int i=l1;i<l2;i++)
				del(a[i]);
		else
			for (int i=l2;i<l1;i++)
				ins(a[i]);
		
		if (r1 < r2)
			for (int i=r1+1;i<=r2;i++)
				ins(a[i]);
		else
			for (int i=r2+1;i<=r1;i++)
				del(a[i]);

q[i].ans = ans;
	}
	sort(q+1,q+m+1,cmp2);
	for (int i=1;i<=m;i++)
		cout << q[i].ans << "\n";
		
	return 0;
}
```

## 4. 分治
分治算法的基本思想是将一个规模为$N$的问题分解为$K$个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成.
### 归并求逆序对
```cpp
void merge(int l,int r)//要计算l~r这个区间有多少个逆序对
{
	if (l==r) return;
	int m=(l+r) >> 1;//(l+r)/2
	merge(l,m);//递归去算l~m的答案 a[l]~a[m] 排好序了 
	merge(m+1,r);//递归去算m+1~r的答案 a[m+1]~a[r] 排好序了 
	//i在左边 j在右边的答案 
	int p1 = l, p2 = m+1;
	for (int i=l;i<=r;i++)
	{
		if (p1 > m) b[i] = a[p2],p2++;
		else if (p2 > r) b[i] = a[p1],p1++; 
		else if (a[p1] <= a[p2]) b[i] = a[p1],p1++;
		else b[i] = a[p2],p2++,ans+=m-p1+1;
	}
	for (int i=l;i<=r;i++)
		a[i] = b[i]; 
} 
```