5.第五题难度比较大并查集删边离散化

现在小美拿到了一个仅由大写字母组成字符串她可以最多操作k次每次可以修改任意一个字符。

小美想知道操作结束后最多共有多少个M和T字符

输入描述

第一行输入两个正整数n,k代表字符串长度和操作次数。

第二行输入一个长度为n的、仅由大写字母组成的字符串。

1kn10^5

输出描述

2.操作次数为k因此最多可以min(k,add)将个字符变为M和T

#include

现在小美想知道如果那些未知的元素在区间[l,r]范围内随机取值的话数组所有元素之和的最小值和最大值分别是多少

输入描述

区间左值(res*l)反之最大值就是0的数量*区间右值(res*r)。

#include

sc.nextInt();System.out.println((sum

res

现在小美希望你回答有多少个i*i的完美矩形区域。

你需要回答1in的所有答案。

输入描述

{cnt;}}}System.out.println(cnt);}}

小美拿到了一个大小为n的数组她希望删除一个区间后使得剩余所有元素的乘积末尾至少有k个

输入描述

第一行输入两个正整数nk。

第二行输入n个正整数ai代表小美拿到的数组。

1n,k10^5

1.我们首先统计整个数组的2和5的因子3数量和每个元素对应的5的因子数量。

2.维护2个指针l,r

3.如果l,r的区间min(cnt2,cnt5)k,我们答案就累加l-r1

#include

input.nextInt();cnt2Cnt5Count();int

0;long

小美认为在人际交往中但是随着时间的流逝朋友的关系也是会慢慢变淡的最终朋友关系就淡忘了。

现在初始有一些朋友关系存在一些事件会导致两个人淡忘了他们的朋友关系。

小美想知道某一时刻中某两人是否可以通过朋友介绍互相认识

事件共有

第一行输入三个正整数n,m,q代表总人数初始的朋友关系数量发生的事件数量。

接下来的m行每行输入两个正整数u,v代表初始编号u的人和编号v的人是朋友关系。

接下来的q行每行输入三个正整数op,u,v含义如题目描述所述。

10^9

1.离线处理因为这里的n非常大1e9,后面是使用并查集构造n个节点fa***r数组肯定装不下.

2.并查集处理加边,删边转换下思路

3.如果我们已经找出所有可能要删除的边然后假设所有边都删除了构建一个最终的并查集(这个并查集并不影响后面的删边的情况)。

4.逆向遍历所有的q次操作如果是查询1操作使用并查集直接查出即可如果是删除(2操作)则往并查集添加边。

#include

{res.push_back(No);}}}reverse(res.begin(),

res.end());for

scanner.nextInt();fa***r.put(u,

u);fa***r.put(v,

{res.add(No);}}}Collections.reverse(res);for

(String

{System.out.println(s);}}static

int

觉得讲解不错的可以关注反响不错的话会更新此系列讲解视频最后的最后祝大家offer满满