Kilave Krave

시간 제한5초메모리 제한1024 MB

요약
큰 격자에 직사각형 울타리가 주어질 때, 각 소가 아래나 오른쪽으로만 이동하며 울타리를 넘지 않고 방문할 수 있는 데이지를 센다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 정렬, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

Obližnji pašnjak možemo predstaviti pravokutnom pločom koja se sastoji od 10610^6 redaka i 10610^6 stupaca. Retci su numerirani brojevima od 11 do 10610^6 odozgo prema dolje, dok su stupci numerirani brojevima od 11 do 10610^6 slijeva nadesno.

Krdo od nn krava nalazi se pašnjaku i to tako da se svaka krava nalazi u nekom jediničnom kvadratu. Na pašnjaku se također nalazi i mm tratinčica koje se također nalaze u jediničnim kvadratima. Konačno, na pašnjaku se nalazi i ff pravokutnih ograda čije se stranice protežu rubovima jediničnih kvadrata. Ograde se ne sijeku niti se diraju, međutim ograda se može u potpunosti nalaziti unutar područja koje ograđuje neka druga ograda.

Sve su krave kilave te se mogu kretati samo u dva smjera – dolje ili desno. Na svojim putovanjima mogu stati na bilo koje polje (uključujući i ona na kojima su druge krave ili tratinčice), ali ne mogu prelaziti preko ograde.

Za svaku kravu, odredite ukupan broj tratinčica koje ta krava može posjetiti šetnjom iz svoje početne pozicije.

입력

U prvom je retku cijeli broj ff (0≤f≤200,0000 ≤ f ≤ 200\\,000) iz teksta zadatka.

U svakom od sljedećih ff redaka su prirodni brojevi r_1r\_1, c_1c\_1, r_2r\_2, c_2c\_2 (1≤r_1,c_1,r_2,c_2≤1061 ≤ r\_1, c\_1, r\_2, c\_2 ≤ 10^6) koji opisuju jednu ogradu. Preciznije, (r_1,c_1)(r\_1, c\_1) su koordinate (red i stupac) gornjeg-lijevog jediničnog kvadrata unutar ograde, dok su (r_2,c_2)(r\_2, c\_2) koordinate donjeg-desnog jediničnog kvadrata unutar ograde. Niti jedne dvije ograde se ne sijeku niti diraju.

U sljedećem je retku cijeli broj mm (0≤m≤200,0000 ≤ m ≤ 200\\,000) iz teksta zadatka.

U kk-tom od idućih mm redaka nalaze se prirodni brojevi rr i cc (1≤r,c≤1061 ≤ r, c ≤ 10^6) koji redom predstavljaju redak i stupac u kojem se nalazi kk-ta tratinčica. Dvije tratinčice nikad se neće nalaziti na istoj lokaciji.

U sljedećem je retku cijeli broj nn (0≤n≤200,0000 ≤ n ≤ 200\\,000) iz teksta zadatka.

U kk-tom od idućih nn redaka nalaze se prirodni brojevi rr i cc (1≤r,c≤1061 ≤ r, c ≤ 10^6) koji redom predstavljaju redak i stupac u kojem se nalazi kk-ta krava. Dvije krave nikad se neće nalaziti na istoj lokaciji, niti će se neka krava nalaziti na lokaciji na kojoj se nalazi tratinčica.

출력

U kk-tom retku izlaza treba ispisati jedan cijeli broj – ukupan broj tratinčica koje kk-ta krava iz ulaza može posjetiti šetnjom iz svoje pozicije.

힌트

예제1

  1. 예제 1

    입력
    4
2 2 8 4
1 9 4 10
6 7 9 9
3 3 7 3
9
3 4
8 4
11 5
10 7
10 8
9 8
2 8
4 11
9 11
8
1 1
5 10
6 9
3 7
7 1
4 2
7 5
3 3
    예상 출력
    5
1
0
1
3
1
3
0