2024.2.6

T1 珠子

小 F 有 $n $颗珠子排成一个序列，每个珠子有一个颜色，颜色共有 $m $种，编号为 $1,2,…,m $。她想取出一段连续的珠子，对于每一种颜色 $i $，要求取出的珠子个数在 \([l_i,r_i] ( 0 \leqslant l_i \leqslant r_i \leqslant n)\)之间。求有多少种取珠子的方案。

暴力：前缀和处理前\(i\)位第\(j\)类珠子的总数，用\(n^2\)枚举\(l,r\)

期望：\(60pts\)

没用前缀和：\(30pts\)

正解：双指针

先固定左端点，然后分别去找满足颜色要求的最小\(r_1\)(一般是满足下限)和最大\(r_2\)（一般是达到上限），由于\(r_1 \sim r_2\)各颜色数目显然单调不减，所以一对\((r_1,r_2)\)对答案的贡献就是\(r2 - r1 + 1\)

至于怎么较快的找到\(r_1,r_2\)，不会先咕咕

T2 数组

初始\(a_i = i\),现有两种操作

• \(A\)：已知\(p,q\)，修改所有数，\(a_i = p \times i + q\)

• \(B\)：已知\(x,y\)，将\(a_x\)改为\(y\)

给出若干操作，在每次操作后输出数组元素和

第一个好办，看第二种

第二种的麻烦点在于上一次\(x\)位置的\(B\)操作可能会被\(A\)覆盖掉，所以要记录上一次\(A\)操作的时候\(num\)，以及\(x\)处的上一次\(B\)操作的时候\(tag\)

如果\(tag \leqslant num\)，说明上一次的\(B\)操作已经被覆盖掉了，那么就减去上次\(A\)操作改的值，加上\(y\)

否则减去上次\(B\)操作改成的值\(y'\)，加上\(y\)

for(int i = 1;i <= m;i++)
{
	cin >> op;
	if(op == 'A')
	{
		cin >> t[i].p >> t[i].q;
		cnt = i;//记录最新A操作的时候
		sumq = 0;//覆盖掉
		cout << (ll)t[i].p * sum + t[i].q * n << '\n';
	}
	if(op == 'B')
	{
		cin >> t[i].p >> t[i].q;
		if(tag[t[i].p] <= cnt)//上次该处的B已被覆盖
		{
			sumq = sumq + (ll)t[i].q - (ll)(t[cnt].p * t[i].p + t[cnt].q);// 减去A操作留下的值(p*i+q),加上y
			tag[t[i].p] = i;
		}
		else
		{
			int y = tag[t[i].p];
			sumq = sumq + t[i].q - t[y].q;//减去上次B操作留下的值
			tag[t[i].p] = i;
		}
		cout << (ll)t[cnt].p * sum + n * t[cnt].q + sumq << '\n';
	}
}

蒟蒻没有考虑到\(A\)操作会覆盖\(B\)，只得了一半分，gg

T3 幸运区间

已知\(\{a_i\}\)，定义幸运区间为区间内所有数的\(\gcd = 1\),求幸运区间数

暴力：分解质因数，拿质因子搞

\(20pts\)（主要是数组开不了那么多）

正解：双指针(byd)

考虑一个显然的结论：若一个序列存在一个子序列，其所有数的\(\gcd = 1\)，那么这整个序列的数的\(\gcd = 1\)

那么，每次固定左端点，找到最小的\(r\),满足\([l,r]\)中元素\(\gcd = 1\)，那么根据结论：\([l,r],[l,r + 1],[l,r + 2] \cdots [l,n]\)均为幸运区间，也就是说一个\(r\)对答案的贡献\(ans += n - r + 1\)

至于找到最小的\(r\)，可以使用一些数据结构来维护

还有一点：有结论我们还可推得：一个序列的\(\gcd = 1\)，这个序列的子序列的\(\gcd\)一定\(\geqslant1\)，所以找到\(r\)后，我们可以固定\(r\)，跳\(l\)，这样就可以省时间了

int l=1,r=1;
for(l=1;l<=n;l++)
{
	r=max(l,r);//双指针思想，性质保证了可以固定r跳l，这样就是O(n)
	while(l<=r&&r<=n)
	{
		if(st.getgcd(l,r,1,n,1)==1) break;//此处使用线段树，由结论可知gcd有传递性
		r++;
	}
	ans+=n-r+1;
}

T4 找不同

已知一串单词，给定若干区间，判断每个区间中是否有重复单词

先Hash，此处使用map开的mp和last

类比HH的项链，不同单词即不同颜色，那么没有重复就是区间内颜色种类等于区间长度

蒟蒻没想到类比，打的暴力，又gg了，只能说树状数组那章是划水过来的

for(int i = 1;i <= q;i++)
{
	int l1 = b[i].l;
	int r1 = b[i].r;
	while(pos <= r1)
	{
		add(pos,1);
		if(last[mp[pos]] == 0) last[mp[pos]] = pos;//记录上一次出现位置
		else
		{
			if(last[mp[pos]] < pos)//上一次出现位置在区间内
			{
				add(last[mp[pos]],-1);//把原来加的1减掉
				last[mp[pos]] = pos;//更新
			}
		 } 
		 pos++;
	}
	ans[b[i].id].val = sum(r1) - sum(l1 - 1);
	ans[b[i].id].l = l1;
	ans[b[i].id].r = r1;
}

两道双指针题给蒟蒻的第一感觉就是：\(l,r\)只会往一个方向走，不会反向跳到某一位置