Submission #48036884

---

Source Code Expand

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import qualified Data.IntMap as IM
import qualified Data.IntSet as IS

main :: IO ()
main = do
  [n,q] <- bsGetLnInts
  as <- bsGetLnInts
  ixs <- replicateM q bsGetLnInts
  let ans = abc330e n q as ixs
  mapM_ print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc330e :: Int -> Int -> [Int] -> [[Int]] -> [Int]
abc330e n q as ixs = snd $ mapAccumL step (arr0, mis0, mex0) ixs
  where
    arr0 = IM.fromDistinctAscList $ zip [1..] as
    mis0 = fromListMIS as
    mex0 = IS.fromDistinctAscList [0..n + q] IS.\\ IS.fromList as
    step (arr, mis, mex) (i:x:_) = ((arr1, mis1, mex1), IS.findMin mex1)
      where
        ai = arr IM.! i
        arr1 = IM.insert i x arr
        mis1 = insertMIS x $ deleteMIS ai mis
        mex1 = IS.delete x $ if memberMIS ai mis1 then mex else IS.insert ai mex

-- 多重集合
-- @gotoki_no_joe
type MultiIntSet = IM.IntMap Int

fromListMIS :: [Int] -> MultiIntSet
fromListMIS xs = IM.fromListWith (+) [(x, 1) | x <- xs]

insertMIS :: Int -> MultiIntSet -> MultiIntSet
insertMIS x ms = IM.insertWith (+) x 1 ms

deleteMIS :: Int -> MultiIntSet -> MultiIntSet
deleteMIS x ms = IM.update dec x ms
  where
    dec 1 = Nothing
    dec n = Just $ pred n

memberMIS :: Int -> MultiIntSet -> Bool
memberMIS x ms = IM.member x ms

{-
公式解説のやり方。MEXの専用データ構造がなくても、単純な整数集合で補集合を追跡するだけでいい。
-}

Submission Info

Compile Error

app/Main.hs:26:5: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘step’:
        Patterns of type ‘(IM.IntMap IS.Key, MultiIntSet, IS.IntSet)’,
                         ‘[IS.Key]’ not matched:
            (_, _, _) []
            (_, _, _) [_]
   |
26 |     step (arr, mis, mex) (i:x:_) = ((arr1, mis1, mex1), IS.findMin mex1)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

Judge Result