题解 U146773 【数据结构一】
疑似整体二分，思路上有很大的启发性，值得写一篇题解。
我愿称之为 “整体分治”。
似乎这东西其实就是线段树分治？
实则在顶风作案
原题链接
【题意简述】
给定一个序列，每一次询问一个区间，求这个区间 所有子区间的最大值与最小值之积 之和。
【思路】
碰到这一类题，一种可行的套思路是单调栈，我们这里不考虑这一种套路。
考虑分治。
首先我们对于每一个询问，一种很 naive 的分治套路是把询问分成左右两半，然后拆成“左边一半的贡献+右边一半的贡献+左右之间的贡献”这三部分，下文称这个把序列分成的位置为 “分治断点”，显然这个点可以任意取（这一点很重要）。
这么搞显然是不行的，复杂度会爆炸。
于是我们利用类似整体二分的方法，来一个整体分治。
我们用一个类似于线段树的结构，每一个结点表示一个区间，储存所有 被这个区间完全包含 的询问，显然应该首先在根结点上储存所有询问。
然后我们钦定这个区间的
那么剩下的所有点都必然经过这个
首先不难发现，对于一个区间
于是，现在我们要处理的是一堆横跨了
显然
故我们要遍历
我们现在考虑某 一个 确定的右端点
不难发现，此时对于一个左端点
（为方便理解，下文中记区间
-
- 仅
\min[l',r'] 出现在[l',mid] 中。 - 仅
\max[l',r'] 出现在[l',mid] 中。 -
于是我们对于
同时我们记录
然后我们发现这四部分分别满足的条件是：
-
Mn[l']<Min,Mx[l']>Max -
Mn[l']<Min,Mx[l']\le Max -
Mn[l']\ge Min,Mx[l']>Max -
Mn[l']\ge Min,Mx[l']\le Max
由于我们不难发现
故每一部分的区间是连续的，可以一起求。
并且显然，这个东西的分布从左到右长这样：
[1][2/3][4]其中
于是我们考虑记录
由于
于是我们就确定了每一类数的出现区间。
那么接下来考虑每一类数的贡献。
不难发现每一类数产生的贡献为：
-
Mn[l']\times Mx[l'] -
Mn[l']\times Max -
Min\times Mx[l'] -
Min\times Max
不难发现每一段区间的贡献都可以表示为“一个不变的常数乘上一个变化的系数”的形式，故可以用线段树去维护，复杂度一次
查询贡献时，考虑一个询问的右端点是否与当前扫到的右端点重合，若重合，则当前区间
但我们如何保证询问数的总和复杂度正确呢？
考虑对于一个询问，若它的询问区间与所在的结点所表示的区间相同，那么显然可以直接返回而不下传。
这样我们就得到了一个类似线段树的结构，每一个询问都最多只会访问到
于是我们达到了总体复杂度
【代码】
#include <cstdio>
#include <vector>
#include <algorithm>
using std :: vector;
using std :: sort;
template <typename T>
inline void read(T &x){
x = 0;int fu = 1;
char c = getchar();
while(c > 57 || c < 48){
if(c == 45) fu = -1;
c = getchar();
}
while(c <= 57 && c >= 48){
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
x *= fu;
}
template <typename T>
inline void fprint(T x){
if(x < 0) putchar(45), x = -x;
if(x > 9) fprint(x / 10);
putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
fprint(x);putchar(ch);
}
template <typename T>
inline T mn(T x, T y) {return x < y ? x : y;}
template <typename T>
inline T mx(T x, T y) {return x > y ? x : y;}
template <typename T>
inline void chmin(T &x, T y) {(x > y) && (x = y);}
template <typename T>
inline void chmax(T &x, T y) {(x < y) && (x = y);}
#define MAXN 100005
struct Quest{
int l, r, id;
Quest (int l, int r, int id) : l(l), r(r), id(id) {}
inline bool operator < (const Quest &tmp) const{return r < tmp.r;}
};
typedef vector <Quest> vec;
int n, m;
int a[MAXN];
const int MOD = 1000000007;
#define LSON rt << 1, l, mid
#define RSON rt << 1 | 1, mid + 1, r
struct SegTree{
int t[MAXN << 2], tag[MAXN << 2], fac[MAXN << 2];
int base[MAXN];
inline void pushup(int rt){t[rt] = (t[rt << 1] + t[rt << 1 | 1]) % MOD;}
void build(int rt, int l, int r){
t[rt] = tag[rt] = 0;
if(l == r){
fac[rt] = base[l];
return ;
}
int mid = (l + r) >> 1;
build(LSON);build(RSON);
fac[rt] = (fac[rt << 1] + fac[rt << 1 | 1]) % MOD;
}
inline void update(int rt, int val){
t[rt] = (1ll * t[rt] + 1ll * fac[rt] * val) % MOD;
tag[rt] = (tag[rt] + val) % MOD;
}
inline void pushdown(int rt){
if(tag[rt]){
update(rt << 1, tag[rt]);
update(rt << 1 | 1, tag[rt]);
tag[rt] = 0;
}
}
void modify(int rt, int l, int r, int x, int y, int z){
if(x <= l && r <= y) return update(rt, z);
pushdown(rt);
int mid = (l + r) >> 1;
if(x <= mid) modify(LSON, x, y, z);
if(y > mid) modify(RSON, x, y, z);
pushup(rt);
}
int query(int rt, int l, int r, int x, int y){
if(x <= l && r <= y) return t[rt];
pushdown(rt);
int mid = (l + r) >> 1, ret = 0;
if(x <= mid) ret = query(LSON, x, y);
if(y > mid) ret = (ret + query(RSON, x, y)) % MOD;
return ret;
}
}st[4];
vec v[MAXN << 2];
int ans[MAXN], Mn[MAXN], Mx[MAXN];
int num[MAXN << 2];
#define V v[rt]
void solve(int rt, int l, int r){
int mid = (l + r) >> 1, sz = V.size();
if(l == r){
num[rt] = 1ll * a[l] * a[l] % MOD;
for (register int i = 0;i < sz;i ++) ans[V[i].id] = (ans[V[i].id] + num[rt]) % MOD;
return ;
}
int j = 0;
while(j < sz && V[j].r <= mid) ++ j;
Mn[mid] = Mx[mid] = a[mid];
for (register int i = mid - 1;i >= l;i --){
Mn[i] = mn(Mn[i + 1], a[i]);
Mx[i] = mx(Mx[i + 1], a[i]);
}
for (register int i = l;i <= mid;i ++){
st[0].base[i] = 1ll * Mn[i] * Mx[i] % MOD;st[3].base[i] = 1;
st[1].base[i] = Mn[i];st[2].base[i] = Mx[i];
}
for (register int i = 0;i < 4;i ++) st[i].build(1, l, mid);
int p1 = mid + 1, p2 = mid + 1, p3 = mid + 1;
int MX = a[mid + 1], MN = MX;
for (register int i = mid + 1;i <= r;i ++){
chmax(MX, a[i]);chmin(MN, a[i]);
while(p1 > l && MX > Mx[p1 - 1] && MN < Mn[p1 - 1]) -- p1;
while(p2 > l && MX > Mx[p2 - 1]) -- p2;
while(p3 > l && MN < Mn[p3 - 1]) -- p3;
if(p1 <= mid) st[3].modify(1, l, mid, p1, mid, 1ll * MX * MN % MOD);
if(p3 < p1) st[2].modify(1, l, mid, p3, p1 - 1, MN);
if(p2 < p1) st[1].modify(1, l, mid, p2, p1 - 1, MX);
if(mn(p2, p3) > l) st[0].modify(1, l, mid, l, mn(p2, p3) - 1, 1);
while(j < sz && V[j].r == i){
if(V[j].l > mid || (V[j].l == l && V[j].r == r)){++ j;continue;}
for (register int k = 0;k < 4;k ++) ans[V[j].id] = (ans[V[j].id] + st[k].query(1, l, mid, V[j].l, mid)) % MOD;
++ j;
}
}
for (register int i = 0;i < sz;i ++){
if(l == V[i].l && r == V[i].r) continue;
if(V[i].r <= mid) v[rt << 1].push_back(V[i]);
else if(V[i].l > mid) v[rt << 1 | 1].push_back(V[i]);
else{
v[rt << 1].push_back(Quest(V[i].l, mid, V[i].id));
v[rt << 1 | 1].push_back(Quest(mid + 1, V[i].r, V[i].id));
}
}
for (register int i = 0;i < 4;i ++) num[rt] = (num[rt] + st[i].query(1, l, mid, l, mid)) % MOD;
solve(LSON);solve(RSON);
num[rt] = (num[rt] + (num[rt << 1] + num[rt << 1 | 1]) % MOD) % MOD;
for (register int i = 0;i < sz;i ++)
if(l == V[i].l && r == V[i].r) ans[V[i].id] = (ans[V[i].id] + num[rt]) % MOD;
}
int main(){
read(n);read(m);
for (register int i = 1;i <= n;i ++) read(a[i]);
for (register int i = 1;i <= m;i ++){
int l, r;read(l);read(r);
v[1].push_back(Quest(l, r, i));
}
sort(v[1].begin(), v[1].end());
solve(1, 1, n);
for (register int i = 1;i <= m;i ++) fprint(ans[i], 10);
}