莫队算法

确实是看过的最良心的讲解： https://www.cnblogs.com/CsOH/p/5904430.html

• 问题：有n个数组成一个序列，有m个形如询问L, R的询问，每次询问需要回答区间内至少出现2次的数有哪些。

朴素的解法需要读取O(nm)次数。如果数据范围小，可以用数组，时间复杂度为O(nm)。如果使用STL的Map来保存出现的次数，则需要O(nmlogn)的复杂度。有没有更快的方法呢？

注意到询问并没有强制在线，因此我们可以使用离线方法。注意到一点，如果我们有计算完[L, R]时的“中间变量”（在本题为每个数出现的次数），那么[L - 1, R]、[L + 1, R]、[L, R - 1]、[L, R + 1]都能够在“中间变量”的“基本操作时间复杂度”得出。如果能安排适当的询问顺序，使得每次询问都能用上上次运行产生的中间变量，那么我们将可以在更优的复杂度完成整个询问。

如果数据较小，用数组，时间复杂度为O(1)；如果数据较大，可以考虑用离散化或map，时间复杂度为O(logn)。

那如何安排询问呢？这里有个时间复杂度非常优秀的方法：首先将每个询问视为一个“点”，两个点P1, P2之间的距离为abs(L1 - L2) + abs(R1 - R2)，即曼哈顿距离，然后求这些点的最小生成树，然后沿着树边遍历一次。由于这里的距离是曼哈顿距离，所以这样的生成树被称为“曼哈顿最小生成树”。最小曼哈顿生成树有专用的算法，求生成树时间复杂度可以仅为O(mlogm)。

其实这里是建边的算法，建边后依然使用传统的Prim或者Kruskal算法来求最小生成树。

不幸的是，曼哈顿最小生成树的写法很复杂，考场上不建议这样做. 　
一种直观的办法是按照左端点排序，再按照右端点排序。但是这样的表现不好。特别是面对精心设计的数据，这样方法表现得很差。
　　举个例子，有6个询问如下：(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。
　　这个数据已经按照左端点排序了。用上述方法处理时，左端点会移动6次，右端点会移动移动98+97+95+98+95=483次。右端点大幅度地来回移动，严重影响了时间复杂度——排序的复杂度是O(mlogm)，所有左端点移动次数仅为为O(n)，但右端点每个询问移动O(n)，共有m个询问，故总移动次数为O(nm)，移动总数为O(mlogm + nm)。运行时间上界并没有减少。
　　其实我们稍微改变一下询问处理的顺序就能做得更好：(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。
　　左端点移动次数为2+2+1+2+2=9次，比原来稍多。右端点移动次数为2+3+95+3+1=104，右端点的移动次数大大降低了。
　　上面的过程启发我们：①我们不应该严格按照升序排序，而是根据需要灵活一点的排序方法；②如果适当减少右端点移动次数，即使稍微增多一点左端点移动次数，在总的复杂度上看，也是划算的。
　　在排序时，我们并不是按照左右端点严格升序排序询问，而只是令其左右端点处于“大概是升序”的状态。具体的方法是，把所有的区间划分为不同的块，将每个询问按照左端点的所在块序号排序，左端点块一样则按照右端点排序。注意这个与上一个版本的不同之处在于“第一关键字”是左端点所在块而非左端点。
　　莫队算法首先将整个序列分成√n个块（同样，只是概念上分的块，实际上我们并不需要严格存储块），接着将每个询问按照块序号排序（一样则按照右端点排序）。之后，我们从排序后第一个询问开始，逐个计算答案。

模板题：Harvest of Apples

纪念再一次打铁和第一次倒数第一

题目描述

There are n apples on a tree, numbered from 1 to n.
Count the number of ways to pick at most m apples.

输入

The first line of the input contains an integer T (1≤T≤105) denoting the number of test cases.
Each test case consists of one line with two integers n,m (1≤m≤n≤105).

输出

For each test case, print an integer representing the number of ways modulo 109+7.

样例输入

2
5 2
1000 500

样例输出

16
924129523

组合数的前缀和
将询问离线下来
根据公式递推S(m,n)=2*S(m-1,n)-C(m-1,n-1)来add或erase

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mp make_pair
#define met(a,x) memset(a,x,sizeof(a))
using namespace std;
const int maxn=1e5+7;
ll ans[maxn],two;
int block;
ll fac[maxn],inv[maxn];
const int mod=1e9+7;
struct node{
    int l,r,i;
    bool operator<(const node&c) const {
        if(l/block==c.l/block){
            return r/block<c.r/block;
        }
        else return l/block<c.l/block;
    }
}s[maxn];
ll qpow(ll a,ll n){
    ll res=1;
    while (n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
void init(){
    fac[0]=1;
    for (ll i = 1; i < maxn; ++i) {
        fac[i]=fac[i-1]*i%mod;
    }
    inv[maxn-1]=qpow(fac[maxn-1],mod-2);
    for (ll i = maxn-2; i>=0 ; --i) {
        inv[i]=inv[i+1]*(i+1)%mod;
    }
    two=qpow(2,mod-2);
}
ll C(int m, int n){
    if(!m||!n) return 1;
    if(m<n) return 0;
    return fac[m]*inv[n]%mod*inv[m-n]%mod;
}
int main(){
    init();
    int t;scanf("%d",&t);
    for (int i = 1; i <=t ; ++i) {
        scanf("%d%d",&s[i].l,&s[i].r);
        s[i].i=i;
    }
    block=sqrt(1e5);
    sort(s+1,s+1+t);ll sum=1;
    for (int i = 1,l=1,r=0; i <=t ; ++i) {
        while (l<s[i].l){sum=(2*sum%mod-C(l++,r)+mod)%mod;}
        while (l>s[i].l){sum=(sum+C(--l,r))%mod*two%mod;}
        while (r<s[i].r){sum=(sum+C(l,++r))%mod;}
        while (r>s[i].r){sum=(sum-C(l,r--)+mod)%mod;}
        ans[s[i].i]=sum;
    }
    for (int i = 1; i <=t; ++i) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}