题意
给定排列 \(a,b\)，\(q\) 次询问 \(l,r\)，你需要求出 \(\sum_{l\le l'\le r'\le r}(\max_{i=l'}^{r'}a_i)(\max_{i=l'}^{r'}b_i)\) 对 \(2^{64}\) 取模的值。
\(n,q\le 2.5\times10^5\)
分析
根据经典套路，按 \(r\) 扫描线，维护两个单调栈，那么加入一个数就相当于进行若干段区间加。当扫到 \(r\) 的时候，每个点 \(l\) 存储的是以 \(l\) 为左端点，分别以 \(1\sim r\) 为右端点的权值之和，而最终的查询就相当于求 \([l,r]\) 的区间历史和是多少。
这个东西看上去就不是很好维护。我们考虑把转移写成矩阵形式，设向量 \(\begin{bmatrix}len\ \sum a\ \sum b\ \sum a\cdot b\end{bmatrix}\)，那么，对 \(a\) 进行区间加的转移矩阵就是 \(\begin{bmatrix}1&v&0&0&0\\0&1&0&0&0\\0&0&1&v&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}\)，对 \(b\) 进行区间加的转移矩阵就是 \(\begin{bmatrix}1&0&v&0&0\\0&1&0&v&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}\)，对全局将当前答案加到历史和的转移矩阵是 \(\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&1\\0&0&0&0&1\end{bmatrix}\)。暴力维护矩阵乘法的时间复杂度 \(O(5^3n\log n)\)，一脸过不去。
考虑到：
- 该矩阵是一个上三角矩阵，故我们不需要维护左下部分。
- 对角线上的元素恒为 1，故我们也不需要维护对角线。
- \((2,3)\) 上的元素恒为 0（\(\sum a\) 对 \(\sum b\) 肯定没贡献），故我们也不需要维护该位置的值。
- \((1,2),(3,4)\)、\((1,3),(2,4)\) 两个位置的元素恒等（考虑实际意义），故每对位置中维护其中一个即可。
- 这样我们只需要维护 \(25-15-1-2=7\) 个值，暴力展开矩阵乘法即可。向量乘矩阵是平凡的。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2.5e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int ID,n,Q;
int a[maxn],b[maxn];
int sta[2][maxn],tp[2];
vector<pii>q[maxn];
u64 ans[maxn];
namespace sgt{
struct info{
u64 len,asum,bsum,absum,hsum;
info(){len=asum=bsum=absum=hsum=0;}
};
struct Tag{
u64 wa,wb,ws,hl,ha,hb,hs;
Tag(){wa=wb=ws=hl=ha=hb=hs=0;}
inline Tag(u64 _a,u64 _b,u64 _c,u64 _d,u64 _e,u64 _f,u64 _g){
wa=_a,wb=_b,ws=_c,hl=_d,ha=_e,hb=_f,hs=_g;
}
inline bool empty(){
return !wa&&!wb&&!ws&&!hl&&!ha&&!hb&&!hs;
}
};
inline info operator+(info x,info y){
info res;
res.len=x.len+y.len;
res.asum=x.asum+y.asum;
res.bsum=x.bsum+y.bsum;
res.absum=x.absum+y.absum;
res.hsum=x.hsum+y.hsum;
return res;
}
inline Tag operator+(Tag x,Tag y){
Tag res;
res.wa=x.wa+y.wa;
res.wb=x.wb+y.wb;
res.ws=x.ws+y.ws+x.wa*y.wb+x.wb*y.wa;
res.hl=x.hl+y.hl+x.wa*y.ha+x.wb*y.hb+x.ws*y.hs;
res.ha=x.ha+y.ha+x.wb*y.hs;
res.hb=x.hb+y.hb+x.wa*y.hs;
res.hs=x.hs+y.hs;
return res;
}
inline info operator+(info x,Tag y){
info res;
res.len=x.len;
res.asum=x.asum+x.len*y.wa;
res.bsum=x.bsum+x.len*y.wb;
res.absum=x.absum+x.len*y.ws+x.asum*y.wb+x.bsum*y.wa;
res.hsum=x.hsum+x.len*y.hl+x.asum*y.ha+x.bsum*y.hb+x.absum*y.hs;
return res;
}
info d[maxn<<2];
Tag tag[maxn<<2];
inline void pu(int p){
d[p]=d[lson(p)]+d[rson(p)];
}
inline void pt(int p,Tag v){
d[p]=d[p]+v,tag[p]=tag[p]+v;
}
inline void pd(int p){
if(!tag[p].empty()){
pt(lson(p),tag[p]),pt(rson(p),tag[p]);
tag[p]=Tag();
}
}
#define mid ((l+r)>>1)
inline void bd(int l=1,int r=n,int p=1){
d[p].len=r-l+1;
if(l==r)return;
bd(l,mid,lson(p)),bd(mid+1,r,rson(p));
}
inline void upd(int ll,int rr,Tag v,int l=1,int r=n,int p=1){
if(ll<=l&&r<=rr)return pt(p,v);
pd(p);
if(ll<=mid)upd(ll,rr,v,l,mid,lson(p));
if(rr>mid)upd(ll,rr,v,mid+1,r,rson(p));
pu(p);
}
info qry(int ll,int rr,int l=1,int r=n,int p=1){
if(ll<=l&&r<=rr)return d[p];
info res;pd(p);
if(ll<=mid)res=res+qry(ll,rr,l,mid,lson(p));
if(rr>mid)res=res+qry(ll,rr,mid+1,r,rson(p));
return res;
}
#undef mid
}un sgt;
inline void solve_the_problem(){
ID=rd(),n=rd();
rep(i,1,n)a[i]=rd();
rep(i,1,n)b[i]=rd();
Q=rd();
rep(i,1,Q){
int l=rd(),r=rd();
q[r].pb(mp(l,i));
}
bd();
rep(i,1,n){
while(tp[0]&&a[i]>a[sta[0][tp[0]]]){
upd(sta[0][tp[0]-1]+1,sta[0][tp[0]],Tag(a[i]-a[sta[0][tp[0]]],0,0,0,0,0,0));
--tp[0];
}
upd(i,i,Tag(a[i],0,0,0,0,0,0)),sta[0][++tp[0]]=i;
while(tp[1]&&b[i]>b[sta[1][tp[1]]]){
upd(sta[1][tp[1]-1]+1,sta[1][tp[1]],Tag(0,b[i]-b[sta[1][tp[1]]],0,0,0,0,0));
--tp[1];
}
upd(i,i,Tag(0,b[i],0,0,0,0,0)),sta[1][++tp[1]]=i;
upd(1,i,Tag(0,0,0,0,0,0,1));
// write(qry(1,i).hsum,10);
for(pii qwq:q[i]){
int l=qwq.fi,id=qwq.se;
info res=qry(l,i);
// write(res.len,32),write(res.asum,32),write(res.bsum,32),write(res.absum,10);
ans[id]=res.hsum;
}
}
rep(i,1,Q)write(ans[i],10);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/