TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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被坑之后更正数据范围