最近又看了一下莫队，发现我以前完全理解错了莫队算法。

莫队算法适用于无修（带修不会啊QAQ@lbn187）的区间询问且若已知[L,R]的答案能够以较快的速度求出[L-1,R],[L+1,R],[L,R-1],[L,R+1],那么就可以使用莫队。

莫队是将所有区间按照一定顺序排序，使得这个区间移动次数较少。

最优的方法就是曼哈顿距离的最小生成树。但写起来太麻烦。

用这种方法排序是比较优秀的：如果L1/blk=L2/blk，那么就按R排序，否则按L排序。

经典例题小Z的袜子（叫你每天代码抄抄）

[51nod1290]询问区间内多少对数差的绝对值<=k，k为全局给定。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 50010
#define M 150010
#define ll long long
using namespace std;
struct zhl
{
	int l,r,id;
	zhl(){}
    zhl(int L,int R,int ID):l(L), r(R), id(ID){}
}eg[N];

int l,r,n,k,q,pos[N],blk,len,gg[M],a[N],b[N],c[N],x,y;
ll Ans,ans[N];

int cmp(zhl x,zhl y)
{
	return pos[x.l]^pos[y.l]?x.l < y.l:x.r < y.r;
}

int g[M];
void update(int x,int y)
{
	for (;x <= len;x += x&-x)
		g[x] += y;
}
int query(int x)
{
	int y = 0;
	for (;x;x -= x&-x)
		y += g[x];
	return y;
}

void solve()
{
	l = r = 1, Ans = 0;
	update(a[1],1);
	rep(i,1,q)
	{
		int L = eg[i].l,R = eg[i].r;
		for (;l < L;l++) update(a[l],-1),Ans -= query(c[l])-query(b[l]-1);
		for (;l > L;update(a[l],1)) l--,Ans += query(c[l])-query(b[l]-1);
		for (;r < R;update(a[r],1)) r++,Ans += query(c[r])-query(b[r]-1);
		for (;r > R;r--) update(a[r],-1),Ans -= query(c[r])-query(b[r]-1);
		ans[eg[i].id] = Ans;
	}
}
 
int main()
{
	scanf("%d%d%d",&n,&k,&q); blk = sqrt(n);
	rep(i,1,n)
	{
		scanf("%d",&a[i]);
		gg[++len] = a[i];
		gg[++len] = a[i]+k;
		gg[++len] = a[i]-k;
	}
	sort(gg+1,gg+len+1);
	len = unique(gg+1,gg+len+1)-gg-1;
	rep(i,1,n)
	{
		b[i] = lower_bound(gg+1,gg+len+1,a[i]-k)-gg;
		c[i] = lower_bound(gg+1,gg+len+1,a[i]+k)-gg;
		a[i] = lower_bound(gg+1,gg+len+1,a[i])-gg;
		pos[i] = (i-1)/blk;
	}
	rep(i,1,q)
	{
		scanf("%d%d",&x,&y);
		eg[i] = zhl(x+1,y+1,i);
	}
	sort(eg+1,eg+q+1,cmp);
	solve();
	rep(i,1,q) printf("%lld\n",ans[i]);
	return 0;
}

[bzoj4540]求一段区间的所有子区间的最小值的和。

考虑加入一个数的贡献，令p为[L,R]的最小值。

那么（p-L+1）*a[p]是其中一部分的贡献，还有的贡献在[p+1,R]。

令sl[i]为1~i的答案，那么sl[R]-sl[p]就是[p+1,R]的答案。

为什么呢？因为p是最小值，也就是说[p+1,R]的所有值的sl都是以sl[p]为基础转移的。

还有一点，莫队的时候应该先增加区间，再减小区间，不然有可能会有L>R的情况，会biubiu。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;

#define N 100010
int L[N],R[N],stk[N],pos[N],pw[20],n,q,top,blk,Left,Right;
ll sl[N],sr[N],a[N],ans[N],now;

int lg[N],f[N][20];
struct xfy
{
	int l,r,id;
}eg[N];
void checkmin(int& x,int y)
{
	if (a[x] > a[y]) x = y;
}

int getmin(int x,int y)
{
	if (x > y) Swap(x,y);
	int l = lg[y-x+1],r1 = f[x][l],r2 = f[y-pw[l]+1][l];
	return a[r1]<a[r2]?r1:r2;
}

void updatel(int l,int r,int ty)
{
	int o = getmin(l,r);
	ll res = a[o]*(r-o+1)+sr[l]-sr[o];
	now += res*ty;
}

void updater(int l,int r,int ty)
{
	int o = getmin(l,r);
	ll res = a[o]*(o-l+1)+sl[r]-sl[o];
	now += res*ty;
}

int cmp(xfy x,xfy y)
{
	return pos[x.l] == pos[y.l]?x.r<y.r:x.l<y.l;
}
int main()
{
	scanf("%d%d",&n,&q); blk = sqrt(n);
	pw[0] = 1;
	rep(i,1,18) pw[i] = pw[i-1]+pw[i-1];
	rep(i,1,n) scanf("%lld",&a[i]);
	rep(i,1,n)
	{
	    for (;top&&a[stk[top]]>=a[i];R[stk[top--]]=i);
		stk[++top] = i;
	}
	for (;top;R[stk[top--]]=n+1);
	drep(i,n,1)
	{
	    for (;top&&a[stk[top]]>a[i];L[stk[top--]]=i);
	    stk[++top] = i;
	}
	for (;top;L[stk[top--]]=0);
	rep(i,1,n) sl[i] = sl[L[i]]+a[i]*(i-L[i]);
	drep(i,n,1) sr[i] = sr[R[i]]+a[i]*(R[i]-i);
	lg[0] = -1;
	rep(i,1,n) lg[i] = lg[i>>1]+1,pos[i] = (i-1)/blk,f[i][0] = i;
	rep(j,1,18)
	{
		rep(i,1,n)
		{
			f[i][j] = f[i][j-1];
			if (i+pw[j-1] <= n) checkmin(f[i][j],f[i+pw[j-1]][j-1]);
		}
	}
	rep(i,1,q) scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].id = i;
	sort(eg+1,eg+q+1,cmp);
	Left = Right = 1;now = a[1];
	rep(i,1,q)
	{
		int l = eg[i].l,r = eg[i].r;
		for (;Right < r;Right++) updater(Left,Right+1,1);
		for (;Left > l;Left--) updatel(Left-1,Right,1);
		for (;Right > r;Right--) updater(Left,Right,-1);
		for (;Left < l;Left++) updatel(Left,Right,-1);
		ans[eg[i].id] = now;
	}
	rep(i,1,q) printf("%lld\n",ans[i]);
	return 0;
}