题解：P11845 [USACO25FEB] Min Max Subarrays P
furina__
·
·
题解
首先看到这种比较复杂的比大小的问题，尝试套路的扫描一个值域然后将序列转为 01 序列。
$Ans=\sum_{v\ge 1}g(v)$，$g(v)$ 表示答案大于等于 $v$ 的区间个数。
将 $a_i\ge v$ 的看作 $1$，其他看作 $0$，$g(v)$ 即是这个 $01$ 序列的所有子区间中操作完得到 $1$ 的子区间按个数。
现在问题就可做多了，考虑刻画什么样的序列最终可以得到 $1$。
首先你要得到 $1$，那么你的序列肯定不能是全 $0$，这是第一个条件。
我们先将极长同色段给划分出来，这样会比较好分析。
考虑操作取 $\min$ 操作的时候我们肯定尽量去给相邻两个 $0$ 取 $\min$，可以使一段长度大于等于 $2$ 的 $0$ 段的长度减一，同时下一次的取 $\max$ 操作我们肯定尽量不操作相邻两个 $1$，这样也可以使一段 $0$ 段的长度减一。
通过上面的分析，我们发现 $1$ 似乎比较难被删除，那可以合理猜测 $1$ 的个数比较多的时候是不是一定就可以得到 $1$，首先只有一个 $1$ 显然不够多（反例：$01$），两个也不够（反例：$0110$），那么三个呢，好像够了，通过一些简单分讨可以证明的确够。
考虑证明，首先对于所有 $0$ 段，我们可以通过上面分析的操作在一回合内（一次取 $\min$ 一次取 $\max$）将一段的长度减二，所以我们就只用讨论 $-1-1-1-$ 的情况，$-$ 表示可以存在单个 $0$ 或者一个都不存在，其中很多情况都是重复或者显然的（手玩之前最好先证明 $101,01010,110$ 都是合法的，后续很多分讨都可以将序列中某一段奇数长度的区间直接看作 $0$ 后套用这几个小结论），手玩一下可以发现都可以合并出 $1$。
剩下的情况就只有 $1$ 的个数为 $1$ 或 $2$ 了，先来看个数为 $1$，分讨这个 $1$ 左右两侧 $0$ 的奇偶性，可以发现只有在奇偶性不同时，即区间长度为偶数，或者区间为 $010$ 的时候非法。
再来看个数为 $2$，同样分讨左中右的 $0$ 的个数的奇偶性，虽然看起来有 $8$ 中情况，但是其中有重复的还有非常显然的，所以~~分讨并不复杂~~，分讨完后可以发现只有一下序列非法：$1010,001010,0110,010010,0101,010100$。
总结一下非法的序列为：$010,1010,001010,0110,010010,0101,010100$，以及只有一个 $1$ 且长度为偶数的序列，还有不存在一的区间。
从小到达扫描 $v$，每次将一个位置的 $1$ 改为 $0$，前面那七种非法的区间个数都可以直接 $\mathcal{O}(1)$ 计算变化量，后面这个非法的区间直接在每个 $1$ 那里记录上一个以及下一 $1$ 的位置，也可以 $\mathcal{O}(1)$ 计算变化量，最后维护一下 $0$ 段，将不存在一的区间减掉即可。
时间复杂度 $\mathcal{O}(n)$。
```cpp
#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
typedef long long ll;
using namespace std;
bool ST; namespace fast_IO {
#define IOSIZE 100000
static unsigned int precision = 6, POW[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; // 鍚戜笅鍙栨暣鍒板皬鏁扮偣鍚庣 precision 浣?
static char obuf[IOSIZE], *p3 = obuf;
#ifdef ONLINE_JUDGE
static char ibuf[IOSIZE], *p1 = ibuf, *p2 = ibuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#endif
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
inline int64_t read() { int64_t s = 0; int w = 1; char ch; while (ch = getchar(), !(ch>47 and ch<58) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while ((ch>47 and ch<58)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> static inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !(ch>47 and ch<58) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while ((ch>47 and ch<58)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> static inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
static inline bool read(char &s) { while (s = getchar(), isspace(s) and s != EOF); return s != EOF; }
static inline void print(char x) { putchar(x); }
static inline bool read(char *s) { char ch; while (ch = getchar(), (ch<33) && ch != EOF); if (ch == EOF) return false; while (!(ch<33) and (ch != EOF)) *s++ = ch, ch = getchar(); *s = '\0'; return true; }
static inline void print(char *x) { while (*x) putchar(*x++); }
static inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
static inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), (ch<33) and ch != EOF); if (ch == EOF) return false; while (!(ch<33)) s += ch, ch = getchar(); return true; }
static inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
static inline bool read(bool &b) { char ch; while(ch=getchar(), (ch<33) and ch != EOF); return ch == EOF ?false :(b=ch^48, true); }
static inline void print(bool b) { putchar(b+48); }
static inline bool read(double &x) { char ch = getchar(); int f = 1; for(; (ch<48 or 57<ch) and (ch != EOF); ch=getchar()) if(ch == '-') f = -1; if(ch == EOF) return false; for(x=0; 47<ch and ch<58; ch=getchar()) x = x*10 + (ch^48); if(ch != '.') return x *= f, true; double y = 0.1; for(ch=getchar(); 47<ch and ch<58; ch=getchar()) x += y*(ch^48), y /= 10; return x *= f, true; }
static inline void print(double x) { if(x < 0) putchar('-'), x = -x; if(!precision) print((unsigned long long)(x-(unsigned long long)(x)>=0.5 ?x+1 :x)); else { unsigned long long xx = x; double y = ((x-xx)*POW[precision]); unsigned long long yy = (y-(unsigned long long)(y)>=0.5 ?y+1 :y); if(yy == POW[precision]) xx++, yy = 0; print(xx), putchar('.'); for(int j=precision-1; ~j; j--) putchar(48+yy/POW[j]%10); } }
template<typename T, typename... T1> static inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> static inline void print(T a, T1... other) { print(a), print(other...); }
static struct Fast_IO {
bool flag = 1;
inline ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); }
// inline void SetPrecision(int x) { if(x > 9) throw runtime_error("Precision too high!"); else if(x < 0) throw runtime_error("Precision too low!"); else precision = x; } // 娴偣鏁扮簿搴﹁涓?x锛屽嵆绮剧‘鍒板皬鏁扮偣鍚?x 浣嶃€?
inline operator bool() { return flag; }
} io;
Fast_IO& operator >> (Fast_IO &io, char *b) { return io.flag &= read(b), io; }
template<typename T> static Fast_IO& operator >> (Fast_IO &io, T &b) { return io.flag &= read(b), io; }
template<typename T> static Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
namespace furina{
const int N = 1e6, inf = 0x7fffffff >> 1;
int n;
int a[N + 10], b[N + 10], c[N + 10];
vector<int> vt[N + 10];
struct segment{
int l, r;
} s[N + 10];
int bl[N + 10];
int lst[N + 10], nxt[N + 10];
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i], vt[a[i]].push_back(i);
ll ans = 0, res = -1, sum1 = 0, sum2 = 0, sum3 = 0;
for(int i = 0; i <= n + 1; i++)
b[i] = 1, s[bl[i] = i] = {-1, -1}, lst[i] = i - 1, nxt[i] = i + 1;
auto update = [&](const int &l, const int &type) -> void {
if(l < 1)
return;
if(l + 2 <= n && b[l] == 0 && b[l + 1] == 1 && b[l + 2] == 0)
sum2 += type;
if(l + 3 <= n && b[l] == 0 && b[l + 1] == 1 && b[l + 2] == 0 && b[l + 3] == 1)
sum2 += type;
if(l + 3 <= n && b[l] == 1 && b[l + 1] == 0 && b[l + 2] == 1 && b[l + 3] == 0)
sum2 += type;
if(l + 3 <= n && b[l] == 0 && b[l + 1] == 1 && b[l + 2] == 1 && b[l + 3] == 0)
sum2 += type;
if(l + 5 <= n && b[l] == 0 && b[l + 1] == 1 && b[l + 2] == 0 && b[l + 3] == 1 && b[l + 4] == 0 && b[l + 5] == 0)
sum2 += type;
if(l + 5 <= n && b[l] == 0 && b[l + 1] == 0 && b[l + 2] == 1 && b[l + 3] == 0 && b[l + 4] == 1 && b[l + 5] == 0)
sum2 += type;
if(l + 5 <= n && b[l] == 0 && b[l + 1] == 1 && b[l + 2] == 0 && b[l + 3] == 0 && b[l + 4] == 1 && b[l + 5] == 0)
sum2 += type;
};
auto get0 = [&](const int &x) -> int {
return (x >> 1) + 1;
};
auto get1 = [&](const int &x) -> int {
return (x + 1) >> 1;
};
auto calc = [&](const int &x) -> ll {
if(x < 1 || x > n)
return 0;
ll res = 0;
int L = x - lst[x] - 1, R = nxt[x] - x - 1;
//0<=l<=L,0<=r<=R,(l+r)&1=1
res += 1ll * get0(L) * get1(R) + 1ll * get1(L) * get0(R);
return res;
};
for(int i = 1; i <= n; i++){
if(res != -1){
ans += res;
continue;
}
res = 1ll * n * (n + 1) / 2 - sum1 - sum2 - sum3;
ans += res;
for(int j : vt[i]){//赋值为0
for(int k = 0; k < 6; k++)
update(j - k, -1);
b[j] = 0;
for(int k = 0; k < 6; k++)
update(j - k, 1);
sum3 -= calc(j) + calc(lst[j]) + calc(nxt[j]);
nxt[lst[j]] = nxt[j], lst[nxt[j]] = lst[j];
sum3 += calc(lst[j]) + calc(nxt[j]);
if(b[j - 1] && b[j + 1])
s[bl[j]] = {j, j}, sum1++;
else if(!b[j - 1] && !b[j + 1]){
int L = s[bl[j - 1]].l, R = s[bl[j + 1]].r;
s[bl[L] = bl[R] = bl[j]] = {L, R};
sum1 += 1ll * (j - L + 1) * (R - j + 1);
}
else if(!b[j - 1]){
int L = s[bl[j - 1]].l, R = j;
s[bl[L] = bl[R] = bl[j]] = {L, R};
sum1 += R - L + 1;
}
else if(!b[j + 1]){
int L = j, R = s[bl[j + 1]].r;
s[bl[L] = bl[R] = bl[j]] = {L, R};
sum1 += R - L + 1;
}
}
res = -1;
}
cout << ans << '\n';
return 0;
}
} bool ED;
signed main(){
furina::main();
cerr << 1000. * clock() / CLOCKS_PER_SEC << "ms" << '\n';
cerr << (abs(&ST - &ED) >> 20) << "mb" << '\n';
return 0;
}
/*
g++ -o furina furina.cpp -std=c++14 -Wall -O2 -lm -Wl,--stack=2000000000 & furina
*/
```