https://www.luogu.com.cn/problem/P8868
我学会了历史和！
在一阵扫描线过后，你会发现，\([l,r]\) 的所有子区间的答案，就一定是扫到 \(i\) 的时候，加上 \([k,i]\) 的答案，\(k\le i,i\in[l,r]\)，然后又因为只有当 \(i\ge l\) 的时候，才能对左端点在 \([l,r]\) 的答案贡献，因此，你会发现这个东西就是一个扫过去，然后区间加法，然后查询区间历史和的问题。
即对于 \([l,r]\)，我们需要知道 \([l',r']\subset[l,r]\) 的答案，那么我们可以扫描线，扫到 \(i\) 的时候，用序列的第 \(j\) 位表示 \([j,i]\) 的答案。因为 \(i\) 只会更新 \(j\le i\)，因此当扫到 \(i<l\) 的时候，对答案无影响。当 \(i\ge l\) 的时候，会更新左端点的答案，此时若左端点在范围内，显然是要贡献给答案的，注意到，左端点的限制是仅跟查询的区间有关的，而对于一个询问 \([l,r]\) 我们可以把它挂在 \(r\) 上，那么需要往后一位扫，更新，贡献，往后一位扫，更新，贡献……这样的一个过程，对于贡献抽离出来，发现就是历史和问题。
总结一下，对于抽象到二维平面问题的矩形和，我们可以利用扫描线，然后维护更新操作，那么答案一定某些左端点的历史答案的和，这些左端点仅跟询问的区间有关
具体一下就是 \([l,r]\) 的子区间有啥呢？
\([l,l]\)
\([l,l+1],[l+1,l+1]\)
\([l,l+2],[l+1,l+2],[l+2,l+2]\)
...
\([l,r],[l+1,r],[l+2,r]...[r-1,r],[r,r]\)
如果说扫到某个位置，比如 \(l+2\)，那么比如说 \([l,l+2]\) 的答案是贡献到 \(l\) 上的。
那么对于 \([l,l],[l,l+1],[l,l+2],...,[l,r]\) 这些，你会发现就是扫到 \(r\) 后 \(l\) 的历史和。
嗯！
然后历史和，就是在每次更新后，将当前的答案，贡献给历史和，你就把矩阵乘法的形式写一写，然后嗯算哪些位置可能非零，然后抽离出来大力算。
然后在维护的时候不要想一步到位，抽离出来每一个步骤比较好做。比如你要时刻维护历史和，那你可以看成更新完，然后再来一个维护历史和的操作，而不是在更新的过程中就顺带维护了历史和。
更新后必须的更新历史和。
\([Ans,val,S_a,S_b,len]\to[Ans+val,val,S_a,S_b,len]\)
更新 \(A\)。
\([Ans,val,S_a,S_b,len]\to[Ans,v\cdot S_b,v\cdot len,S_b,len]\)
更新 \(B\) 同理。
#include <bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define ls ((cur)<<1)
#define rs ((ls)|1)
#define pb push_back
using namespace std;
const int N=(int)(2.5e5+5);
vector<pair<int,int> >vec[N];
ull ans[N];
int La[N],Lb[N],tp,st[N],n,q,a[N],b[N];
struct Matt {
ull a[5];
Matt() {
memset(a,0,sizeof(a));
}
void clr() {
memset(a,0,sizeof(a));
}
}val[N<<2];
struct Mat {
ull a[14];
Mat() {
memset(a,0,sizeof(a));
}
void clr() {
memset(a,0,sizeof(a));
}
void clr1() {
clr();
a[0]=a[2]=a[5]=a[8]=a[13]=1;
}
}tag[N<<2],P;
Matt Mul(const Matt &f,const Mat &g) {
Matt res;
res.a[0]=1llu*f.a[0]*g.a[0]+1llu*f.a[1]*g.a[1]+1llu*f.a[2]*g.a[3]+1llu*f.a[3]*g.a[6]+1llu*f.a[4]*g.a[9];
res.a[1]=1llu*f.a[1]*g.a[2]+1llu*f.a[2]*g.a[4]+1llu*f.a[3]*g.a[7]+1llu*f.a[4]*g.a[10];
res.a[2]=1llu*f.a[2]*g.a[5]+1llu*f.a[4]*g.a[11];
res.a[3]=1llu*f.a[3]*g.a[8]+1llu*f.a[4]*g.a[12];
res.a[4]=1llu*f.a[4]*g.a[13];
return res;
}
Mat mul(const Mat &f,const Mat &g) {
Mat res;
res.a[0]=1llu*f.a[0]*g.a[0];
res.a[1]=1llu*f.a[1]*g.a[0]+1llu*f.a[2]*g.a[1];
res.a[2]=1llu*f.a[2]*g.a[2];
res.a[3]=1llu*f.a[3]*g.a[0]+1llu*f.a[4]*g.a[1]+1llu*f.a[5]*g.a[3];
res.a[4]=1llu*f.a[4]*g.a[2]+1llu*f.a[5]*g.a[4];
res.a[5]=1llu*f.a[5]*g.a[5];
res.a[6]=1llu*f.a[6]*g.a[0]+1llu*f.a[7]*g.a[1]+1llu*f.a[8]*g.a[6];
res.a[7]=1llu*f.a[7]*g.a[2]+1llu*f.a[8]*g.a[7];
res.a[8]=1llu*f.a[8]*g.a[8];
res.a[9]=1llu*f.a[9]*g.a[0]+1llu*f.a[10]*g.a[1]+1llu*f.a[11]*g.a[3]+1llu*f.a[12]*g.a[6]+1llu*f.a[13]*g.a[9];
res.a[10]=1llu*f.a[10]*g.a[2]+1llu*f.a[11]*g.a[4]+1llu*f.a[12]*g.a[7]+1llu*f.a[13]*g.a[10];
res.a[11]=1llu*f.a[11]*g.a[5]+1llu*f.a[13]*g.a[11];
res.a[12]=1llu*f.a[12]*g.a[8]+1llu*f.a[13]*g.a[12];
res.a[13]=1llu*f.a[13]*g.a[13];
return res;
}
void push_up(int cur) {
val[cur].a[0]=val[ls].a[0]+val[rs].a[0];
val[cur].a[1]=val[ls].a[1]+val[rs].a[1];
val[cur].a[2]=val[ls].a[2]+val[rs].a[2];
val[cur].a[3]=val[ls].a[3]+val[rs].a[3];
val[cur].a[4]=val[ls].a[4]+val[rs].a[4];
}
void build(int cur,int l,int r) {
val[cur].clr(); tag[cur].clr1();
val[cur].a[4]=r-l+1;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
push_up(cur);
}
void push_down(int cur) {
tag[ls]=mul(tag[ls],tag[cur]);
tag[rs]=mul(tag[rs],tag[cur]);
val[ls]=Mul(val[ls],tag[cur]);
val[rs]=Mul(val[rs],tag[cur]);
tag[cur].clr1();
}
void upt(int cur,int l,int r,int cl,int cr) {
if(cl<=l&&r<=cr) {
val[cur]=Mul(val[cur],P);
tag[cur]=mul(tag[cur],P);
return ;
}
int mid=(l+r)>>1;
push_down(cur);
if(cl<=mid) upt(ls,l,mid,cl,cr);
if(cr>mid) upt(rs,mid+1,r,cl,cr);
push_up(cur);
}
ull qry(int cur,int l,int r,int cl,int cr) {
if(cl<=l&&r<=cr) {
return val[cur].a[0];
}
int mid=(l+r)>>1;
push_down(cur);
if(cr<=mid) return qry(ls,l,mid,cl,cr);
if(cl>mid) return qry(rs,mid+1,r,cl,cr);
return qry(ls,l,mid,cl,cr)+qry(rs,mid+1,r,cl,cr);
}
signed main() {
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
cin.tie(0); ios::sync_with_stdio(false);
cin>>n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) {
while(tp&&a[st[tp]]<a[i]) {
--tp;
}
if(tp) La[i]=st[tp];
st[++tp]=i;
}
tp=0;
for(int i=1;i<=n;i++) {
while(tp&&b[st[tp]]<b[i]) {
--tp;
}
if(tp) Lb[i]=st[tp];
st[++tp]=i;
}
cin>>q;
for(int i=1;i<=q;i++) {
int l,r; cin>>l>>r;
vec[r].pb(make_pair(l,i));
}
build(1,1,n);
for(int i=1;i<=n;i++) {
P.clr();
P.a[0]=1; P.a[7]=a[i]; P.a[8]=1; P.a[11]=a[i]; P.a[13]=1;
upt(1,1,n,La[i]+1,i);
P.clr();
P.a[0]=1; P.a[4]=b[i]; P.a[5]=1; P.a[12]=b[i]; P.a[13]=1;
upt(1,1,n,Lb[i]+1,i);
P.clr1(); P.a[1]=1;
upt(1,1,n,1,i);
for(auto x:vec[i]) ans[x.second]+=qry(1,1,n,x.first,i);
}
for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
return 0;
}