【CF652C】Foe Pairs(线性扫描)
2024-10-21 03:10:05
题意:给你1-n的一个排列和m组数对,问有多少区间不包含任意一个数对。 (1 ≤ n, m ≤ 3·105)
思路:数据范围过大,不能用容斥原理
f[i]表示以位置i上的数为左端点,右端点最小到哪里
不包含=总数-包含即可
var f,c:array[..]of int64;
n,m,x,y,t:int64;
i:longint;
ans:int64; function min(x,y:int64):int64;
begin
if x<y then exit(x);
exit(y);
end; begin
//assign(input,'cf652C.in'); reset(input);
// assign(output,'cf652C.out'); rewrite(output);
read(n,m);
for i:= to n do
begin
read(x);
c[x]:=i; f[i]:=n+;
end;
ans:=n*(n+) div ;
for i:= to m do
begin
read(x,y);
if c[x]>c[y] then begin t:=x; x:=y; y:=t; end;
f[c[x]]:=min(f[c[x]],c[y]);
end;
for i:=n- downto do f[i]:=min(f[i],f[i+]);
for i:= to n- do ans:=ans-(n-f[i]+);
writeln(ans);
// close(input);
// close(output);
end.
最新文章
- ASP.NET加密和解密数据库连接字符串
- 【web前端面试题整理04】阿里一行之大神面对面
- POJ1985Cow Marathon[树的直径]
- Emmet:HTML/CSS代码快速编写神器
- Jackson 框架,轻易转换JSON
- http示例代码
- Hadoop中两表JOIN的处理方法
- [Erlang危机](5.0)执行时指标
- ios UIKit动力
- 统计学习方法——CART, Bagging, Random Forest, Boosting
- MYSQL问题解决方案:Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password:YES)
- 转载redis持久化的几种方式
- ASP.NET Core 添加区域步骤(详细)
- ESLint常见命令(规则表)
- 下拉列表模仿placeholder效果
- exception: java.net.ConnectException: Connection refused; For more details see: http://wiki.apache.org/hadoop/ConnectionRefused
- [sql]sql函数coalesce返回第一个非空的值
- Ionic 使用karma进行单元测试
- mybatis中的增删改查操作
- Postman—添加断言和检查点