算法：思维，前缀最大值
模拟一下他的运行过程就会发现，两次之后整个数组就固定了，之后每次都是每个数往后移动一位，可以模拟两次之后计算每个数的存活轮数，计算贡献。

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 2e5+100;
int n;
int a[N];
map < int , int > M;
int Max[N];void Work(){cin>>n;int sum = 0;for (int i = 1; i <= n; i++) cin>>a[i],sum+=a[i];int maxx = 0;M.clear();for (int i = 1; i <= n; i++){M[a[i]]++;if (M[a[i]] > 1) maxx = max(maxx,a[i]);Max[i] = maxx;sum+=maxx;}M.clear();maxx = 0;M.clear();for (int i = 1; i <= n; i++){M[Max[i]]++;if (M[Max[i]] > 1) maxx = max(maxx,Max[i]);sum+=maxx*(n-i+1);}cout<<sum<<endl;for (int i = 1; i <= n+1; i++) Max[i] = 0;return;
}signed main(){int t; cin>>t;while (t--) Work();return 0;
}

算法：贪心
贪心很多时候就是靠一个直觉
其实2*2的收益很多时候是不如直接染一行的。
不难发现，只要一行黑色的格子数大于4，肯定就是直接用操作2更优（一旦黑色格子数大于4，就意味着你想消掉这一行至少要用两次，那收益肯定不如操作2。而且2 * 2的格子范围最多涉及两行，就算这两次操作让下一行也消失，收益也就等同于操作2.）
上述可以说明，只有当格子里的格子数量小于等于4的时候，我们才会考虑操作1.
什么时候我们可以直接上手用操作1？
只有当当前操作1可以直接消掉这一整行的时候，直接用操作1显然更优。
因为这个时候操作1不仅可以消除这一行，还可以惠及下一行，至少不会更劣。
发现这个规律以后，我们又发现，操作1所涉及到的格子只有两种情况，1,2格和3,4格。
每一行按照这两种情况讨论即可。

#include<bits/stdc++.h>
using namespace std;const int N = 2e5+100;
int a[N];
int n;int l[N],r[N];int Work(){cin>>n;int s = 0;for (int i = 1; i <= n; i++) cin>>a[i],s+=a[i];int sum = 0;int la = 0;for (int i = 1; i <= n; i++){if (a[i] == 0){la = 0; continue;}if (la == 0){if (a[i] > 2) {sum++; la = 0; continue;}sum++; la = 1; continue;}if (la == 1){if (a[i] > 4){sum++; la = 0; continue;}if (a[i] <= 2){la = 0; continue;}sum++; la = 2; continue;}if (la == 2){if (a[i] > 4){sum++; la = 0; continue;}sum++; la = 1; continue;}}return sum;
}int main(){int t; cin>>t;while (t--) cout<<Work()<<endl;return 0;
}
/*
100
4
2 2 2 2
*/