首页 > 其他分享 > AT_abc260_e

AT_abc260_e

时间:2023-10-23 22:35:31浏览次数:29  
标签:www cn ai 合法 abc260 区间

给出 n 对点 ai ,bi ,在[1,m] 之间取一段区间。

当每一对点都有一个点在这个区间内时,这个区间合法。

求出不同长度的合法区间分别有多少个。

 

枚举 l,   右边r有个最小值R(l), 而 (l, j) j>r 之后的点都是合法点, 后面就是区间加,用差分维护

 

考虑这个 R (l) ,

可以预处理: 先做出单点  然后,用前缀思想 ,R[i] =max( R[i-1], R[i], i)

 

https://www.luogu.com.cn/record/131279233

标签:www,cn,ai,合法,abc260,区间
From: https://www.cnblogs.com/towboa/p/17783645.html

相关文章

  • abc260F - Find 4-cycle
    F-Find4-cycle显然就是在一个集合中枚举两个点,然后看在另一个集合中是否存在两个点与这个集合中的两个点都相连。假设x是v1中的一个点,设它的两条出边是(x,a),(x,b),那么记录下f[a][b]=x,根据鸽巢原理,这样做是n^2的#include<cstdio>#include<algorithm>#include<cstring>#in......
  • abc260_f Find 4-cycle 题解
    Find4-cycle题意有一个\(s+t\)个点\(m\)条边的简单无向图\(G\)。点标号为\(1\cdotss+t\),边标号为\(1\cdotsm\)。第\(i\)条边连接点\(u_i\)和\(v_i\)。如果\(G\)中包含一个大小为\(4\)的简单环,选择任意一个并按任意顺序输出环上的\(4\)个点。若不存......
  • abc260_e At Least One 题解
    AtLeastOne题意给定一个整数\(m\)和\(n\)对数\((a_i,b_i)\),我们定义一个\(f(x)\)函数表示满足以下要求的整数序列数量:整数序列为\((1,2,3\cdotsm)\)的一个子段且序列长度为\(x\)。对于\(1\leqslanti\leqslantn\),满足\(a_i\)或者\(b_i\)在整数序列......
  • 2023.5.16 总结 AT_abc260_g
    atcoderAT_abc260_g题意一个点O可以影响到其它点,能影响到的点的坐标满足:(\((u,v)\)为当前点的坐标,\((x,y)为能影响到的点的坐标\))\(u\lex\)\(v\ley\)\((x-u)+\dfrac{(y-v)}{2}<M\)给\(q\)个询问,问每个点会被几个O给影响。思路题解算法标签差分,很恶......
  • abc260_g Scalene Triangle Area 题解
    题目传送门题意给定一个大小为\(n\timesn\)的字符矩阵,每个字符为X或者O。对于一个位于\((x,y)\)的字符o和一个格子\((u,v)\),如果满足以下条件,那么\((u,v)\)就可以被\((x,y)\)控制。\(x\leqslantu\leqslantn\),\(y\leqslantv\leqslantn\)。\((u-x)+\fr......