题意:给你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.

最新文章

  1. ASP.NET加密和解密数据库连接字符串
  2. 【web前端面试题整理04】阿里一行之大神面对面
  3. POJ1985Cow Marathon[树的直径]
  4. Emmet:HTML/CSS代码快速编写神器
  5. Jackson 框架,轻易转换JSON
  6. http示例代码
  7. Hadoop中两表JOIN的处理方法
  8. [Erlang危机](5.0)执行时指标
  9. ios UIKit动力
  10. 统计学习方法——CART, Bagging, Random Forest, Boosting
  11. MYSQL问题解决方案:Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password:YES)
  12. 转载redis持久化的几种方式
  13. ASP.NET Core 添加区域步骤(详细)
  14. ESLint常见命令(规则表)
  15. 下拉列表模仿placeholder效果
  16. exception: java.net.ConnectException: Connection refused; For more details see: http://wiki.apache.org/hadoop/ConnectionRefused
  17. [sql]sql函数coalesce返回第一个非空的值
  18. Ionic 使用karma进行单元测试
  19. mybatis中的增删改查操作
  20. Postman—添加断言和检查点

热门文章

  1. C#基于联通短信Sgip协议构建短信网关程序
  2. iOS 资源大全整理
  3. Mysql数据库插入中文出现乱码相关
  4. matlplotlib根据函数画出图形
  5. 【MySql】Mysql ERROR 1067: Invalid default value for ‘date’ 解决
  6. k8s的资源限制及资源请求
  7. Qt概念和快捷键
  8. nginx作为正向代理,反向代理的一些应用
  9. java上传附件,批量下载附件(一)
  10. Tomcat Bug记录