[2009國家集訓隊]小Z的襪子(hose) 分塊做法

題目描述: Click here

作為一個生活散漫的人，小Z每天早上都要耗費很久從一堆五顔六色的襪子中找出一雙來穿。終于有一天，小Z再也無法忍受這惱人的找襪子過程，于是他決定聽天由命……

具體來說，小Z把這N隻襪子從1到N編号，然後從編号L到R(L 盡管小Z并不在意兩隻襪子是不是完整的一雙，甚至不在意兩隻襪子是否一左一右，他卻很在意襪子的顔色，畢竟穿兩隻不同色的襪子會很尴尬。

你的任務便是告訴小Z，他有多大的機率抽到兩隻顔色相同的襪子。當然，小Z希望這個機率盡量高，是以他可能會詢問多個(L,R)以友善自己選擇。

這個oj 不支援cout 。。被坑了一個多點。。＝＝第一次碰到這樣的oj。。  

解法應該不難。。就是分塊然後進行統計。。因為時限太長。。怎麼樣都不會逾時。。暴力除外。

freq[i] 統計的出現的 >= i次的數目。。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55555;
const int Sqrt = 333;
#define ll long long
int n,m;
int a[N];
int freq[N],cnt[N];
int zl[N],rr[N],idx[N];
pair<ll,ll> ans[N];
bool cmp(int x,int y){
	if(zl[x]/Sqrt == zl[y]/Sqrt)
		return rr[x] < rr[y];
	return zl[x] < zl[y];
}
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
pair<ll,ll> query(int l,int r){
	ll ans2 = (long long)(r-l+1)*(r-l)/2;
	ll ans1 = 0,i = 1;
	while(freq[i]>0){
		//printf("freq[%d]=%d\n",i,freq[i]);
		int num = freq[i] - freq[i+1];
		if(num)
			ans1 += (ll)i*(i-1)/2*num;
		i++;
	}
	int gc = gcd(ans2,ans1);
	return make_pair(ans1/gc,ans2/gc);
}
int main(){
	while(scanf("%d %d",&n,&m)!=EOF){
		memset(freq,0,sizeof(freq));
		memset(cnt,0,sizeof(cnt));
		for(int i = 1;i <= n;i++) scanf("%d",a+i);
		for(int i = 1;i <= m;i++) scanf("%d %d",zl+i,rr+i);
		for(int i = 1;i <= m;i++) idx[i] = i;
		sort(idx+1,idx+1+m,cmp);
		int lp = 1, rp = 0;
		for(int i = 1;i <= m;i++){
			int l = zl[idx[i]] , r = rr[idx[i]] ;
			while(rp<r) freq[++cnt[a[++rp]]]++;
		//	printf("ce freq[1]=%d\n",freq[1]);
			while(lp>l) freq[++cnt[a[--lp]]]++;
			while(rp>r) freq[cnt[a[rp--]]--]--;
			while(lp<l) freq[cnt[a[lp++]]--]--;
			ans[idx[i]] = query(l,r);
		} 
		for(int i = 1;i <= m;i++){
			printf("%lld/%lld\n",ans[i].first,ans[i].second);
		}
	}
	return 0;
}
           

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 105555;
int Sqrt = 333;
#define ll long long
int n,m;
int a[N];
int cnt[N];
int zl[N],rr[N],idx[N];
struct node{
	ll first,second;
	node(){}
	node(ll _f,ll _s){ first=_f , second=_s;}

};
node ans[N];
/*
bool cmp(int x,int y){
	if(zl[x]/Sqrt == zl[y]/Sqrt)
		return rr[x] < rr[y];
	return zl[x] < zl[y];
}*/
struct q_node{
	int l,r,id;
	bool operator < (const q_node& tmp) const{
		if(l / Sqrt == tmp.l / Sqrt) return r < tmp.r;
		return l < tmp.l;
	}
}Q[N];
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int main(){
	while(scanf("%d%d",&n,&m) == 2){
		memset(cnt,0,sizeof(cnt));
		for(int i = 1;i <= n;i++) scanf("%d",a+i);
		for(int i = 1;i <= m;i++) scanf("%d %d",&Q[i].l,&Q[i].r);
		for(int i = 1;i <= m;i++) Q[i].id = i;
		Sqrt = (1.0)*sqrt(n);
		sort(Q+1,Q+1+m);
		int lp = 1, rp = 0;
		ll ans1  ,ans2  , tmp = 0 ;
		for(int i = 1;i <= m;i++){
			int l = Q[i].l , r = Q[i].r;
			while(rp<r) {
				rp++;
				tmp -= (ll)cnt[a[rp]]*cnt[a[rp]];
				cnt[a[rp]]++;
				tmp += (ll)cnt[a[rp]]*cnt[a[rp]];
			}
			while(lp>l) {
				lp--;
				tmp -= (ll)cnt[a[lp]]*cnt[a[lp]];
				cnt[a[lp]]++;
				tmp += (ll)cnt[a[lp]]*cnt[a[lp]];
			}
			while(rp>r) {
				tmp -= (ll)cnt[a[rp]]*cnt[a[rp]];
				cnt[a[rp]]--;
				tmp += (ll)cnt[a[rp]]*cnt[a[rp]];
				rp--;
			}
			while(lp<l) {
				tmp -= (ll)cnt[a[lp]]*cnt[a[lp]];
				cnt[a[lp]]--;
				tmp += (ll)cnt[a[lp]]*cnt[a[lp]];
				lp++;
			}
			ans1 = tmp - (r-l+1); ans2 = (ll)(r-l+1)*(r-l);
			ll gc = gcd(ans2,ans1);
			ans[Q[i].id] = node(ans1/gc , ans2/gc);
		} 
		for(int i = 1;i <= m;i++){
			printf("%lld/%lld\n",ans[i].first,ans[i].second);
			//cout << ans[i].first << "/" << ans[i].second << endl;
		}
	}
	return 0;
}
           

0 0這是類似思路。不同寫法。。