【BZOJ2038】小Z的袜子（莫队）

Patrickpwq

于 2019-02-17 15:01:37 发布

阅读量235

点赞数

本文链接：https://blog.csdn.net/Patrickpwq/article/details/87534483

版权

博客讲述了作者在解决BZOJ2038问题时，错误地使用了块划分并忽略了排序，却意外通过了洛谷的评测。此情况在提交到WOJ时被发现，引发了对于不同平台评测速度差异的讨论。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

解锁成就：块分错+忘了排序结果还TM在洛谷上AC了....交到WOJ才发现（或许这也是WOJ评测慢的好处？）

//P(same)=sigma(cnt[i]*(cnt[i]-1))/(r-l+1)*(r-l) 
#include<bits/stdc++.h>
#define ll long long
#define re register
const int N=50005;
using namespace std;
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=nc();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=nc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
    x*=f; 
}
int n,m,a[N],size;
ll ans,cnt[N],sol[N][2];
struct Query
{
    ll l,r;
	int id,pos;
    bool operator <(const Query &x) const
    {
        if(this->pos==x.pos)	return this->r<x.r;
        return this->pos<x.pos;
    }
}q[N];
inline void Remove(int p)
{
    ans-=cnt[a[p]]*(cnt[a[p]]-1);
    cnt[a[p]]--;
    ans+=cnt[a[p]]*(cnt[a[p]]-1);
}
inline void Add(int p)
{	
    ans-=cnt[a[p]]*(cnt[a[p]]-1);
    cnt[a[p]]++;
    ans+=cnt[a[p]]*(cnt[a[p]]-1);
}
inline void write(ll x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main()
{
    read(n),read(m);
    size=sqrt(n);
    for(re int i=1;i<=n;i++) read(a[i]);
    for(re int i=1;i<=m;i++) 
        read(q[i].l),read(q[i].r),q[i].id=i,q[i].pos=(q[i].l-1)/size+1;
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(re int i=1;i<=m;i++)
    {
        if(q[i].l==q[i].r)	{sol[q[i].id][0]=0,sol[q[i].id][1]=1;continue;} 
        while(l<q[i].l) Remove(l++);
        while(l>q[i].l) Add(--l);
        while(r<q[i].r) Add(++r);
        while(r>q[i].r) Remove(r--);
        ll temp=(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        ll gcd=__gcd(temp,ans);
        sol[q[i].id][0]=ans/gcd,sol[q[i].id][1]=temp/gcd;
    }
    for(re int i=1;i<=m;i++) 
		write(sol[i][0]),putchar('/'),write(sol[i][1]),putchar('\n');
    return 0;
}