题面。
算是比较简单的题目了，自己多手出几个样例就可以发现规律了。
强烈建议多读几遍题目！！！！
思路
设 0 表示硬币朝上，1 表示硬币朝下，则第 \(0\) 次与第 \(n\) 操作一定输出 \(1\)。因为没有可以操作的对象，前者是由于全部硬币朝上，后者是由于全部硬币朝下，即使没有操作也要遍历一遍。注意这里输出有 \(n + 1\) 个数。
以样例 \(2\) 为例子，最开始的序列是这样的：
00000000
第一次修改第 \(6\) 枚硬币，序列变为：
00000100
此时按照题目中的操作，第一次修改最后序列变为：
00000001
可以想到一共遍历了 \(2\) 次序列。
第二次操作修改第 \(8\) 枚硬币：
00000101
操作后：
00000011
明显这里只遍历了一次，但输出却是 \(2\)，因为修改完后再遍历了一遍，所以输出是 \(1 + 1 = 2\)。
第三次操作修改第三枚硬币：
00100101
操作：
00000111
输出 \(3\)。
第四次修改第四枚硬币：
00110101
这里给出详细操作：
00110101
\(→\) 00101011
\(→\) 00010111
\(→\) 00001111
输出为 \(3 + 1 = 4\)。
通过第三，四次操作可以发现，对于没有被硬币阻挡的硬币，第一次遍历就可以一换到底。而部分硬币由于后面的硬币的阻挡，并没有一换到底，最终的操作次数也因为这些硬币而增加。
因此可以的出结论：最终操作数就是当前处于反面状态的总硬币数 \(i\)，减去处于末尾的连续的反面状态的硬币数 \(j\)，最后要再检查一遍，故输出为 \(i-j+1\)。
代码
内涵部分注释，可以更好地理解题解。
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define inf 0x3f3f3f3f
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
#pragma comment(linker , "/stack : 200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
inline char gchar()
{
static char buf[1000000] , *p1 = buf , *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1000000 , stdin) , p1 == p2) ? EOF : *p1++;
}
inline ll read()
{
ll x = 0 , f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
ll n , ex , coin[300005];
ll ans;
ll r;
signed main()
{
r = n = read();
printf("1 ");//单独处理第0次
n--;
while(n >= 1)
{
ans++;
ex = read();
coin[ex] = 1;
//对r进行优化，不需要每次都从最后一枚硬币开始
while(coin[r--] != 0)
{
ans--;
}
r++;//在遍历时r多减了1，加回来
printf("%lld " , ans + 1);
n--;
}
printf("1");//单独处理第n次
system("pause");
return 0;
}
/*
0朝上
1朝下
*/