TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5945
  • 题目
  • P5945超级贞鱼
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    马达加斯加贞鱼是一种神奇的双脚贞鱼,它们把自己的智慧写在脚上——每只贞鱼的左脚和右脚上个有一个数。
    有一天,K只贞鱼兴致来潮( \(1≤k≤10^5\)),排成一列,从左到右第i只贞鱼会在右脚写Ai( \(1≤Ai≤10^9\)),左脚上写上i(1≤i≤K),
    第二年,这K只贞鱼按右脚的数从小到大排成一列,然后,它们决定重编号,从左到右第i只贞鱼会在右脚上写上左脚的数,在左脚上写i,
    第三年,它们按第二年的方法重排列、重编号......n年后( \(1≤n≤10^5\)),对于从左到右第i和第j贞鱼,若i<j且第i只贞鱼右脚上的数比第j只贞鱼右脚上的数大,则称它们为一对“超级贞鱼”。
    问一共有多少对“超级贞鱼”。

    输入格式

    一共3行,第一行一个正整数k(\(1≤k≤10^5\)),
    第二行k个数从左到右输入Ai( \(1≤Ai≤10^9\)),
    第三行一个正整数n( $1≤n≤10^5 $)。

    输出格式

    一个整数,表示“超级贞鱼”对数。

    样例输入

    6
    5 2 6 3 1 7
    0

    样例输出

    7

    提示

    对于全部数据:\(Ai≤10^9\)
    30%的数据:n,k<=400;
    70%的数据:n,k<=10000;
    100%的数据:n,k<=100000;
    \(k\le 2\times10^6, n\le 10^{18}\)


    来源  bzoj 4769,感谢nodgd被坑之后更正数据范围