首页 > 其他分享 >cf1209g2-solution

cf1209g2-solution

时间:2024-02-27 20:48:14浏览次数:33  
标签:颜色 最大值 solution mxs cf1209g2 区间

CF1209G2 Solution

link

根据题意,对于一个颜色的所有下标集合 \(S\),设其最小,最大位置是 \(l,r\),那么最后染完色的 \([l,r]\) 区间一定是同一种颜色。

如果有两个颜色 \(i,j\),\([l_i,r_i]\) 和 \([l_j,r_j]\) 有交集,那么这个区间并起来的大区间也一定是同一种颜色的。

这样我们并并并可以得到一些互不相交,且覆盖了 \([1,n]\) 的区间。设对于一种颜色 \(i\),其集合大小为 \(s_i\)。

对于每个区间,把区间内数都变成一样的操作代价显然是 \(r-l-mxs\),\(mxs\) 是区间内原来颜色的 \(s\) 的最大值。

下面是妙妙转化。对于每个颜色 \(i\),设一个数组 \(b\)。我们把 \([l_i,r_i)\) 的 \(b\) 加 \(1\)。那么每个 \(b_i=0\) 的位置就是大区间的末尾。

再来一个数组 \(c\),把每种颜色的下标数量放在 \(c_l\)。现在要求的就是,按照 \(b\) 的 \(0\) 分段后每段的 \(c\) 最大值之和。

还要支持 \(b\) 的区间加减、\(c\) 的单点修改。这些可以用线段树维护。

具体地,维护每个区间的最大值,从左端点向右/右端点向左一段的最大值,以及区间的答案,push_up 容易实现。

复杂度 \(O(n\log n)\)。

标签:颜色,最大值,solution,mxs,cf1209g2,区间
From: https://www.cnblogs.com/iorit/p/18038177

相关文章

  • cf1153f-solution
    CF1153FSolutionlink题意:有一段长为\(l\)的线段,有\(n\)个实数区间,左右端点在\([0,l)\)间均匀随机。求期望被至少\(k\)段区间覆盖的长度,对\(998244353\)取模。\(1\lek\len\le10^7,1\lel\le10^{10^6}\)首先\(l\)是没用的,我们可以计算线段长为\(1\)时的......
  • cf1148h-solution
    CF1148HSolutionlink对于区间mex,若固定一个右端点\(r\),左端点\(l\)越小mex肯定越大。假设我们维护了右端点为\(n\),左端点为\(i\in[1,n]\)的区间mex(设为\(b_i\)),考虑在序列末尾加入一个数\(x\):显然有且仅有原先\(b_i=x\)的一段\(b\)会被改掉。改成什么呢?大概......
  • cf1184a3-solution
    CF1184A3Solutionlink题意:给你两个长度为\(n\)的小写字符串\(s,t\)和一个\(m\),定义哈希函数\[h(s)=\left(\sum_{i=0}^{n-1}s_ir^i\right)\bmodp\]求构造\((p,r)\)且\(p\gem,r\in[2,p-1]\),使得\(h(s)=h(t)\)。\(n,m\le10^5\)。题目即求一个多项式\(f(x)=\sum_{......
  • cf1188e-solution
    CF1188ESolutionlink考虑\(x_i\)表示最后序列中每个数被操作的次数。显然我们可以假设\(\min\{x_i\}=0\)。仍然显然的是这样子的\(x\)序列与最后得到的序列一一对应,也就是说每个最终序列可以只能由一种\(x\)得到。那么就变成计数合法的\(x\)序列了。考虑\(x_i\)需......
  • cf1205d-solution
    CF1205DSolutionlink题意:给你一棵\(n\)个节点的树。请你给它的\(n-1\)条边确定权值,使得树上\(\dbinomn2\)条路径的权值和包含\(\displaystyle1\sim\left\lfloor\frac{2n^2}9\right\rfloor\)中所有整数。\(n\le1000\)。注意到有关树上路径问题,我们考虑设\(rt\)......
  • Rancher 无法删除集群的Solution
    Rancher无法删除集群的Solution不同版本的Rancher都能遇到该问题,此问题中,Rancher版本为v2.6.0当我们先删除节点,并在节点宿主机上删除了对应的服务器,再通过Rancher界面去删除托管/自建立集群时,往往这个操作会卡住,并出现报错:{"type":"error","links":{},"code":"PermissionDe......
  • Solution Set #11
    177qoj7607.TheDoublingGame2首先可以发现对于一个局面,操作到这个局面的方案是唯一的(考虑一条边左右的棋子数量,可以知道这条边的移动方向,删去所有不移动的边之后,每个联通块只有一个点有棋子,而对于只有根有棋子的局面构造显然唯一)据此可以\(\mathcal{O}(n^2)\)DP:设\(f_{u......
  • 2.22 闲话 & solution 『虽然我不是神/不像他们无所不能/却总畏惧一语成谶』
    有↑没有↓谁↑能够↓代↑替↓我↑(去考开学的一调)唐氏模拟赛,板子大战,全场都是板子,\(\textT3\)甚至还不如板子,\(byd\)题解居然是用的高贵的\(O(n\logn)\)算欧拉函数,唐\(\text{lxyt}\)复活赛打赢了可以去打\(\text{HEOI2024}\)了,体验名额DZ和xrlong的代码进行了大量对拍,仍......
  • solution-div2contest-D
    题面可以在link看到?大力手玩题!场切了!首先看到这种题,我们一定是先想给定一个树怎么求他的最大独立集。我忘记怎么贪心了,于是考虑DP,设\(f_{u,0/1}\)表示以\(u\)为根的子树中独立集包含或不包含\(u\)这个点的最大独立集大小。转移是显然的,为了下文讲解方便还是在这里写出......
  • 2.21闲话 & solution『 有没有/谁/能够代替我』
    上午有唐氏模拟赛,100/0/0/20,rk7/15,鉴定为最唐的一次T1签到题,思路很简单题面ame是一个可爱的女孩子,她想要你帮她排序。给定\(4\timesn\)个数,要求将其分为\(n\)组,使得对于每组四个数,所有组中的\(|a\timesb-c\timesd|\)和最大,求最大和。排序,对于前\(2n\)大的,尽量把大......