并不对劲的bzoj2038:p1494:[国家集训队]小Z的袜子

题目大意

有\(n\)(\(n\leq5*10^4\))个数\(a_1,a_2,...,a_n\)(\(\forall i\in[1,n], 1\leq a_i\leq n\))

\(m\)(\(m\leq5*10^4\))次询问，每次给出区间\([L,R]\)，求在\(a_L,a_{L+1},...,a_R\)中随机选两个数，两数相等的概率

题解

设区间\([L,R]\)中，值为\(i\)的数的个数为\(b_i\)

那么答案就是\(\sum_{i=1}^{n}{C_{b_i}^{2}}\)

发现将区间变成\([L+1,R],[L,R+1],[L-1,R],[L,R-1]\)时，维护\(b\)数组的复杂度是\(\Theta(1)\)的

这样就可以用莫队离线解决了

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define maxn 50010

#define blo 223

#define LL long long

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(LL x)

{

    if(x==0){putchar('0');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    return;

}

struct que{int l,r,id;}q[maxn];

int nowl,nowr,num[maxn],n,m,a[maxn];

LL ansa[maxn],ansb[maxn],nowans;

LL gcd(LL a,LL b)

{

    if(a>b)swap(a,b);

    if(!a)return b;

    return gcd(b%a,a);

}

bool cmpl(que x,que y){return x.l<y.l;}

bool cmpr1(que x,que y){return x.r<y.r;}

bool cmpr2(que x,que y){return x.r>y.r;}

LL c2(int x){return (LL)x*(LL)(x-1)/2ll;}

int main()

{

    n=read(),m=read();

    rep(i,1,n)a[i]=read();

    rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;

    sort(q+1,q+m+1,cmpl);

    for(int i=1,s=1,t=1+blo;s<=m;s=t+1,t=s+blo,i)

    {

        int lim=min(t,m);

        if(i&1)sort(q+s,q+lim+1,cmpr1);

        else sort(q+s,q+lim+1,cmpr2);

    }nowl=1,nowr=0;

    rep(i,1,m)

    {

        while(nowr<q[i].r)nowr++,nowans-=c2(num[a[nowr]]),num[a[nowr]]++,nowans+=c2(num[a[nowr]]);

        while(nowl>q[i].l)nowl--,nowans-=c2(num[a[nowl]]),num[a[nowl]]++,nowans+=c2(num[a[nowl]]);

        while(nowr>q[i].r)nowans-=c2(num[a[nowr]]),num[a[nowr]]--,nowans+=c2(num[a[nowr]]),nowr--;

        while(nowl<q[i].l)nowans-=c2(num[a[nowl]]),num[a[nowl]]--,nowans+=c2(num[a[nowl]]),nowl++;

        if(nowans==0)ansa[q[i].id]=0,ansb[q[i].id]=1;

        else

        {

            ansa[q[i].id]=nowans,ansb[q[i].id]=c2(q[i].r-q[i].l+1);

            LL gdc=gcd(ansa[q[i].id],ansb[q[i].id]);

            ansa[q[i].id]/=gdc,ansb[q[i].id]/=gdc;

        }

    }

    rep(i,1,m)write(ansa[i]),putchar('/'),write(ansb[i]),putchar('\n');

    return 0;

}

巴特西

并不对劲的bzoj2038:p1494:[国家集训队]小Z的袜子

题目大意

题解

代码

最新文章

热门文章