【题意】

n个奶牛排成一排,顺次编号为1n
John每次给队头发一个礼物,然后队头移动到后面去
若奶牛i是队头,则它拿到礼物后会插入到倒数第ai个奶牛的前面
John发了+次礼物,则有多少个奶牛一个礼物也拿不到呢?

【数据范围】

n100000

想了很久不得 于是膜了leoly的代码 什么为什么别人比我快这么多? 因为没有线段树..

每次我可以去二分一下我认为这头牛他会得到礼物 那么什么情况下他不会得到礼物呢 那么就是他前面的牛 所去到的位置全部都在他前面的时候我这头牛就一定得不到  那么就 把认为能得到礼物的边界那个人缩小

 

线段树:leolyun的做法

可以想象 我一定是由于前面的前缀陷入了循环导致后面无法get礼物  问题在于怎么寻找这个最小的环  我可以预处理 每个位置都是由哪些牛到来 那么我可以知道 如果我到这部分的总牛数>=i的时候说明我有可能是答案了 这时候我需要去贰分一下  找到最后一个是谁填满了我前面i个前缀 如果我是前面的一部分人 恰好填满到i那么说明我那个人有可能就是答案 所以我认为只需要找到第一个与之相等的地方退出即可 即到达前i个位置的数他之前的数能够满足构成循环

update进一步思考 我认为只要陷入循环 我给他重新编号之后偶可以直接认为是一个前缀在循环就是因为这个最终循环状态中我一定是整个前缀都参与了这个循环所以 因为最后问多少个牛没拿到 不妨 进行重新编号也不会影响

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论