BZOJ 2038 小z的袜子 & 莫队算法(不就是个暴力么..)

时间：2023-03-08 15:57:02

题意:

　　给一段序列,询问一个区间,求出区间中.....woc! 贴原题!

　　作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

sol:

　　莫队大法好,莫队就是换一个方法打暴力,有一个非常6的论文,极为清楚易懂...(先挖个坑,找不到....)

　　那么就直接上代码了...(第一发忘开ll....已经好几次这样了....

CODE:

　　

/*==========================================================================

# Last modified: 2016-02-27 16:55

# Filename: 2038.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 100000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

int L,R;

struct Query{

	int l,r,id,op;

}q[maxm];

struct Answer{

	ll x,tot;

}ans[maxm];

bool cmp(const Query &x,const Query &y){

	if(x.op==y.op) return x.r<y.r;

	 else return x.op<y.op;

}

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}

ll a[maxn],cnt[maxn];

ll tmp=0;

void add(int i){ tmp+=cnt[a[i]]; cnt[a[i]]++;}

void remove(int i){cnt[a[i]]--;tmp-=cnt[a[i]];}

void solve(int l,int r,int id){

	while (l>L) {remove(L); L++;}

	while (l<L) {L--; add(L);}

	while (r<R) { remove(R); R--;}

	while (r>R) { R++; add(R);}

	ans[id].x=tmp;

//	FORP(i,l,r) ans[id].x+=(cnt[i]*(cnt[i-1])/2);

}

int main(){

	int n,m; read(n); read(m);

	int sz=trunc(sqrt(n));//num=n/sz+n%sz?0:1;

	FORP(i,1,n)	read(a[i]);

	FORP(i,1,m){

		read(q[i].l); read(q[i].r); q[i].id=i;

		q[i].op=q[i].l/sz+(q[i].l%sz?1:0);

	}

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

	tmp=0,L=q[1].l,R=q[1].r;

	ll num=R-L+1;

	FORP(i,L,R) add(i);

	ans[q[1].id].x=tmp; ans[q[1].id].tot=num*(num-1)/2;

	FORP(i,2,m){

		num=q[i].r-q[i].l+1 ;

		//if (i==1) L=q[i].l,R=q[i].r;

		ans[q[i].id].tot=num*(num-1)/2;

		solve(q[i].l,q[i].r,q[i].id);

	}

	FORP(i,1,m){

		if (ans[i].x==0) {printf("0/1\n"); continue;}

		ll t=gcd(ans[i].x,ans[i].tot);

		printf("%lld/%lld\n",ans[i].x/t,ans[i].tot/t);

	}

}

相关文章