Submission #47953414

---

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 Data.Array.IO

main :: IO ()
main = do
  [n,q] <- bsGetLnInts
  as <- bsGetLnInts
  abc330e n q as

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

abc330e :: Int -> Int -> [Int] -> IO ()
abc330e n q as = -- snd $ mapAccumL step (arr0, mis0, mex0) ixs
  do
    arr <- newListArray (1,n) as :: IO (IOUArray Int Int)
    foldM_ (\(mis, mex) _ -> do
      [i,x] <- bsGetLnInts
      ai <- readArray arr i
      writeArray arr i x
      let mis1 = insertMIS x $ deleteMIS ai mis
      let mex1 = insertMEX x $ if memberMIS ai mis1 then mex else deleteMEX ai mex
      print $ mexMEX 0 mex1
      return (mis1, mex1)
      ) (mis0, mex0) [1..q]
  where
    mis0 = fromListMIS as
    mex0 = foldl' (flip insertMEX) IM.empty as

-- 多重集合
-- @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
-- 含まれる整数を区間で記憶する
type MexSet = IM.IntMap Bool

insertMEX :: Int -> MexSet -> MexSet
insertMEX x ms
  | memberx = ms
  | expandLow && expandHigh = IM.delete x        $ IM.delete x1 ms
  | expandLow               = IM.insert x1 False $ IM.delete x  ms
  |              expandHigh = IM.insert x  True  $ IM.delete x1 ms
  | otherwise               = IM.insert x1 False $ IM.insert x  True ms
  where
    x1 = succ x
    low  = IM.lookupLE x ms
    high = IM.lookupGT x ms
    expandLow  = maybe False ((x  ==) . fst) low
    expandHigh = maybe False ((x1 ==) . fst) high
    memberx = maybe False snd low

mexMEX :: Int -> MexSet -> Int
mexMEX x ms =
  case IM.lookupGT x ms of
    Just (b,False) -> b
    _ -> x

deleteMEX :: Int -> MexSet -> MexSet
deleteMEX x ms
  | notmemberx = ms
  | shrinkLow && shrinkHigh = IM.delete x       $ IM.delete x1 ms
  | shrinkLow               = IM.insert x False $ IM.delete x1 ms
  |              shrinkHigh = IM.insert x1 True $ IM.delete x  ms
  | otherwise               = IM.insert x1 True $ IM.insert x False ms
  where
    x1 = succ x
    low  = IM.lookupLE x ms
    high = IM.lookupGT x ms
    shrinkLow  = maybe False ((x1 ==) . fst) high
    shrinkHigh = maybe False ((x  ==) . fst) low
    notmemberx = not $ maybe False snd low

Submission Info

Judge Result