24/11/30 ABC381+莫队+分块+整体二分学习笔记

[ABC381D]

好题。
由于题目描述中提到了取出的子序列长度必须是偶数个，所以可以考虑对于原来的\(a\)序列每次进行长度为\(2\)的尺取，这时候不难发现对于开头位置具有两个答案，一个是从\(1\)为开头，一个是从\(2\)为开头，所以写个函数封装一下就好了，类似这种cout << max(solve(1),solve(2))。

接下来考虑在尺取过程中如何计算答案的贡献，设当前枚举到的区间开头为\(l\),结尾是\(r\)，每个数出现的次数是\(cnt_i\)，拥有以下两种情况：

• 第一种：\(a_r \ne a_{r+1}\)
  针对这种情况，显然是对于\(a_r\)和\(a_{r+1}\)这两个位置都不可取(Q：为什么不可以取\(a_{r+1}\)呢? A:若取了\(a_{r+1}\)，那么后面答案计算出来的都是成对出现的，一定是偶数个，加上这个序列长度就会变成奇数个)，既然这两个位置不可取，那么所有包含他俩的子序列都不可取，所以将\(l \to r\)这段区间所有的数都扔掉，即这段区间所有数的出现次数\(-1\)，同时将\(r\)变成\(r+2\)(即下个尺取的地方)，\(l = r\)。

if(a[r] != a[r+1])
{
	for(int i = l;i < r;i++) cnt[a[i]]--;
	r = r+2;
	l = r;
}

• 第二种:\(a_{r} = a_{r+1}\)
  针对这种情况，我们对于\(l \to r\)这段区间还要满足第三个条件，也就是题目中说到的所有数出现次数不是\(0\)次，就是\(2\)，直接从\(l\)开始,不断地将\(l + 2\)并同时减去\(a_l\)与\(a_{l+1}\)出现的次数，直到满足\(cnt_{a_r} = 2\)，最后将\(r+2\)，变动一下就好了。

else
{
	cnt[a[r]]++,cnt[a[r+1]]++;
	while(l < r && cnt[a[r]] > 2)
	{
		cnt[a[l]] -= 2;
		l += 2;
	}
	r += 2;
}

那么最后对于所有计算过程中算到的答案取一个\(\max\)即可。

[ABC381E]

好题。
如果将题面抽象一下的话，其实跟龙之研习差不多，比较有意思，如果做过这场ABC的C题的话，有可能会受到启发。

我们考虑将每一个/的位置用数组记录下来，针对每一个/所产生的答案，显然为(其左侧\(1\)的个数和其右侧\(2\)的个数)\(\times 2+1\)，随着/位置的向右侧移动，显然发现\(1\)的个数在单调递增，\(2\)的个数在单调递减，可以考虑二分，二分方法如下：

用数组记录每个/的位置，二分出任意一个/，判断这个位置是否在查询的区间内，不在的话就移动\(l\)或\(r\)；提前预处理出针对每一段区间\(1\)的个数和\(2\)的个数，显然可以用前缀和,\(O(1)\)计算当前/左侧\(1\)的个数和\(2\)的个数，贡献计算方式上面写了，对于单调性问题，我们显然是尽可能让右侧的\(1\)的数量增加，故当\(c_1 <= c_2\)时，l=mid+1

Submission