題目

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;
}