简要:
莫队算法是一个对于区间树或其他结构离线 (在线) 维护的算法, 此算法基于一些基本算法, 例如暴力维护, 树状数组, 分块, 最小曼哈顿距离生成树, 对其进行揉合从而产生的一个简单易懂且短小好写的算法此算法在很多情况下可以很轻松的切掉一些复杂而且难写的数据结构问题
例题: BZOJ2038
Description
作为一个生活散漫的人, 小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿终于有一天, 小 Z 再也无法忍受这恼人的找袜子过程, 于是他决定听天由命
具体来说, 小 Z 把这 N 只袜子从 1 到 N 编号, 然后从编号 L 到 R(L 尽管小 Z 并不在意两只袜子是不是完整的一双, 甚至不在意两只袜子是否一左一右, 他却很在意袜子的颜色, 毕竟穿两只不同色的袜子会很尴尬
你的任务便是告诉小 Z, 他有多大的概率抽到两只颜色相同的袜子当然, 小
- Sample Input
- 6 4
- 1 2 3 3 3 2
- 2 6
- 1 3
- 3 5
- 1 6
- Sample Output
- 2/5
- 0/1
- 1/1
- 4/15
- HINT
- #include <bits/stdc++.h>
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <vector>
- #include <map>
- #include <set>
- #include <bitset>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <iomanip>
- #include <cstdlib>
- using namespace std;
- #define is_lower(c) (c>=a && c<=z)
- #define is_upper(c) (c>=A && c<=Z)
- #define is_alpha(c) (is_lower(c) || is_upper(c))
- #define is_digit(c) (c>=0 && c<=9)
- #define min(a,b) ((a)<(b)?(a):(b))
- #define max(a,b) ((a)>(b)?(a):(b))
- #define IO ios::sync_with_stdio(0);\
- cin.tie(0); cout.tie(0);
- #ifdef ONLINE_JUDGE
- #define hash rename_hash
- #define next rename_next
- #define prev rename_prev
- #endif
- #define For(i,a,b) for(int i = a; i <= b; i++)
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> pii;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef double db;
- const ll inf=1000000007LL;
- const double EPS=1e-10;
- const ll inf_ll=(ll)1e18;
- const ll maxn=100005LL;
- const ll mod=1000000007LL;
- const int N = 50000+5;
- int n,m,sum[N],a[N];
- ll ans;
- struct node{
- int l,r,id,block;
- ll a,b;
- }q[N];
- ll gcd(ll a,ll b)
- {
- return b?gcd(b,a%b):a;
- }
- bool cmp(node a,node b){
- return a.block==b.block?a.r<b.r:a.l<b.l;
- }
- bool cmp1(node a,node b){
- return a.id<b.id;
- }
- void add(int x)
- {
- ans += (2*sum[a[x]]+1);
- sum[a[x]]++;
- }
- void les(int x)
- {
- ans -= (2*sum[a[x]]-1);
- sum[a[x]]--;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- int x = sqrt(n);
- For(i,1,n)
- scanf("%d",&a[i]);
- For(i,1,m)
- {
- scanf("%d%d",&q[i].l,&q[i].r);
- q[i].id=i;
- q[i].block = q[i].l/x;
- }
- sort(q+1,q+m+1,cmp);
- int l=1,r=0;
- For(i,1,m)
- {
- if(q[i].l==q[i].r)
- {
- q[i].a=0;q[i].b=1;
- continue;
- }
- while(l<q[i].l)les(l++);
- while(l>q[i].l)add(--l);
- while(r>q[i].r)les(r--);
- while(r<q[i].r)add(++r);
- q[i].a = ans-(q[i].r-q[i].l+1);
- q[i].b =1LL*(q[i].r-q[i].l)*(q[i].r-q[i].l+1);
- ll xx = gcd(q[i].a,q[i].b);
- q[i].a/=xx;
- q[i].b/=xx;
- }
- sort(q+1,q+m+1,cmp1);
- For(i,1,m)
- printf("%lld/%lld\n",q[i].a,q[i].b);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2516625.html