POJ 2352 Stars(treap 연습)
2156 단어 tar
제목:평면 상의 점 을 제시 하고 각 점 의 level 값 은 왼쪽 아래 점 의 개수(정 하와 왼쪽 포함)입 니 다.출력 level 값 이[0,n-1]에 있 는 점 은 각각 몇 개 입 니까?
사고방식:제시 한 점 은 y 의 오름차 순 에 따라 x 의 오름차 순 이기 때문에 x 를 treap 에 삽입 하고 매번 왼쪽 나무의 노드 개 수 를 통계 한다.
struct node
{
int L,R,key,pri,cntL,cntR;
};
class treap
{
public:
node p[N];
int size,root;
void init()
{
srand(time(0));
size=root=-1;
}
void rotL(int &x)
{
int y=p[x].R;
p[x].R=p[y].L;
p[x].cntR=p[y].cntL;
p[y].L=x;
p[y].cntL=p[x].cntL+p[x].cntR+1;
x=y;
}
void rotR(int &x)
{
int y=p[x].L;
p[x].L=p[y].R;
p[x].cntL=p[y].cntR;
p[y].R=x;
p[y].cntR=p[x].cntL+p[x].cntR+1;
x=y;
}
void insert(int &k,int key)
{
if(k==-1)
{
k=++size;
p[k].L=p[k].R=-1;
p[k].cntL=p[k].cntR=0;
p[k].key=key;
p[k].pri=rand();
}
else if(key<p[k].key)
{
p[k].cntL++;
insert(p[k].L,key);
if(p[p[k].L].pri>p[k].pri) rotR(k);
}
else
{
p[k].cntR++;
insert(p[k].R,key);
if(p[p[k].R].pri>p[k].pri) rotL(k);
}
}
int find(int k,int key)
{
if(k==-1) return 0;
if(key<p[k].key) return find(p[k].L,key);
return p[k].cntL+1+find(p[k].R,key);
}
};
struct point
{
int x,y;
void get()
{
RD(x,y);
}
};
point p[N];
treap a;
int n,ans[N];
int main()
{
Rush(n)
{
a.init(); clr(ans,0);
int i;
FOR0(i,n) p[i].get();
FOR0(i,n)
{
a.insert(a.root,p[i].x);
ans[a.find(a.root,p[i].x)-1]++;
}
FOR0(i,n) PR(ans[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LinuC 합격 1주만에 LPIC 기초 학습이 가능한 책 3일차 총결산gzip을 통한 압축 gunzip을 통한 동결 해제 zip을 통한 압축 unzip 동결해제 데이터 아카이빙 데이터를 통한 아카이빙 데이터 압축 아카이빙 데이터 압축 압축 압축 해제 사용자 추가 ※ su 환경 변수를 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
