@TaoSama
2016-04-20T02:33:25.000000Z
字数 1535
阅读 1606
每周一题
int l = 1, r = n;
while(l <= r){ //[ ]
int m = l + r >> 1;
if(x > a[m]) l = m + 1;
else r = m -1;
}
//upper_bound > , -1
int binarySearch(int l, int r){
int L = l;
while(l <= r){
int m = l + r >> 1;
int zero = prefixSum[m]-prefixSum[L-1]; //[L,m]
if(zero <= k) l = m + 1;
else r = m - 1;
}
retrun l - 1;
}
//<
pair<int, int> ans = make_pair(-INF, -INF); //长度,左端点
for(int l = 1; l <= n; ++l){
int r = binarySearch(l, n);
ans = max(ans, make_pair(r - l + 1, l));
}
//correct some mistakes
for(int i = ans.second; ans.first--; ++i) a[i] = 1;
for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
int zero = 0;
pair<int, int> ans = make_pair(-INF, -INF); //长度,左端点
// [l, r)
for(int l = 1, r = 1; l <= n; ++l){
while(r <= n && zero + (a[r] == 0) <= k) zero += a[r++] == 0;
ans = max(ans, make_pair(r - l, l));
zero -= a[l] == 0;
}
//correct some mistakes
for(int i = ans.second; ans.first--; ++i) a[i] = 1;
for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
multiset<int> s; //erase(val), (iterator)
int ans = 0;
for(int l = 1, r = 1; l <= n; ++l){
while(r <= n){
if(!s.size()){ //空的
s.insert(a[r++]);
}
else{
//最大值 最小值
if(a[r] - *s.begin() > k || *s.rbegin() - a[r] > k) break;
s.insert(a[r++]);
}
ans += r - l;
if(ans >= MOD) ans -= MOD;
s.erase(s.find(a[l]));
}
}