题目：给出一个数列，要求快速查询区间lr内相同数字的对数。
思路：对于每次询问暴力跑，但是我们注意到由于可以复用之前的结果，所以不同的计算顺序计算量可能不同，直观上来说，两个查询点的曼哈顿距离越短，需要计算的量就越小。于是我们可以找出一个最佳计算顺序，就是平面点阵的最短哈密顿回路。由于这是np的，所以可以用最小曼哈顿生成树代替。再简化一下，可以使用分快处理的方法得到比较快的速度。
这就是所谓的莫队算法。
/* * @author: Cwind */ ///#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-7) #define IINF (1<<29) #define LINF (1ll<<59) #define INF (1000000000) #define FINF (1e3) #define clr(x) memset((x),0,sizeof (x)) #define cp(a,b) memcpy((a),(b),sizeof (a)) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,int> P; const int maxn=5e4+3000; struct Q{ int l,r; int id; }q[maxn];; bool cmp1(const Q &a,const Q &b){return a.r<b.r;} vector<Q> B[50]; int n,m; int c[maxn]; ll a[maxn]; ll ans[maxn][2]; void solve(){ for(int i=1;i<=m;i++) B[q[i].l/1001].pb(q[i]); for(int i=0;i<50;i++) sort(B[i].begin(),B[i].end(),cmp1); ll ax=0,ay=0; int l=1,r=1; a[c[1]]++; for(int i=0;i<50;i++){ for(int j=0;j<B[i].size();j++){ int tl=B[i][j].l,tr=B[i][j].r; for(int k=r;k>tr;k--){ax-=a[c[k]]-1;a[c[k]]--;ay-=k-l;} for(int k=r+1;k<=tr;k++){ax+=a[c[k]];a[c[k]]++;ay+=k-l;} for(int k=l;k<tl;k++){a[c[k]]--;ax-=a[c[k]];ay-=tr-k;} for(int k=l-1;k>=tl;k--){ax+=a[c[k]];a[c[k]]++;ay+=tr-k;} l=tl,r=tr; ll dd=__gcd(ax,ay); int id=B[i][j].id; ans[id][0]=ax/dd; ans[id][1]=ay/dd; if(ax==0) ans[id][1]=1; } } } int main(){ freopen("/home/slyfc/CppFiles/in","r",stdin); cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } solve(); for(int i=1;i<=m;i++) printf("%lld/%lld ",ans[i][0],ans[i][1]); return 0; }