[BZOJ 2038] 작은 Z 의 양말 (2009 국가 대표 훈련 팀) - 모 팀 알고리즘

테스트 주소: 작은 Z 양말
방법: f (i) 를 색상 i 로 구간 [l, r] 에 나타 나 는 횟수 로 설정 하면 구간 [l, r] 의 답 은:ΣC (2, f (i) / C (2, r - l + 1), 이런 물건 에 직면 하면 선분 수 는 어 쩔 수 없 는데.....................................................
그래서 저 는 오늘 전설 속 오프라인 처리 구간 에서 묻 는 무적 알고리즘 인 모 팀 알고리즘 을 배 웠 습 니 다. 느낌 이 아주 좋 습 니 다!모 팀 알고리즘 에 대한 설명 은 여기 있 습 니 다.이 블 로그 에서 도 이 문 제 를 예 로 들 어 상세 하 게 말 했 습 니 다. 그럼 구체 적 으로 실현 하 겠 습 니 다. 답 의 형식 중 대부분 은 l 과 r 를 통 해 직접 구 할 수 있 기 때문에 우 리 는 하나의 ans 만 유지 합 니 다 =Σ(f (i) ^ 2, (l, r) 에서 (l, r + 1) 로 옮 길 때 r + 1 의 색 이 c 라 고 가정 하면 ans 는 원래 보다 많다. (f (c) + 1) ^ 2 - f (c) ^ 2 = 2 * f (c) + 1.한편, (l, r) 에서 (l, r - 1) 로 옮 길 때 약간 다 릅 니 다. ans 는 원래 보다 많 습 니 다. (f (c) - 1) ^ 2 - f (c) ^ 2 = - 2 * f (c) + 1.그래서 우리 가 이동 하 는 구간 이 확 대 될 때 ans 가 증가 하 는 것 은 2 * f (c) + 1 이 고 반대로 - 2 * f (c) + 1 이다. 그리고 답 은 위의 블 로그 가 말 한 것 처럼 계산 하면 된다.가장 간단 한 점수 로 변 하 는 것 은 분자 와 분모 가 그들 을 제외 한 gcd 이다.
다음은 본인 코드 입 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m,c[50010],pos[50010],f[50010]={0};
struct query
{
  long long a,b;
  int l,r,id;
}q[50010];

bool cmp1(query a,query b)
{
  return pos[a.l]q[i].l) l--,transfer(l,ans,1);
	if (r>q[i].r) while(r>q[i].r) transfer(r,ans,-1),r--;
	if (q[i].l>l) while(l