题目

https://gmoj.net/senior/#main/show/6854

题目大意

给你一个长度为 n n n的序列 s s s和 m m m个询问，每个询问会给出两个正整数 l , r ( 1 ≤ l ≤ r ≤ n ) l,r(1\le l\le r\le n) l,r(1≤l≤r≤n)，求 ∑ i = l r ∑ j = l r ( max ⁡ k = i j s k ) ⋅ ( min ⁡ k = i j s k ) \sum_{i=l}^r \sum_{j=l}^r \left(\max_{k=i}^j s_k\right) \cdot \left(\min_{k=i}^j s_k\right) i=l∑r​j=l∑r​(k=imaxj​sk​)⋅(k=iminj​sk​)

题解

看到这个套娃的询问就觉得很烦，但因为这是模拟赛中为数不多的数据结构题，让我想要一试。

解法1

这是我考场上的思路。

考虑枚举询问区间的右端点（即 r r r），那么以这个点的答案等于 r − 1 r-1 r−1的答案加上以 r r r为上式中的 j j j的答案。

由于现在固定了区间的右端点，因此很容易想到在左端点上放答案。每个左端点上的答案由它到右端点的 m a x , m i n max,min max,min决定，这个要在线维护，可以考虑用单调栈。那么现在还需要一个支持区间修改、区间查询的数据结构，那就用线段树吧！

可以发现每一次将所有区间都修改一下是不现实的，由于很多修改都是重复的，只要 m a x , m i n max,min max,min不变，修改量不变。因此打上时间戳就可以处理了。

但是这样做要在线段树上维护很多值，而且细节很多，就没有实现了（考场上也没有打出来）。

解法2

题解神奇分治算法。

将整个 [ 1 , n ] [1,n] [1,n]的区间分治一下，对于每个区间只维护跨过 m i d mid mid的区间 [ i , j ] [i,j] [i,j]对答案的贡献，其它的询问只要不是包含了整个区间都分治下去处理。

那么对于一个区间怎么处理呢？枚举右端点，根据 [ l , m i d ] [l,mid] [l,mid]中每个点与右端点之间的 m a x , m i n max,min max,min分别是在 [ l , m i d ] [l,mid] [l,mid]上还是在 [ m i d + 1 , r ] [mid+1,r] [mid+1,r]上将区间 [ l , m i d ] [l,mid] [l,mid]分成3份。具体来说是这样的：

当然，为了方便处理，实际上我把它分成了4份：

1. m a x , m i n max,min max,min值都在 [ l , m i d ] [l,mid] [l,mid]上；
2. 只有 m a x max max值在 [ l , m i d ] [l,mid] [l,mid]上；
3. 只有 m i n min min值在 [ l , m i d ] [l,mid] [l,mid]上；
4. m a x , m i n max,min max,min值都不在 [ l , m i d ] [l,mid] [l,mid]上；

这4段用4棵线段树分别处理它们的系数，比较方便。

这题还有一个难点：对询问的处理。
可以用类似线段树的方法处理：在每个节点上都挂一个存放询问的vector，这样便于下传询问；并且处理出整个区间的答案，这样包含整个区间 [ l , r ] [l,r] [l,r]的询问也就好处理了。

注意细节。

