首页 > 其他分享 >区间满足条件的子区间计数

区间满足条件的子区间计数

时间:2024-02-13 12:00:29浏览次数:43  
标签:满足条件 题意 minn 线段 计数 最小值 maxn 区间

区间满足条件的子区间计数

一般是扫描线,可能会有线段树维护历史版本信息。

CF526F Pudding Monsters

题意:给定一个 \(n \times n\) 的棋盘,其中有 \(n\) 个棋子,每行每列恰好有一个棋子。对于所有的 \(1 \leq k \leq n\),求有多少个 \(k \times k\) 的子棋盘中恰好有 \(k\) 个棋子。

思路:首先是一步转化,即把条件变成\(r-l=max-min\),正确性显然,于是转成了一维的问题。

考虑分治。当前要求的是跨过\(mid\)的合法区间数。于是分类讨论,如果最大、最小值都在某一侧,那么就相当于是\(j=i+maxn[i]-minn[i]\)或者\(j=i-(maxn[i]-minn[i])\),可以直接判断是否合法。另一种是最大、最小值不在同一侧,那么就有$minn[i]+i=maxn[j]+j \(或者\)minn[i]-i=maxn[j]-j $,可以直接双指针求解。写起来有些细节。

CF1004F Sonya and Bitwise OR

题意:单点修改,求一个区间有多少子区间满足按位或和至少为 \(x\)。

思路:类似 [Ynoi2014] 不归之人与望眼欲穿的人们 的做法,不过直接用线段树就是\(O(n\log a+m\log n\log a)\)的,而且比较好写。

CF997E Good Subsegments

题意:有一个\(1-n\)的排列\(P\),如果区间\([l,r]\)中的数是连续的,那么我们称它为好区间。有\(q\)次询问,每次问\([l,r]\)内,有多少子区间是好的?

思路:一道线段树维护区间历史贡献加和的题。

考虑把原条件转化成求有多少区间满足 \(max-min-(r-l)=0\)。然后考虑扫描线,然后用线段树维护区间最小值及最小值的历史出现次数。

具体的维护方法是设 \(sum\) 表示当前区间的最小值的历史出现次数,\(cnt\) 表示当前区间的最小值出现次数要对历史出现次数的贡献,然后下传标记时先下传加法标记然后下传对历史出现次数的贡献即可。

CF1609F Interesting Sections

题意:求有多少子区间满足最大值的 \(popcount\) 等于最小值的 \(popcount\)。

思路:有好多做法,写的是 tzc_wk 的扫描线做法。

考虑每次把 popcount 相同的位置当做关键位置,然后就相当于是有多少区间的最大值和最小值都是关键位置,于是记 \(f_l\) 表示 \([l,r]\) 的最大值是否是关键位置 + \([l,r]\) 的最小值是否是关键位置,然后就相当于是求最大值及出现次数,修改就是区间修改,于是可以用线段树维护。

标签:满足条件,题意,minn,线段,计数,最小值,maxn,区间
From: https://www.cnblogs.com/Xttttr/p/18014464

相关文章

  • 连续性区间位置查询——链式并查集
    目录问题概述思路分析参考代码做题总结问题概述这里给出两个题目,一个是上一篇的新春漫步(其实当时给的官方题解就是链式并查集的写法,但是当时我懒得写了,emmm),二是最近vp的一场cf_div3_923场的d题,准确来说,就是因为这个我才准备写这个的,题目大概就是给出一个长度为n的数组和q组询......
  • 【数据库】对大数据量数据集,PostgreSQL分组统计数量,限定每组最多数量
    一、背景介绍在处理大数据量数据集时,我们经常需要进行分组统计。例如,我们需要统计每个城市的人口数量、每个年龄段的人数等。在PostgreSQL中,我们可以使用row_number()函数结合over(partitionby)子句来实现这个功能。同时,为了限定每组最多数量,我们可以使用row_num<=100......
  • POJ--1179 Polygon(区间DP)
    记录22:012024-2-10http://poj.org/problem?id=1179区间DP问题。区间DP问题可能需要注意的点就是是根据区间长度来计算的,随着迭代区间长度不断增加,结果也就计算出来了这种“任意选择一个位置断开,复制形成2倍长度的链”的方法,是解决DP中环形结构的常用手段之一因此读入数......
  • 三、四元环计数
    无向图三元环计数:定义一个有向图\(G'\):把\(G\)中每条边改成从度数小的点指向度数大的点的有向边。性质:\(G'\)中每个点的出度\(\le2\sqrtm\)。证明:若\(u\)的出度\(>2\sqrtm\),则显然\(u\)在原图中的度数\(>2\sqrtm\)。所以\(u\)指向的至少\(2\sqrtm+1\)个......
  • 牛牛的等差数列(树状数组,区间加等差数列、区间求和)
    https://ac.nowcoder.com/acm/contest/5157/C区间加等差数列,区间求和树状数组,二阶差分\(b_i=a_i-a_{i-1}\)\(c_i=b_i-b_{i-1}\)\[\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^ib_j=\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^jc_k\\=\sum_{k=1}^nc_k\sum_{i,j}[k\......
  • 数字式频率计、通用计数器、高精度频率计的操作使用说明
    在选择测量仪器之前必须了解待测信号的所有特性,附非肯定待测信号是纯净(无噪声干扰)、平稳、单一频率成分,否则应该在制订测试方案前用频谱分析仪先观测待测信号中的干扰信号及噪声电平,然后看计数器的性能是否能允许这些干扰并仍能成功地完成频率的测量。给相应通道输入频率信号,点击启......
  • 使用NumPy实现对满足条件的Tensor索引和值的提取
    在Python中,使用NumPy库可以方便地进行对多维数组(即Tensor)的操作。本文将介绍如何使用NumPy库实现对满足条件的Tensor索引和值的提取,以便读者更好地理解和应用这些功能。一、背景知识NumPy是Python中用于科学计算的核心库之一,提供了多维数组对象和各种工具,可以用来处理数组、矩阵以......
  • 区间统计
    问题:根据J列数据分别统计等于1的客户数;大于1小于等于5的客户数;大于5小于等于7的客户数;大于7小于等于10的客户数;大于10小于等于15的客户数函数公式思路1:P4公式 =COUNTIF(J:J,O4)P5公式 =COUNTIFS(J:J,">"&O4,J:J,"<="&O5)P4公式计算J列中等于O4的个数P5公式计算J列中小于O......
  • 括号序列计数
    1.设\(f(n,m,k)\)表示有\(n\)个左括号,\(m\)个右括号,子序列中合法括号序列最长长度为\(2k\)的括号序列,转移为\[f(n,m,k)=\left\{\matrix{{n+m}\choosen&&k\gemin(n,m)\\f(n-1,m,k-1)+f(n,m-1,k)&&k<min(n,m)}\right.\]通过归纳可以得到\[f(n,m,k)=\left\{\ma......
  • 第十五节:排序算法详解3(希尔排序、计数排序、桶排序、基数排序)
    一.        二.        三.         !作       者:Yaopengfei(姚鹏飞)博客地址:http://www.cnblogs.com/yaopengfei/声     明1:如有错误,欢迎讨论,请勿谩骂^_^。声     明2:原创博客请在转载......