[CF997E] Good Subsegments
前言
我后悔了，要是拉这个加强版就不至于人均切 T4 了。
题目
洛谷
CF
讲解
CF526F Pudding Monsters 的加强版，没做过的建议先去做一下，至少要熟悉那道题的思路。
我们还是移动右端点，用单调栈+线段树维护一下 \(max-min+cnt\) 的值，思考一个好区间对之后的区间的贡献是什么？
其实就是1啦，只要后面的区间的左端点达到现在这个好区间的左端点，那么就会有贡献，所以我们考虑维护一个标记，将其放在好区间的左端点，一旦后面的区间包含这个左端点，那么就可以获得它的贡献。
那么我们应该怎么快速给这些好区间的左端点加上一个1的标记呢？它们的通性不就是全局最小值吗？所以我们只需要把所以是最小值的地方都加上这个标记即可。由于之前的单调栈+线段树的区间加操作不会影响一个顶点左右儿子最小值相对关系，所以只要儿子和当前节点的最小值相同，我们就可以放心大胆地下传这个标记。
时间复杂度 \(O(n\log_2n)\)。
代码
easy to understand
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 120005;
int n,m;
int a[MAXN];
LL ans[MAXN];
vector > q[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
#define lc (x<<1)
#define rc (x<<1|1)
int MIN[MAXN<<2],lz[MAXN<<2],cnt[MAXN<<2],tim[MAXN<<2];
LL val[MAXN<<2];
void calc(int x,LL v)
{
val[x] += v * cnt[x];
tim[x] += v;
}
void down(int x)
{
if(lz[x])
{
MIN[lc] += lz[x]; lz[lc] += lz[x];
MIN[rc] += lz[x]; lz[rc] += lz[x];
lz[x] = 0;
}
if(tim[x])//这两个if写反了，调了5分钟
{
if(MIN[x] == MIN[lc]) calc(lc,tim[x]);
if(MIN[x] == MIN[rc]) calc(rc,tim[x]);
tim[x] = 0;
}
}
void up(int x)
{
MIN[x] = Min(MIN[lc],MIN[rc]); cnt[x] = 0;
if(MIN[x] == MIN[lc]) cnt[x] += cnt[lc];
if(MIN[x] == MIN[rc]) cnt[x] += cnt[rc];
}
void Build(int x,int l,int r)
{
cnt[x] = r-l+1;
if(l == r) return;
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
}
void Add(int x,int l,int r,int ql,int qr,int v)
{
if(ql <= l && r <= qr)
{
MIN[x] += v;
lz[x] += v;
return;
}
int mid = (l+r) >> 1;
down(x);
if(ql <= mid) Add(lc,l,mid,ql,qr,v);
if(mid+1 <= qr) Add(rc,mid+1,r,ql,qr,v);
up(x);
}
LL Query(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) return val[x];
int mid = (l+r) >> 1;LL ret = 0;
down(x);
if(ql <= mid) ret += Query(lc,l,mid,ql,qr);
if(mid+1 <= qr) ret += Query(rc,mid+1,r,ql,qr);
return ret;
}
int s1[MAXN],tl1,s2[MAXN],tl2;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i) a[i] = Read();
m = Read();
for(int i = 1;i <= m;++ i)
{
int l = Read();
q[Read()].emplace_back(make_pair(l,i));
}
Build(1,1,n);
for(int i = 1;i <= n;++ i)
{
Add(1,1,n,1,i,-1);
while(tl1 && a[i] > a[s1[tl1]]) Add(1,1,n,s1[tl1-1]+1,s1[tl1],-a[s1[tl1]]),--tl1;
while(tl2 && a[i] < a[s2[tl2]]) Add(1,1,n,s2[tl2-1]+1,s2[tl2],a[s2[tl2]]),--tl2;
s1[++tl1] = s2[++tl2] = i;
Add(1,1,n,s1[tl1-1]+1,s1[tl1],a[s1[tl1]]);
Add(1,1,n,s2[tl2-1]+1,s2[tl2],-a[s2[tl2]]);
calc(1,1);
for(auto A : q[i]) ans[A.second] = Query(1,1,n,A.first,i);
}
for(int i = 1;i <= m;++ i) Put(ans[i],'\n');
return 0;
}