@HoshinoTented 2019-07-22 16:19 回复
{-# LANGUAGE BangPatterns #-}

import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed ((!), (//))

type UnionFind = V.Vector Int
type UnionFindM = State UnionFind

ask :: UnionFind -> Int -> (UnionFind, Int)
ask !vec !i = if vec ! i == i then (vec, i) else
let (!vec', !result) = ask vec  $vec ! i in (vec' // [(i, result)], result) cat :: UnionFind -> Int -> Int -> UnionFind cat !vec !x !y = let (!vec', !x') = ask vec x in let (!vec'', !y') = ask vec' y in vec // [(x', y')] resolve :: Int -> UnionFind -> IO () resolve 0 _ = return () resolve !n !uf = do [!z, !x, !y] <- map read . words <$> getLine :: IO [Int]

!uf' <- if z == 1 then return  $cat uf x y else let (!vec, !x') = ask uf x (!vec', !y') = ask vec y in putStrLn (if x' == y' then "Y" else "N") >>= const (return vec') resolve (n - 1) uf' main :: IO () main = do [n, m] <- map read . words <$> getLine :: IO [Int]

-- omitted

main :: IO ()
main = do
[n, m] <- map (read . T.unpack) . T.words <$> I.getLine -- omitted @千里冰封ice 2019-07-23 05:36 回复 举报 读入优化 我自己不是很信任 read 的性能——它实际上是一个 Haskell object 的 Parser，而不是类似 scanf 那样的纯粹的数据读取器。 事实上，经过测试，这个读入优化是必须的。 这个读入优化和 C 系语言的 OI 读入优化思路差球不多，都是钦点读入数据一定是合法的 Int import Data.Char int :: String -> Int int s = int' s 0 where int' [ ] n = n int' (c:cs) n = int' cs$ n * 10 + (ord c - ord '0')



resolve n uf = do
[z, x, y] <- map (int . T.unpack) . T.words <$> I.getLine -- omitted main = do [n, m] <- map (int . T.unpack) . T.words <$> I.getLine
-- omitted
@千里冰封ice 2019-07-23 05:43 回复 举报

调整优化的编译参数

{-# LANGUAGE Strict #-}

{-# GHC-OPTIONS -O2 #-}
@千里冰封ice 2019-07-23 05:44 回复 举报

@千里冰封ice 2019-07-23 05:58 回复 举报