BZOJ 3781 작은 B 의 문의 서열 모 팀 알고리즘
방법: 시퀀스 모 팀 알고리즘
왜 모 팀 을 사용 합 니까?
고 급 스 러 운 폭력 이 야.
이 문제 에 대해 복잡 도 를 간단하게 생각해 봅 시다.
폭력 이 라면 바로 N ^ 2, T 가 죽는다.
그래서 폭력 을 최적화 시 키 는 거 야.
우리 가 l, r 를 정렬 하면 좀 나 을 것 같은 데?
하지만 이 정도 면 T 다. 분명히 데 이 터 를 걸 고 하 는 짓 이기 때문이다.
우 리 는 데이터 범 위 를 관찰 합 니 다. 50000. 먼저 고급 점 의 폭력 - 모 팀 이 넘 을 수 있 는 지 없 는 지 를 고려 하고 복잡 도 O (n √ n) 를 계산 합 니 다.차이 가 많 지 않 습 니까?
매번 변 경 된 답 을 다시 봅 시다: O1
그럼 바로 막 대 에 올 라 가세 요.
우 리 는 모든 질문 을 오프라인 으로 하고 모든 질문 에 대해 왼쪽 끝 점 이 있 는 블록 에 따라 첫 번 째 키워드 이 고 오른쪽 끝 점 은 두 번 째 키워드 로 정렬 합 니 다.
이렇게 되면 매번 에 업 데 이 트 를 할 때 왼쪽 점 이 같은 부분 에서 묻 는 것 에 대해 오른쪽 점 은 점점 증가 하 는 것 이다. 즉, 우 리 는 최대 n 번 오른쪽 점 을 매 거 하 는 것 이 고 동시에 블록의 크기 는 √ n 이기 때문에 오른쪽 지침 은 최대 n √ n 번 을 매 거 했 고 왼쪽 점 에서 이동 하 는 것 은 √ n 등급 이 며 m 와 n 의 같은 단 계 를 물 었 다.그래서 왼쪽 끝 점 의 매 거 도 n √ n 등급 이다. 그러면 전체적인 복잡 도 는 n √ n 등급 이 고 이런 말 은 바로 지나 간다.
그리고 이 문제 의 업데이트 부분 에 대해 서 는 원래 의 것 을 빼 고 수량 을 업데이트 한 다음 에 현재 의 것 을 더 합 니 다.O1
코드:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50010
using namespace std;
int c[N];
int s[N];
int print[N];
int n,m,k;
int ans;
struct node
{
int blockl,l,r,no;
}que[N];
int cmp(node a,node b)
{
if(a.blockl==b.blockl)return a.r<b.r;
else return a.blockl<b.blockl;
}
void update(int v,int co)
{
ans-=s[co]*s[co];
s[co]+=v;
ans+=s[co]*s[co];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int sqrn=(int)sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&que[i].l,&que[i].r);
int tmp=0;
tmp+=que[i].l/sqrn;
if(que[i].l%sqrn!=0)tmp++;
que[i].blockl=tmp;
que[i].no=i;
}
sort(que+1,que+m+1,cmp);
int tl=que[1].l,tr=que[1].r;
for(int i=tl;i<=tr;i++)
{
update(1,c[i]);
}
print[que[1].no]=ans;
for(int i=2;i<=m;i++)
{
while(que[i].l<tl)tl--,update(1,c[tl]);
while(que[i].l>tl)update(-1,c[tl]),tl++;
while(que[i].r<tr)update(-1,c[tr]),tr--;
while(que[i].r>tr)tr++,update(1,c[tr]);
print[que[i].no]=ans;
}
for(int i=1;i<=m;i++)printf("%d
",print[i]);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
