10.28校队每日一题思路记录
10.28题目
最开始思路用了一节课想，大体就是从n往1遍历，然后数列被i分为两个部分，不含1的那一部分中的数由于有i的阻挡必然不可能连续，故找到其中的最小值并将大于等于它并且小于i的数字全部标记为0即可
然后不出所料WA了，还是WA on test 2（实际上第一遍写连样例都没过）
在经过两次缝缝补补后仍然WA，遂晓得这个思路不对（但由于手头没有能跑对的代码，cf也没法看完整测试点，实在无从下手）
然后换思路了，标签有个双指针，看的时候不知道怎么用，想了一会，有了点思路
其实原本第一次的思路就是找到含有1~i的最短连续序列，检测序列内是否只含有1~i（实际上只检测区间元素个数就够了），当时没想到怎么用双指针，只想到暴力遍历找区间长度，但这显然会超时，所以换思路了。现在反过来想一想，既然已经用map存了数字的下标，那么遍历1~n的时候对于新增加的i只需要让左指针或者右指针延伸到那里就行了，即 l = min(mp[i],l) , r = max (mp[i],r) 。
然后就开始我的犯病之路了
当时觉得没法直接判定区间长度和i不相等的时候就为0（数学菜鸡，没想出来怎么证明），遂想了歪招，记录1~n的下标的前缀和，然后计算区间内元素的下标和，判断是否相等。
想象很美好，但是WA
由于CF并不提供完整测试点数据的查看，于是我虽然知道最后几位存在1错判0的情况，但并不知道怎么错的，苦恼半天无从下手。
然后水群的时候在校队群内看到老登们直接判的区间元素个数和i，这才反应过来自己想麻烦了，把自己代码一顿修改后终于AC了芜湖！。
实际上证明起来也不算难 所以既然不难你为什么没想到
大致证明就是：由于从1~n遍历含有1~i的连续最短区间（由上面那段划线代码实现），那么当进入对i的判断时，该区间内一定已经含有1~i-1，即区间长度至少为i-1，那么加入i以后，区间延长使得其包含了i，只有该区间长度一样为i才能保证区间内含有1~i所有元素而不包含其他大于i的元素。任意大于i的元素插入该序列都会导致区间元素长度+1.
实际上我的代码实现跟指针毫无关系