데이터 구조의 - 선분 트 리 (2)
1. 직사각형 면적 합.POJ1389 / HDU1542
제목: 사각형 면적 은 n 개의 사각형 (변 은 모두 x 축 이나 y 축) 을 제시 합 니 다. 이런 사각형 은 서로 겹 쳐 서 전체적인 커버 면적 을 구 할 수 있 습 니 다.
분석: 그림 을 그리고 관찰 한 결과 x 축 방향 에서 이런 사각형 을 스 캔 한 결과 앞 변 의 중합 (유효) 길 이 를 기록 해 야 한 다 는 것 을 발견 했다. 예 를 들 어 두 개의 변 이 있 는데 각각 [2, 4], [3, 8] 이 고 그들의 유효 길 이 는 6 이다.직사각형의 왼쪽 (입 변) 은 1 이 고 오른쪽 (출 변) 은 - 1 이다.이제 이 선분 들 의 유효한 길 이 를 어떻게 유지 해 야 합 니까?삽입 과 삭 제 는 모두 logn 단계 이기 때문에 선분 트 리 로 유지 할 수 있 습 니 다.
해: a. 점 y 좌표 의 오름차 순 서 를 정렬 하고 이산 화 하 며 무 게 를 제거 하 며 선분 수 를 구축 하고 잎 노드 구간 의 길 이 를 1 로 주의 하 세 요.
b. 스캐닝 라인 (사각형 의 좌우 변) 을 x 오름차 순 으로 정렬 하고 선분 트 리 에 순서대로 삽입 하여 유효 거 리 를 유지 합 니 다.
c. 면적 + = 전체 구간 의 유효 길이 * (다음 스캐닝 라인 의 x 좌표 - 본 라인 의 x 좌표).
효과 적 인 거 리 를 어떻게 유지 하 느 냐 가 이 문제 의 관건 임 을 알 수 있다.
간단 한 방법 은 매번 잎 노드 로 업데이트 되 지만 이렇게 하면 선분 나무의 장점 을 발휘 하지 못 하고 lazy 사상 을 사용 하지 않 는 다 는 것 이다.
두 개의 변 수 를 설정 할 수 있 습 니 다. len 은 이 구간 의 유효한 길 이 를 표시 합 니 다. cover 는 이 구간 이 완전히 덮어 쓰 였 는 지 여부 입 니 다 (0 은 완전히 덮어 쓰 이지 않 았 음 을 표시 합 니 다. > = 1 은 완전히 덮어 쓰 였 음 을 표시 합 니 다).cover > = 1 시, len = y [r] - y [l];그렇지 않 으 면 잎 노드 라면 len = 0;그렇지 않 으 면, len = len [l] + len [r].
실질: 구간 누적 + 통계 구간 유효 길이
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
const int N = 1005;
int yy[N*2],range; // y
struct Line
{
int x;
int y_up;
int y_down;
int cover; // 1, -1
}line[N*2];
struct Seg_Tree
{
int left;
int right;
int cover; // >=1, 0
int len; //
int calmid()
{
return (left+right)>>1;
}
}tree[N*8];
bool cmp(Line a, Line b)
{
return a.x < b.x;
}
void build(int left, int right, int idx)
{
tree[idx].left = left;
tree[idx].right = right;
tree[idx].cover = 0;
tree[idx].len = 0;
if(left+1==right)
return;
int mid = (left+right)>>1;
build(left,mid,LL(idx));
build(mid,right,RR(idx));
}
int BiSearch(int v)
{
int low = 0;
int high = range;
while(low<=high)
{
int mid = (low+high)>>1;
if(yy[mid]==v)
return mid;
if(yy[mid] < v)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
void updateLen(int i)
{
if(tree[i].cover)
tree[i].len = yy[tree[i].right] - yy[tree[i].left];
else if(tree[i].left + 1 == tree[i].right)
tree[i].len = 0;
else
tree[i].len = tree[LL(i)].len + tree[RR(i)].len;
}
// [a,b]
void update(int a, int b, int c, int idx)
{
if(tree[idx].left==a && tree[idx].right == b)
{
tree[idx].cover += c;
updateLen(idx);
return ;
}
int mid = tree[idx].calmid();
if(b <= mid)
update(a,b,c,LL(idx));
else if(a >= mid)
update(a,b,c,RR(idx));
else
{
update(a,mid,c,LL(idx));
update(mid,b,c,RR(idx));
}
updateLen(idx);
}
int main()
{
int i,j;
int x1,y1,x2,y2;
while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)!=EOF&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1)
{
i = 0;
do
{
line[i].x = x1;
line[i].y_down = y1;
line[i].y_up = y2;
line[i].cover = 1;
yy[i] = y1;
i++;
line[i].x = x2;
line[i].y_down = y1;
line[i].y_up = y2;
line[i].cover = -1;
yy[i] = y2;
i++;
}while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1);
sort(line,line+i,cmp);
sort(yy,yy+i);
range = 0;
for(j = 0; j < i; j++)
{
if(j==0||yy[j]!=yy[j-1])
yy[range++] = yy[j];
}
range--;
build(0,range,1);
int result = 0;
for(j = 0; j < i-1; j++)
{
int a = BiSearch(line[j].y_down);
int b = BiSearch(line[j].y_up);
update(a,b,line[j].cover,1);
result += tree[1].len*(line[j+1].x - line[j].x);
}
printf("%d
",result);
}
return 0;
}
/*
0 1 3 4
2 0 4 3
1 2 5 5
-1 -1 -1 -1
*/
2. 직사각형 면적 교차.HDU1255
직사각형 면적 과 유사 하 며 스캐너 + 선분 트 리 로 해답 을 구한다.여기에 두 개의 변 수 를 설정 해 야 합 니 다 onelen 과 morelen, 각각 덮어 쓰기 횟수 > = 1 번 의 길이 와 > = 2 번 의 길 이 를 나타 낸다.
만약 cover > = 2, onelen=more_len=y[r]-y[l];
cover = = 1, onelen=y[r]-y[l],more_len=one_len[l] + one_len[r];
만약 cover = = 0, onelen=one_len[l]+one_len[r],more_len=more_len[l]+more_len[r]。
void setLen(int idx)
{
int r = tree[idx].right;
int l = tree[idx].left;
if(tree[idx].cover > 1)
tree[idx].one_len = tree[idx].more_len = yy[r] - yy[l];
else if(tree[idx].cover == 1)
{
tree[idx].one_len = yy[r] - yy[l];
if(l+1 == r)
tree[idx].more_len = 0;
else
tree[idx].more_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;
}
else
{
if(l+1 == r)
tree[idx].one_len = tree[idx].one_len = 0;
else
{
tree[idx].one_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;
tree[idx].more_len = tree[LL(idx)].more_len + tree[RR(idx)].more_len;
}
}
}
3. 하나의 사각형 은 최대 몇 개의 점 을 표시 할 수 있 습 니까? (경계 점 은 계산 하지 않 습 니 다)POJ2482 / HDU4007
제목: 2 차원 평면 에 n 개의 점 이 있 는데 너비 가 w 높이 가 h 인 사각형 을 제시 합 니 다. 사각형 은 임의로 이동 할 수 있 습 니 다. 이 사각형 은 최대 몇 개의 점 을 틀 어 놓 을 수 있 는 지 물 어보 세 요.
분석: 이 문 제 는 생각 이 없 는 것 같 으 니 점 을 왼쪽 아래 의 정점 으로 하 는 w * h 의 사각형 으로 보 는 것 도 좋 습 니 다.직사각형 왼쪽 은 1 이 고 오른쪽 은 - 1 이다.약간 위 에 형식 같 지 않 아 요?사실 여 기 는 하나의 점 을 두 점 (x, y, 1) 과 (x + w, y, - 1) 으로 나 누 는 것 입 니 다. 그러면 우리 가 점 을 계속 삽입 할 때 사각형 이 왼쪽 에서 오른쪽으로 이동 하 는 것 과 같 습 니 다. 첫 번 째 점 의 총수 + 1 에 부 딪 히 면 이 점 을 틀 어 놓 은 것 과 같 습 니 다.두 번 째 점 에 부 딪 히 면 1 + (- 1) = 0 으로 테두리 가 없 는 것 과 같다.매번 삽입 할 때마다 x 가 고정 되 어 있 고 y 가 고정 되 어 있 지 않 기 때문에 이 점 이 y 축 에 영향 을 주 는 범 위 는 [y, y + h) 입 니 다. 여 기 는 개방 구간 입 니 다. 경계 점 이 포함 되 어 있 지 않 기 때문에 최대 치 를 기록 합 니 다.
관건 적 인 문제: 구간 누적 과 가장 값 있 는 유 지 를 어떻게 실현 합 니까? 두 변수 add 와 max: add 로 현재 가 한 수의 합 을 나타 내 고 max 는 이 구간 의 가장 값 을 기록 합 니 다. 업 데 이 트 를 할 때마다 현재 노드 add! = 0 이면 이 노드 의 add 값 을 좌우 아이들 노드 에 전달 하고 자신의 add 는 0 으로 다시 부 여 됩 니 다. 전체 구간 의 가장 값 은 좌우 아이들 구간 의 큰 자 입 니 다.
실질: 구간 누적 + 구간 최 값
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
typedef __int64 int64;
const int N = 10005;
int n,w,h;
struct Point
{
int64 x,y;
int64 v;
bool operator <(const Point &p) const
{
if(x != p.x)
return x < p.x;
return v < p.v;
}
}point[N*2];
int64 y[N*2];
struct Seg_Tree
{
int left;
int right;
int64 max; // max
int64 add; //
int calmid()
{
return (left+right)>>1;
}
}tt[N*8];
bool cmp(const int64& a, const int64& b)
{
return a < b;
}
int64 max(int64 a, int64 b)
{
return a > b ? a : b;
}
void build(int left, int right, int idx)
{
tt[idx].left = left;
tt[idx].right = right;
tt[idx].add = tt[idx].max = 0;
if(left == right)
return;
int mid = (left+right)>>1;
build(left,mid,LL(idx));
build(mid+1,right,RR(idx));
}
int BinSearch(int aim, int low, int high)
{
while(low <= high)
{
int mid = (low+high)>>1;
if(y[mid] == aim)
return mid;
if(y[mid] < aim)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
void update(int left, int right, int value, int idx)
{
if(tt[idx].left>=left&&tt[idx].right<=right)
{
tt[idx].add += value;
tt[idx].max += value;
return;
}
if(tt[idx].add != 0)
{
tt[LL(idx)].add += tt[idx].add;
tt[RR(idx)].add += tt[idx].add;
tt[LL(idx)].max += tt[idx].add;
tt[RR(idx)].max += tt[idx].add;
tt[idx].add = 0;
}
int mid = tt[idx].calmid();
if(left <= mid)
update(left,right,value,LL(idx));
if(right > mid)
update(left,right,value,RR(idx));
tt[idx].max = max(tt[LL(idx)].max, tt[RR(idx)].max);
}
int main()
{
int i;
while(scanf("%d %d %d",&n,&w,&h)!=EOF)
{
for(i = 0; i < n; i++)
{
scanf("%I64d %I64d %I64d",&point[i].x,&point[i].y,&point[i].v);
y[i] = point[i].y;
y[n+i] = point[i].y+h;
point[n+i].x = point[i].x+w;
point[n+i].y = point[i].y;
point[n+i].v = -point[i].v;
}
n = n<<1;
sort(y,y+n,cmp);
sort(point,point+n);
int k = 0;
//unique
for(i = 0; i < n; i++)
{
if(i==0 || y[i] != y[i-1])
y[k++] = y[i];
}
k--;
build(0,k,1);
int64 result = -1;
for(i = 0; i < n; i++)
{
int left = BinSearch(point[i].y, 0, k);
int right = BinSearch(point[i].y+h, 0, k) - 1; // [y,y+h)
if(left>right)
swap(left,right);
update(left,right,point[i].v,1);
if(result < tt[1].max)
result = tt[1].max;
}
printf("%I64d
",result);
}
return 0;
}
/*
3 5 3
2 2 3
3 1 5
4 -2 4
8
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.