모 팀 알고리즘, JZOJ 1902, [2010 합숙 팀 출제] 작은 Z 양말

제목.
오래 전부터 이 알고리즘 을 자주 들 었 지만 막 팀 의 문 제 를 풀 시간 이 없 었 습 니 다. 오늘 드디어 시간 이 생 겼 습 니 다. QAQ Description
생활 이 산만 한 사람 으로서 Z 군 은 매일 아침 오 랜 시간 을 들 여 알록달록 한 양말 한 무더기 에서 한 켤레 를 찾 아 신어 야 한다.마침내 어느 날, 작은 Z 는 더 이상 이 짜증 나 는 양말 을 찾 는 과정 을 참 을 수 없 었 다. 그래서 그 는 운명 에 맡 기기 로 결정 했다.(L. 작은 Z 는 두 개의 양말 이 완전한 한 켤레 인지 아 닌 지 에 대해 서 는 신경 쓰 지 않 는 다. 심지어 두 개의 양말 이 왼쪽 과 오른쪽 인지 에 대해 서 는 신경 쓰 지 않 는 다. 그 는 양말 의 색깔 에 신경 을 쓴다. 왜냐하면 두 개의 다른 색 의 양말 을 신 으 면 어색 하기 때문이다. 너의 임 무 는 Z 에 게 그 가 두 개의 색깔 이 같은 양말 을 뽑 을 확률 이 얼마나 되 는 지 알려 주 는 것 이다. 물론 Z 는 이 확률 이 최대한 높 기 를 바란다. 그래서 그 는 가능 한 한 한 한 높 은 것 을 원한 다.선택 하기 편 하도록 여러 개 (L, R) 를 묻는다.
Input
입력 파일 의 첫 줄 에는 두 개의 정수 N 과 M. N 이 양말 의 수량 이 고, M 은 작은 Z 가 제시 한 문의 수량 이 포함 되 어 있 습 니 다. 다음 줄 에는 N 개의 정수 Ci 가 포함 되 어 있 습 니 다. 그 중에서 Ci 는 두 번 째 양말 의 색깔 을 표시 하고, 같은 색깔 은 같은 숫자 로 표시 합 니 다. 그 다음 M 줄 에는 줄 마다 두 개의 정수 L, R 은 하나의 질문 을 표시 합 니 다.
Output
출력 파일 은 M 줄 을 포함 하고 있 습 니 다. 각 질문 의 한 줄 에서 출력 점수 A / B 는 해당 질문 의 구간 [L, R] 에서 양말 두 개 색상 이 같은 확률 을 무 작위 로 추출 합 니 다. 이 확률 이 0 이면 0 / 1 을 출력 합 니 다. 그렇지 않 으 면 출력 된 A / B 는 최소 점수 여야 합 니 다. (예시 참조)
Sample Input
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
Sample Output
2/5
0/1
1/1
4/15
Data Constraint
Hint
질문 1: 총 C (5, 2) = 10 가지 가능, 그 중 2 개 를 뽑 으 면 1 가지 가능, 3 개 를 뽑 으 면 3 가지 가능, 확률 (1 + 3) / 10 = 4 / 10 = 2 / 5. 질문 2: 총 C (3, 2) = 3 가지 가능, 같은 색깔 의 양말 을 뽑 을 수 없 으 며 확률 은 0 / 3 = 0 / 1. 질문 3: 총 C (3, 2)= 3 가지 가능성 은 모두 3 개 를 추출 하 는 것 이 고 확률 은 3 / 3 = 1 / 1 이다. 주: 상기 C (a, b) 는 조합 수 를 나타 내 고 조합 수 C (a, b) 는 a 개의 서로 다른 물품 에서 b 개의 선택 방안 수 를 선택 하 는 것 과 같다.
【 데이터 범 위 】 30% 의 데이터 중 N, M ≤ 5000; 60% 의 데이터 중 N, M ≤ 25000; 100% 의 데이터 중 N, M ≤ 50000, 1 ≤ L < R ≤ N, Ci ≤ N.
모 팀 알고리즘
O (1) 또는 O (log) 의 시간 이 한 상태 (l, r) 에서 (l + 1, r), (l - 1, r), (l, r + 1), (l, r + 1) 로 바 뀔 수 있다 면 우 리 는 모 팀 알고리즘 을 사용 할 수 있다 ~ (≥ ≤)/ ~ 모 팀 알고리즘 은 대략 이 렇 습 니 다. 모 팀 알고리즘 은 오프라인 알고리즘 입 니 다. 우 리 는 먼저 모든 질문 을 l 을 첫 번 째 키워드 로 하고 r 를 두 번 째 키워드 로 순 서 를 정 한 다음 에 가장 큰 왼쪽 점 수 를 얻 습 니 다. 우 리 는 Q - − √ 마다 한 번 씩 나 눈 다음 에 각 블록 을 두 번 째 키워드 에 따라 순 서 를 정 합 니 다.(어쨌든 저 는 그렇게 생각 합 니 다. 왜 다른 사람 이 한 번 만 순 서 를 정 하 는 지 모 르 겠 습 니 다. QAQ) 그러면 지금 각 조각 에 대해 가장 작은 왼쪽 점 위치 와 가장 큰 왼쪽 점 위치 의 차 이 는 Q - − √ 입 니 다. 그리고 전체 정렬 후의 배열 왼쪽 점 은 단 조 롭 게 증가 하고 있 습 니 다. 그러면 왼쪽 점 에 대한 처 리 는 O (n - 8727, Q - √) 입 니 다.그러면 오른쪽 단점 은 각 조각 에 대해 오른쪽 단점 도 단 조 롭 게 증가 하고 모두 Q - − √ 개 에 불과 하기 때문에 오른쪽 단점 을 처리 하 는 이론 적 시간 복잡 도와 왼쪽 단점 은 같다. 그래서 모 팀 의 시간 복잡 도 는 O (n - 8727, Q - √) 이다.
이 문제 의 해법
이 문 제 는 바로 누 드 모 팀 입 니 다. 먼저 상기 방법 에 따라 두 번 째 순 서 를 정 의 했 습 니 다. s [i] 를 현재 의 l 에서 r 까지 모두 s [i] 개 i 가 있 습 니 다. 그러면 매번 에 하나의 수 a [i] 를 삭제 하면 s [a] 를 하나 줄 이 고 ans [i] 를 s [a] 에서 빼 면 됩 니 다. 그리고 다른 디 테 일 도 있 습 니 다. 예 를 들 어 처음에 ans [i] 의 부 가 는 ans [i - 1] 입 니 다.그리고 정렬 하기 전에 처음에 위 치 를 기록 해 야 합 니 다. 마지막 에 원래 순서대로 출력 해 야 하기 때 문 입 니 다. 그리고 세부 사항 이 많 습 니 다. QAQ. 구체 적 으로 제 코드 를 보시 면 됩 니 다.
코드 를 붙이다
왜 우리 모 팀 이 이렇게 못 생 겼 는데 도 이렇게 길 어?

var
    i,j,k,n,m,x,y,l,r,t1,t2:longint;
    cy:int64;
    a,p,s:array[0..50005]of longint;
    b:array[0..50005,1..3]of longint;
    ans,cc,a1,a2:array[0..50005]of int64;
procedure qsort(l,r:longint);
var
    i,j,mid1,mid2:longint;
begin
    i:=l;
    j:=r;
    mid1:=b[(i+j) div 2,1];
    mid2:=b[(i+j) div 2,2];
    repeat
        while (b[i,1]or ((b[i,1]=mid1) and (b[i,2]do inc(i);
        while (b[j,1]>mid1) or ((b[j,1]=mid1) and (b[j,2]>mid2)) do dec(j);
        if i<=j then
        begin
            b[0]:=b[i];
            b[i]:=b[j];
            b[j]:=b[0];
            inc(i);
            dec(j);
        end;
    until i>j;
    if ithen qsort(i,r);
    if lthen qsort(l,j);
end;
procedure qsort1(l,r:longint);
var
    i,j,mid:longint;
begin
    i:=l;
    j:=r;
    mid:=b[(i+j) div 2,2];
    repeat
        while b[i,2]do inc(i);
        while b[j,2]>mid do dec(j);
        if i<=j then
        begin
            b[0]:=b[i];
            b[i]:=b[j];
            b[j]:=b[0];
            inc(i);
            dec(j);
        end;
    until i>j;
    if ithen qsort(i,r);
    if lthen qsort(l,j);
end;
procedure change(p,x,y:longint);
var
    j:longint;
begin
    if xthen
    begin
        for j:=x to y-1 do
        begin
            dec(s[a[j]]);
            dec(ans[p],s[a[j]]);
        end;
    end else
    if x>y then
    begin
        for j:=y to x-1 do
        begin
            inc(ans[p],s[a[j]]);
            inc(s[a[j]]);
        end;
    end;
end;
procedure change1(p,x,y:longint);
var
    j:longint;
begin
    if xthen
    begin
        for j:=x+1 to y do
        begin
            inc(ans[p],s[a[j]]);
            inc(s[a[j]]);
        end;
    end else
    if x>y then
    begin
        for j:=y+1 to x do
        begin
            dec(s[a[j]]);
            dec(ans[p],s[a[j]]);
        end;
    end;
end;
function gcd(x,y:int64):int64;
begin
    if y=0 then exit(x) else exit(gcd(y,x mod y));
end;
procedure init;
begin
    readln(n,m);
    for i:=1 to n do read(a[i]);
    readln;
    for i:=1 to m do
    begin
        readln(b[i,1],b[i,2]);
        b[i,3]:=i;
    end;
    qsort(1,m);
    t1:=trunc(sqrt(b[m,1]));
    b[m+1,1]:=t1+1;
    t2:=0;
    j:=1;
    p[0]:=0;
    while t2do
    begin
        inc(t2,t1);
        for i:=j to m do
        if (b[i-1,1]<=t2) and (b[i,1]>t2) then break;
        if b[i-1,1]=t2 then dec(i);
        if i>j then
        begin
            inc(k);
            p[k]:=i;
        end;
        j:=i;
    end;
end;
begin
    //assign(input,'1902.in'); reset(input);
    init;
    b[m+1,1]:=0;
    for i:=1 to k do qsort1(p[i-1]+1,p[i]);
    l:=1;
    r:=1;
    s[a[1]]:=1;
    for i:=1 to m do
    begin
        ans[i]:=ans[i-1];
        change(i,l,b[i,1]);
        change1(i,r,b[i,2]);
        l:=b[i,1];
        r:=b[i,2];
    end;
    for i:=1 to m do
    begin
        cy:=b[i,2]-b[i,1]+1;
        cy:=(cy*(cy-1)) div 2;
        if ans[i]=0 then cc[i]:=1 else
        begin
            l:=gcd(cy,ans[i]);
            cc[i]:=cy div l;
            ans[i]:=ans[i] div l;
        end;
    end;
    for i:=1 to m do
    begin
        a1[b[i,3]]:=ans[i];
        a2[b[i,3]]:=cc[i];
    end;
    for i:=1 to m do writeln(a1[i],'/',a2[i]);
    //close(input);
end.