CODE

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson k<<1
#define rson k<<1|1
#define P 1000000007
#define M 500005
#define N 100005
int s[N],maxx[N],minn[N],ans[N],f[M],n,m;
inline void add1(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline int add2(int x,int y){ x+=y;if(x>=P) x-=P;return x;}
inline int mymax(int x,int y){ return x>y?x:y;}
inline int mymin(int x,int y){ return x<y?x:y;}
struct SegmentTree
{ 
	int tag[M],sum[M],siz[M],num[N];
	void init(int k,int l,int r)
	{ 
		sum[k]=tag[k]=0;
		if(l==r) siz[k]=num[l];
		else
		{ 
			int mid=l+r>>1;
			init(lson,l,mid),init(rson,mid+1,r);
			siz[k]=add2(siz[lson],siz[rson]);
		}
	}
	inline void pushdown(int k)
	{ 
		add1(tag[lson],tag[k]),add1(tag[rson],tag[k]);
		add1(sum[lson],1LL*tag[k]*siz[lson]%P);
		add1(sum[rson],1LL*tag[k]*siz[rson]%P);
		tag[k]=0;
	}
	void add(int k,int l,int r,int x,int y,int z)
	{ 
		if(l==x&&r==y) add1(tag[k],z),add1(sum[k],1LL*z*siz[k]%P);
		else
		{ 
			int mid=l+r>>1;
			if(tag[k]) pushdown(k);
			if(y<=mid) add(lson,l,mid,x,y,z);
			else if(x>mid) add(rson,mid+1,r,x,y,z);
			else add(lson,l,mid,x,mid,z),add(rson,mid+1,r,mid+1,y,z);
			sum[k]=add2(sum[lson],sum[rson]);
		}
	}
	int qry(int k,int l,int r,int x,int y)
	{ 
		if(l==x&&r==y) return sum[k];
		int mid=l+r>>1;
		if(tag[k]) pushdown(k);
		if(y<=mid) return qry(lson,l,mid,x,y);
		if(x>mid) return qry(rson,mid+1,r,x,y);
		return add2(qry(lson,l,mid,x,mid),qry(rson,mid+1,r,mid+1,y));
	}
}tree[4];
//tree[0]:1*... tree[1]:maxx*... tree[2]:minn*... tree[3]:maxx*minn*...
struct query{ int l,r,id;};
vector<query>qry[M];
bool cmpr(query x,query y){ return x.r<y.r;}
void solve(int k,int l,int r)
{ 
	int mid=l+r>>1,tot=qry[k].size();
	if(l==r)
	{ 
		f[k]=1LL*s[l]*s[l]%P;
		for(int i=0;i<tot;++i) add1(ans[qry[k][i].id],1LL*s[l]*s[l]%P);
		return;
	}
	sort(qry[k].begin(),qry[k].end(),cmpr);
	int j=0;while(j<tot&&qry[k][j].r<=mid) ++j;
	maxx[mid]=minn[mid]=s[mid];
	for(int i=mid-1;i>=l;--i)
	{ 
		maxx[i]=mymax(maxx[i+1],s[i]);
		minn[i]=mymin(minn[i+1],s[i]);
	}
	for(int i=l;i<=mid;++i)
		tree[0].num[i]=1,tree[1].num[i]=maxx[i],
		tree[2].num[i]=minn[i],tree[3].num[i]=1LL*maxx[i]*minn[i]%P;
	int ma=s[mid+1],mi=s[mid+1],x=mid+1,y=mid+1,z=mid+1;
	for(int i=0;i<4;++i) tree[i].init(1,l,mid);
	for(int i=mid+1;i<=r;++i)
	{ 
		ma=mymax(ma,s[i]),mi=mymin(mi,s[i]);
		while(l<x&&minn[x-1]>=mi&&maxx[x-1]<=ma) --x;
		while(l<y&&minn[y-1]>=mi) --y;
		while(l<z&&maxx[z-1]<=ma) --z;
		if(x<=mid) tree[0].add(1,l,mid,x,mid,1LL*ma*mi%P);
		if(y<x)
		{ 
			tree[1].add(1,l,mid,y,x-1,mi);
			if(l<y) tree[3].add(1,l,mid,l,y-1,1);
		}
		if(z<x)
		{ 
			tree[2].add(1,l,mid,z,x-1,ma);
			if(l<z) tree[3].add(1,l,mid,l,z-1,1);
		}
		while(j<tot&&qry[k][j].r==i)
		{ 
			if(qry[k][j].l>mid||qry[k][j].l==l&&qry[k][j].r==r){ ++j;continue;}
			for(int t=0;t<4;++t) add1(ans[qry[k][j].id],tree[t].qry(1,l,mid,qry[k][j].l,mid));
			++j;
		}
	}
	for(int i=0;i<4;++i) add1(f[k],tree[i].qry(1,l,mid,l,mid));
	for(int i=0;i<tot;++i)
	{ 
		if(qry[k][i].l==l&&qry[k][i].r==r) continue;
		if(qry[k][i].r<=mid) qry[lson].push_back(qry[k][i]);
		else if(qry[k][i].l>mid) qry[rson].push_back(qry[k][i]);
		else
		{ 
			qry[lson].push_back((query){ qry[k][i].l,mid,qry[k][i].id});
			qry[rson].push_back((query){ mid+1,qry[k][i].r,qry[k][i].id});
		}
	}
	solve(lson,l,mid),solve(rson,mid+1,r);
	add1(f[k],add2(f[lson],f[rson]));
	for(int i=0;i<tot;++i)
		if(qry[k][i].l==l&&qry[k][i].r==r) add1(ans[qry[k][i].id],f[k]);
}
int main()
{ 
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",s+i);
	for(int i=1;i<=m;++i)
	{ 
		scanf("%d%d",&x,&y);
		qry[1].push_back((query){ x,y,i});
	}
	solve(1,1,n);
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}