题目

题目描述

有这样一道猫树的板题：

给出长度为 nnn 的序列 aaa，定义 cost(l,r)=(max⁡i=lrai)⋅(min⁡i=lrai)cost(l,r)=(\max_{i=l}^{r}a_i)\cdot(\min_{i=l}^ra_i)cost(l,r)=(maxi=lr​ai​)⋅(mini=lr​ai​)，多次询问，回答 ∑l=LR∑r=lRcost(l,r)mod(109+7)\sum_{l=L}^{R}\sum_{r=l}^{R}cost(l,r)\bmod(10^9+7)∑l=LR​∑r=lR​cost(l,r)mod(109+7) 的结果。

但是 FireWingBird\sf FireWingBirdFireWingBird 非常气愤！这是种族之间的深仇大恨。

所以它决定出数据卡掉猫树的 O(nlog⁡2n)\mathcal O(n\log^2n)O(nlog2n) 做法。

但是 std\rm stdstd 还是要给的啊。你能不能帮助 FireWingBird\sf FireWingBirdFireWingBird 写一个标算呢？

数据范围与提示

n⩽105n\leqslant 10^5n⩽105，序列的元素满足 1⩽ai⩽1091\leqslant a_i\leqslant 10^91⩽ai​⩽109 。

思路

就只说一点：区间乘和区间 “赋值” 到底谁简单？这可说不好。

用一个线段树，维护 rrr 为某个值时的 cost(l,r)cost(l,r)cost(l,r) 。两个单调栈，分别维护 min⁡\minmin 和 max⁡\maxmax 。这里一定要选用区间乘，因为单独对 min⁡\minmin 或者 max⁡\maxmax 赋值，都很糟糕。而先乘 invinvinv 再乘当前值，就简单的一批。

区间乘之后，我们要将权值下放到 lll 上（历史值求和）。跟此题较为近似，需要打一个标记，表示 “将当前值累加一次”。显然它和前面的区间乘标记需要一同维护，就写一个结构体就行了。

复杂度 O(nlog⁡nA+qlog⁡nq)\mathcal O(n\log nA+q\log nq)O(nlognA+qlognq) 。

代码

#include <cstdio>#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;typedef long long int_;# define rep(i,a,b) for(int i=(a); i<=(b); ++i)# define drep(i,a,b) for(int i=(a); i>=(b); --i)inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;}inline void writeint(int x){if(x > 9) writeint(x/10);putchar((x-x/10*10)^48);}const int Mod = 1e9+7;inline int qkpow(int_ b,int q){int a = 1;for(; q; q>>=1,b=b*b%Mod)if(q&1) a = a*b%Mod;return a;}struct Tag{// v' = kv * v, his += khis * vint kv, khis;Tag():kv(1),khis(0){}Tag(int A,int B){kv = A, khis = B;}/// @brief command *this and then @p tTag operator * (const Tag &t) const {return Tag(int_(kv)*t.kv%Mod,(int_(kv)*t.khis+khis)%Mod);}Tag& operator *= (const Tag &t){return *this = (*this)*t;}Tag operator + (const Tag &t) const {return Tag((kv+t.kv)%Mod,(khis+t.khis)%Mod);}};const int MaxN = 100005;int n; // length of segment treenamespace SgTree{Tag val[MaxN<<2], lazy[MaxN<<2];void fuck(int o,const Tag &qv){val[o] *= qv, lazy[o] *= qv;}void pushDown(int o){rep(d,0,1) fuck(o<<1|d,lazy[o]);lazy[o] = Tag(1,0); // useless}void pushUp(int o){val[o] = val[o<<1]+val[o<<1|1];}# define __ROOT int o=1,int l=1,int r=n# define LSON o<<1,l,(l+r)>>1# define RSON o<<1|1,((l+r)>>1)+1,rvoid build(__ROOT){val[o] = lazy[o] = Tag(1,0);if(l != r) build(LSON), build(RSON);}void modify(int ql,int qr,const Tag &tag,__ROOT){if(qr < l || r < ql) return ;if(ql <= l && r <= qr) return fuck(o,tag);pushDown(o); modify(ql,qr,tag,LSON);modify(ql,qr,tag,RSON), pushUp(o);}int query(int ql,int qr,__ROOT){if(qr < l || r < ql) return 0;if(ql <= l && r <= qr)return val[o].khis;pushDown(o);int res = query(ql,qr,LSON);res += query(ql,qr,RSON);if(res >= Mod) res -= Mod;return res;}}struct Query{int l, r, id;bool operator < (const Query &t) const {return r < t.r;}};Query ask[MaxN];int mx[MaxN], mn[MaxN], a[MaxN];int top_mx, top_mn, xyx[MaxN];int main(){n = readint(); int q = readint();SgTree::build(); // neededrep(i,1,n) a[i] = readint();rep(i,1,q){ask[i].l = readint();ask[i].r = readint();ask[i].id = i;}sort(ask+1,ask+q+1);for(int i=1,qid=1; i<=n; ++i){while(top_mx && a[mx[top_mx]] < a[i]){int inv = qkpow(a[mx[top_mx]],Mod-2); -- top_mx;SgTree::modify(mx[top_mx]+1,mx[top_mx+1],Tag(inv,0));}SgTree::modify(mx[top_mx]+1,i,Tag(a[i],0));while(top_mn && a[mn[top_mn]] > a[i]){int inv = qkpow(a[mn[top_mn]],Mod-2); -- top_mn;SgTree::modify(mn[top_mn]+1,mn[top_mn+1],Tag(inv,0));}SgTree::modify(mn[top_mn]+1,i,Tag(a[i],0));mx[++ top_mx] = mn[++ top_mn] = i;SgTree::modify(1,i,Tag(1,1)); // accumulate tagfor(; qid<=q&&ask[qid].r==i; ++qid)xyx[ask[qid].id] = SgTree::query(ask[qid].l,i);}rep(i,1,q) writeint(xyx[i]), putchar('\n');return 0;}