데이터 구조 보고서

보고 용 은 이전 내용 과 좀 무 거울 수 있 으 니 양해 바 랍 니 다.)
선분 수 강하 차원
문득 크게 깨닫다.
총 커버 면적 을 구하 기 위해 사각형 의 위치 와 크기 를 보 여 줍 니 다.설명도
해법: 한 방향 을 스캐닝 라인 으로 한다.다른 방향 좌 표 는 이산 화 되 었 다.스캐닝 라인 을 위로 그 어 구간 을 순서대로 업데이트 합 니 다.
메모: 모든 변수의 의 미 를 정의 합 니 다.cover 는 한 구간 이 완전히 덮 였 을 때 몇 무 게 를 계산 했다.하위 구간 은 부모 구간 의 무 게 를 계승 하지 않 아 도 됩 니 다. 그렇지 않 으 면 업데이트 중 오류 가 발생 할 수 있 습 니 다!(이 구 덩이 는 하루 동안) has 는 하나의 구간 으로 전혀 덮어 쓰 지 않 았 습 니 다. 그렇지 않 으 면 가장자리 에 닿 으 면 1 로 설 치 됩 니 다. 하위 구간 has 가 1 일 때 부모 구간 has 는 반드시 1 입 니 다. 동시에 이 구간 cover > 0 일 때 has 는 반드시 1 입 니 다.

void update(int rt, int beg, int end, int l, int r, int flag)
{
    if(l > r || end < l || r < beg) return;
    if(l <= beg && end <= r)
    {
        cover[rt] += flag;
        if(beg == end)
            has[rt] = cover[rt] ? 1 : 0;
        else
            has[rt] = cover[rt]||has[rt<<1]||has[rt<<1|1] ? 1 : 0;
        return;
    }
    int mid = beg + end >> 1;
    update(rt<<1, beg, mid, l, min(r, mid), flag);
    update(rt<<1|1, mid+1, end, max(mid+1, l), r, flag);
    has[rt] = cover[rt]||has[rt<<1]||has[rt<<1|1] ? 1 : 0;
}

double query(int rt, int l, int r)
{
    if(!has[rt])
        return 0;
    if(cover[rt])
        return a[r+1]-a[l];
    int mid = l+r >> 1;
    return query(rt<<1, l, mid) + 
    query(rt<<1|1, mid+1, r);
}

또 다른 유사 한 문제.
사각형 의 위치 와 크기 를 보 여 주 며 덮어 쓰 는 둘레 를 구 합 니 다.
병 찰 집
더 이상 rank 으로 문 제 를 풀 지 마 세 요!벡터 와 유사 하여 매번 상대 값 을 기록 합 니 다.

int get(int a){
    if(p[a] != a) p[a] = get(p[a]);
    return p[a];
}

get 작업 을 거 친 후에 a 점 은 소속 단의 단장 을 가리 키 며 경로 의 화살 표를 압축 했다.
쌓 인 모형
처음에는 n 개의 사각형 이 었 다.다음 과 같은 두 가지 조작 이 있다. 1. x 와 이하 의 사각형 을 Y 가 있 는 더미 에 올 려 놓는다.2. x 가 있 는 더미 에 모두 몇 개의 사각형 이 있 는 지 물 어보 세 요.
해법: 합 리 적 인 구 조 는 구 해 에 도움 이 된다.이동 할 때마다 맨 아래 에 쌓 인 나 무 를 단장 으로 한다.p [i]: i 가 쌓 인 단장 은 처음에 i a [i]: i 밑 에 몇 개의 블록 이 있 는 지, 처음에 0 s [i]: i 가 단장 일 때 이 쌓 인 나무의 총 수 를 나타 낸다. 처음에 1 이 될 때마다 get 의 값 을 업데이트 하고 a [i] 가 i 의 지인 을 위해 새로운 단장 의 체인 에 있 는 a [j] 의 합 을 나타 내 며 새로운 단장 을 포함 하지 않 는 다."이 사슬 에는 i, 연대장, 새 단장 만 있 기 때문에 j 가 연대장 이라는 것 입 니 다." 맞 습 니까?

int get(int x){
    if(p[x] != x){
        a[x] += a[p[x]];
        p[x] = get(p[x]);
    }
    return p[x];
}

사실, 여러 번 merge 는 긴 사슬 을 만 들 수 있 습 니 다. 위의 표기 법 은 잘못된 것 입 니 다!비교적 좋 은 귀속 표기 법 은 다음 과 같다.

int get(int x){
    if(p[x] != x){
        int t = get(p[x]);
        a[x] += a[p[x]];
        p[x] = t;
    }
    return p[x];
}

잃 어 버 릴 뻔 했 습 니 다. 선후 순 서 는 p [x] 가 선행 처리 되 었 고 a [p [x] 값 이 바 뀌 었 습 니 다.쓰 지 못 하면 좀 더 어 리 석 은 방법 은 다음 과 같다.

int get(int x){
    if(p[x] != x){
        int t = get(p[x]), y = x;
        while(p[y] != t){
            a[x] += a[p[y]];
            y = p[y];
        }
        p[x] = t;
    }
    return p[x];
}

언뜻 보기 에는 결코 수집 한 것 같 지 않다
n 개의 물품 이 곧 기한 이 지나 서 원가 와 기한 이 지나 면 가 치 는 0 이다.가장 좋 은 판매 안 배 를 구하 여 물품 의 가치 와 최대 로 하 다.
해법: 첫 번 째 키워드: 가치 두 번 째 키워드: 날짜 정렬 매번 들 어 가 는 아 이 템 이 넣 고 싶 은 위치 가 설정 되 어 있 으 면 이 라인 의 맨 왼쪽 에 만 놓 을 수 있 습 니 다.
거짓말 아니에요.
n. 개인 이 n 마디 를 했 는데 진실 일 수도 있 고 거짓 일 수도 있 습 니 다.서로 모 순 될 때 Inconsistent 를 출력 합 니 다.그렇지 않 으 면 최대 몇 명 이 진실 을 말 했다.
해법: x 는 'y 가 진실 을 말 했다' 고 말 하면 x 와 y 는 진실 과 거짓 이다.그렇지 않 으 면 x 와 y 는 진위 가 다르다.'x 는 진실 을 말 했다' 와 'x 는 거짓말 을 했다' 는 두 가지 상황 이 서로 대칭 되 기 때문에 모든 사람 이 x 에 대한 진 위 를 제시 하면 된다.
팀 구성 방안
서로 아 는 사람 만 팀 을 구성 할 수 있다.모 두 를 두 팀 으로 나 누 어 각각 x 와 y 로 나눈다.x 와 y 의 차 이 를 최소 화 하 는 팀 구성 방안 을 구하 십시오.
해법: 서로 모 르 는 사람 은 관 계 를 맺 을 수 있다.여러 개의 단 체 를 만들다.DP 해 야 지!
지속 가능
이동 나무 블록 에서 3: x 를 한 무더기 에서 삭제 합 니 다.
해법: 번 호 를 다시 만 들 고 위 지 속 됩 니 다.
K 번 째 동작 으로 돌아 갈 때의 상황 은?