首页 > 代码库 > 【CF652C】Foe Pairs(线性扫描)
【CF652C】Foe Pairs(线性扫描)
题意:给你1-n的一个排列和m组数对,问有多少区间不包含任意一个数对。 (1?≤?n,?m?≤?3·105)
思路:数据范围过大,不能用容斥原理
f[i]表示以位置i上的数为左端点,右端点最小到哪里
不包含=总数-包含即可
1 var f,c:array[1..310000]of int64; 2 n,m,x,y,t:int64; 3 i:longint; 4 ans:int64; 5 6 function min(x,y:int64):int64; 7 begin 8 if x<y then exit(x); 9 exit(y); 10 end; 11 12 begin 13 //assign(input,‘cf652C.in‘); reset(input); 14 // assign(output,‘cf652C.out‘); rewrite(output); 15 read(n,m); 16 for i:=1 to n do 17 begin 18 read(x); 19 c[x]:=i; f[i]:=n+1; 20 end; 21 ans:=n*(n+1) div 2; 22 for i:=1 to m do 23 begin 24 read(x,y); 25 if c[x]>c[y] then begin t:=x; x:=y; y:=t; end; 26 f[c[x]]:=min(f[c[x]],c[y]); 27 end; 28 for i:=n-1 downto 1 do f[i]:=min(f[i],f[i+1]); 29 for i:=1 to n-1 do ans:=ans-(n-f[i]+1); 30 writeln(ans); 31 // close(input); 32 // close(output); 33 end.
【CF652C】Foe Pairs(线性扫描)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。