洛谷 P1494 [国家集训队]小Z的袜子 /【模板】莫队

题目链接

0x00 思路

我们考虑统计区间内相同颜色的袜子的个数,设(S_i)表示第(i)种颜色的袜子数,则这种颜色袜子对方案数的贡献就是(S_i * (S_i - 1))

长度为(S)的区间,其总方案数为(S * (S - 1))

最后答案约分即可,如果概率为0,输出0/1

0x01 莫队维护

我们只要维护区间的相同颜色袜子数,存在一个(cnt)数组里,同时维护可行方案数(sum)

每次用两个指针(L R),不断左右移动,去和查询区间重合即可

部分代码:

    while(L > q[i].l) -- L,sum += cnt[a[L]] << 1,++ cnt[a[L]];
    while(L < q[i].l) -- cnt[a[L]],sum -= cnt[a[L]] << 1,++ L;
    while(R > q[i].r) -- cnt[a[R]],sum -= cnt[a[R]] << 1,-- R;
    while(R < q[i].r) ++ R,sum += cnt[a[R]] << 1,++ cnt[a[R]];

注意维护的顺序

对于询问区间,我们将其排序,排序原则

1. 将左端点分块,块大小为(sqrt(n)),记左端点所在的块的编号为(pos)

2. 如果两个查询区间(pos)不同,则按(pos)从小到大排序

3. 如果(pos)相同,则按右端点(r)从小到大排序

部分代码:

bool cmp(node a,node b){
    return (a.pos ^ b.pos) ? (a.pos < b.pos) : (a.r < b.r);
}

复杂度证明 参考博客 莫队算法——从入门到黑题

1. 右端点的移动:在每一块里复杂度最坏是(O(n))的,总共有(O(sqrt{n}))块,复杂度(O(n sqrt{n}))

2. 左端点的移动:在每一块里有(X_i)个左端点,左端点的移动最坏是(O(X_isqrt{n}))的;从前一块跳到后一块,最坏是(O(2 sqrt{n}))的距离,也就是说左端点每次跳跃都有可能是(O(sqrt{n}))级别的,复杂度(O(n sqrt{n}))

3. 排序,复杂度(O(n log{n}))

总复杂度是(O(nsqrt{n} ))

0x02 Code

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int read(){
	int x=0; char c=getchar(); int flag=1;
	while(!isdigit(c)) { if(c=='-') flag=-1; c=getchar(); }
	while(isdigit(c)) { x=((x+(x<<2))<<1)+(c^48); c=getchar(); }
	return x*flag;
}
int n,m,a[N],cnt[N];
struct node{ int l,r,pos,id; } q[N]; 
bool cmp(node a,node b){
    return (a.pos ^ b.pos) ? (a.pos < b.pos) : ( (a.pos & 1) ? (a.r < b.r) : (a.r > b.r) );
}
long long ans[N][2];
long long gcd(long long x,long long y) { return !y ? x : gcd(y,x % y); }
signed main(){
    n = read(),m = read();
    int size = sqrt(n);
    for(int i = 1;i <= n;i ++) a[i] = read();
    for(int i = 1;i <= m;i ++) q[i].l = read(),q[i].r = read(),q[i].pos = (q[i].l - 1) / size + 1, q[i].id = i;
    sort(q + 1,q + m + 1,cmp);
    long long sum=0; int L=1,R=0;
    for(int i = 1;i <= m;i ++){
	    while(L > q[i].l) -- L,sum += cnt[a[L]] << 1,++ cnt[a[L]];
		while(L < q[i].l) -- cnt[a[L]],sum -= cnt[a[L]] << 1,++ L;
		while(R > q[i].r) -- cnt[a[R]],sum -= cnt[a[R]] << 1,-- R;
		while(R < q[i].r) ++ R,sum += cnt[a[R]] << 1,++ cnt[a[R]];
		
		ans[q[i].id][0] = sum; ans[q[i].id][1] = 1ll * (R - L + 1) * (R - L);
	}
	for(int i = 1;i <= m;i ++){
	    if(ans[i][0] == 0) { puts("0/1"); continue; }
		long long z = gcd(ans[i][0],ans[i][1]);
	    ans[i][0] /= z; ans[i][1] /= z;
	    printf("%lld/%lld
",ans[i][0],ans[i][1]);
	    
	}
	return 0;
}