[BZOJ3809] Gty의 2박 여동생 서열(모팀+블록)
제목 설명
전송문
문제풀이
모대+나무상수조의 사고방식은 매우 명확하지만 시간 O(mn√log2n) 모대+권치 블록을 나누는 방법이 비교적 우수하다.값을 블록으로 나누어 수정하면 O(1) 조회 O(n√)
코드
#include
#include
#include
#include
#include
using namespace std;
const int max_n=1e5+5;
const int max_m=1e6+5;
const int max_sqrt=350;
int n,m,t,num,ans;
int a[max_n],val[max_n],sum[max_sqrt];
struct hp{int l,r,a,b,id,final;}q[max_m];
inline int cmp(hp a,hp b){
int num1,num2;
if (a.l%t==0) num1=a.l/t; else num1=a.l/t+1;
if (b.l%t==0) num2=b.l/t; else num2=b.l/t+1;
return num1int ask(int l,int r){
int ans=0,k,lrange,rrange,numl,numr;
if (l%t==0) numl=l/t;
else numl=l/t+1;
if (r%t==0) numr=r/t;
else numr=r/t+1;
if (numl==numr){
for (int i=l;i<=r;++i)
if (val[i]) ans++;
return ans;
}
lrange=numl+1;
k=numl*t;
for (int i=l;i<=k;++i)
if (val[i]) ans++;
k=(numr-1)*t+1;
for (int i=k;i<=r;++i)
if (val[i]) ans++;
rrange=numr-1;
for (int i=lrange;i<=rrange;++i)
ans+=sum[i];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
t=(int)sqrt(n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i;
sort(q+1,q+m+1,cmp);
for (int i=q[1].l;i<=q[1].r;++i){
if (a[i]%t==0) num=a[i]/t; else num=a[i]/t+1;
++val[a[i]];
if (val[a[i]]==1) ++sum[num];
}
ans=ask(q[1].a,q[1].b);
q[q[1].id].final=ans;
for (int i=2;i<=m;++i){
if (q[i-1].l<q[i].l)
for (int j=q[i-1].l;j<q[i].l;++j){
if (a[j]%t==0) num=a[j]/t; else num=a[j]/t+1;
--val[a[j]];
if (!val[a[j]]) --sum[num];
}
if (q[i-1].l>q[i].l)
for (int j=q[i-1].l-1;j>=q[i].l;--j){
if (a[j]%t==0) num=a[j]/t; else num=a[j]/t+1;
++val[a[j]];
if (val[a[j]]==1) ++sum[num];
}
if (q[i-1].r<q[i].r)
for (int j=q[i-1].r+1;j<=q[i].r;++j){
if (a[j]%t==0) num=a[j]/t; else num=a[j]/t+1;
++val[a[j]];
if (val[a[j]]==1) ++sum[num];
}
if (q[i-1].r>q[i].r)
for (int j=q[i-1].r;j>q[i].r;--j){
if (a[j]%t==0) num=a[j]/t; else num=a[j]/t+1;
--val[a[j]];
if (!val[a[j]]) --sum[num];
}
ans=ask(q[i].a,q[i].b);
q[q[i].id].final=ans;
}
for (int i=1;i<=m;++i)
printf("%d
",q[i].final);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.