4.21

闲话

做题纪要

4.22

闲话

做题纪要

luogu P1494 [国家集训队] 小 Z 的袜子

• 设 \([l,r]\) 内每个数出现的次数为 \(cnt_{i}\) ，有 \(\begin{aligned} \frac{\sum\limits_{i=1}^{\max\limits_{j=1}^{n} \{ c_{j} \}} \binom{cnt_{i}}{2}}{\binom{r-l+1}{2}} \end{aligned}\) 即为所求。

• 注意莫队在修改对是否大于 \(0\) 进行特判。

  点击查看代码

  ll a[50010],cnt[50010],L[50010],R[50010],pos[50010],klen,ksum;
  pair<ll,ll>ans[50010];
  struct ask
  {
  	ll l,r,id;
  }q[50010];
  bool q_cmp(ask a,ask b)
  {
  	return (pos[a.l]==pos[b.l])?((pos[a.l]%2==1)?(a.r<b.r):(a.r>b.r)):(a.l<b.l);
  }
  void init(ll n,ll m)
  {
  	klen=n/sqrt(m)+1;
  	ksum=n/klen;
  	for(ll i=1;i<=ksum;i++)
  	{
  		L[i]=R[i-1]+1;
  		R[i]=R[i-1]+klen;
  	}
  	if(R[ksum]<n)
  	{
  		ksum++;
  		L[ksum]=R[ksum-1]+1;
  		R[ksum]=n;
  	}
  	for(ll i=1;i<=ksum;i++)
  	{
  		for(ll j=L[i];j<=R[i];j++)
  		{
  			pos[j]=i;
  		}
  	}
  }
  void add(ll x,ll &sum)
  {
  	sum-=(cnt[a[x]]>=1)*cnt[a[x]]*(cnt[a[x]]-1)/2;
  	cnt[a[x]]++;
  	sum+=cnt[a[x]]*(cnt[a[x]]-1)/2;
  }
  void del(ll x,ll &sum)
  {
  	sum-=cnt[a[x]]*(cnt[a[x]]-1)/2;
  	cnt[a[x]]--;
  	sum+=(cnt[a[x]]>=1)*cnt[a[x]]*(cnt[a[x]]-1)/2;
  }
  ll gcd(ll a,ll b)
  {
  	return b?gcd(b,a%b):a;
  }
  int main()
  {
  	ll n,m,l=1,r=0,sum=0,d,i;
  	cin>>n>>m;
  	for(i=1;i<=n;i++)
  	{
  		cin>>a[i];
  	}
  	init(n,m);
  	for(i=1;i<=m;i++)
  	{
  		cin>>q[i].l>>q[i].r;
  		q[i].id=i;
  	}
  	sort(q+1,q+1+m,q_cmp);
  	for(i=1;i<=m;i++)
  	{
  		while(l>q[i].l)
  		{
  			l--;
  			add(l,sum);
  		}
  		while(r<q[i].r)
  		{
  			r++;
  			add(r,sum);
  		}
  		while(l<q[i].l)
  		{
  			del(l,sum);
  			l++;
  		}
  		while(r>q[i].r)
  		{
  			del(r,sum);
  			r--;
  		}
  		ans[q[i].id]=make_pair(sum,(q[i].r-q[i].l+1)*(q[i].r-q[i].l+1-1)/2);
  	}
  	for(i=1;i<=m;i++)
  	{
  		if(ans[i].first==0)
  		{
  			cout<<"0/1"<<endl;
  		}
  		else
  		{
  			d=gcd(ans[i].first,ans[i].second);
  			if(d==0)
  			{
  				cout<<"0/1"<<endl;
  			}
  			else
  			{
  				cout<<ans[i].first/d<<"/"<<ans[i].second/d<<endl;
  			}
  		}
  	}
  	return 0;
  }