# Cod sursa(job #613686)

Utilizator Data 3 octombrie 2011 23:36:13 Zoo 60 cpp done Arhiva de probleme 4.15 kb
``````#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 100005
#define x first
#define y second

vi arb[MAX_N << 2];
vi sqy[MAX_N << 2];

pii P[MAX_N];
int X1, X2, Y1, Y2, N, cost[MAX_N];
int vl[MAX_N], vr[MAX_N], tmp[MAX_N];
int RES;

void merge (int node, int li, int lf) {
arb[node].resize(lf - li + 1);
sqy[node].resize(lf - li + 1);

int sl = 2*node;
int sr = 2*node + 1;

arb[sl].pb(oo), arb[sr].pb(oo);

FOR (i, 0, sz(sqy[sl])) vl[i] = (i > 0) ? sqy[sl][i] - sqy[sl][i - 1] : sqy[sl][i];
FOR (i, 0, sz(sqy[sr])) vr[i] = (i > 0) ? sqy[sr][i] - sqy[sr][i - 1] : sqy[sr][i];

int i, j, k;
for (i = 0, j = 0, k = 0; k <= lf - li; ++k)
if (arb[sl][i] < arb[sr][j]) {
arb[node][k] = arb[sl][i];
tmp[k] = vl[i++];
}
else {
arb[node][k] = arb[sr][j];
tmp[k] = vr[j++];
}

sqy[node][0] = tmp[0];
FOR (i, 1, lf - li + 1) sqy[node][i]= sqy[node][i - 1] + tmp[i];
}

void buildtree (int node, int li, int lf) {
if (li == lf)  {
arb[node].clear();
sqy[node].clear();
arb[node].pb(P[li].y);
sqy[node].pb(cost[li]);
}
else {
int m = (li + lf) >> 1;
buildtree(2*node, li, m);
buildtree(2*node + 1, m + 1, lf);

merge(node, li, lf);
}
}

int summify (int node) {
if (arb[node][0] > Y2 || arb[node][sz(arb[node]) - 1] < Y1) return 0LL;

int li, lf, m, c1, c2;
li = 0, lf = sz(arb[node]) - 1;

while (li <= lf) {
m = (li + lf) >> 1;
if (arb[node][m] < Y1) li = m + 1;
else lf = m - 1;
}

while (m && arb[node][m - 1] >= Y1) --m;
while (arb[node][m] < Y1 && m < sz(arb[node]) - 1) ++m;
c1 = m;

li = 0, lf = sz(arb[node]) - 1;

while (li <= lf) {
m = (li + lf) >> 1;
if (arb[node][m] < Y2) li = m + 1;
else lf = m - 1;
}
while (m < sz(arb[node]) - 1 && arb[node][m + 1] <= Y2) ++m;
while (arb[node][m] > Y2 && m) --m;
c2 = m;

if (!c1)
return sqy[node][c2];
else
return sqy[node][c2] - sqy[node][c1 - 1];
}

void query (int node, int li, int lf) {
if (X1 <= P[li].x && P[lf].x <= X2)
RES += summify (node);
else
if (li != lf) {
int m = (li + lf) >> 1;

if (X1 <= P[m].x)
query(2*node, li, m);
if (P[m + 1].x <= X2)
query(2*node + 1, m + 1, lf);
}
}

int main () {
freopen ("zoo.in", "r", stdin);
freopen ("zoo.out", "w", stdout);

int tests = 1;
//    scanf ("%d", &tests);
while (tests--) {
scanf ("%d", &N);

FOR (i, 0, N) {
scanf ("%d %d", &P[i].x, &P[i].y);
cost[i] = 1;
}

sort (P, P + N);
buildtree(1, 0, N - 1);

int nq;
scanf ("%d", &nq);

FOR (i, 0, nq) {
scanf ("%d %d %d %d", &X1, &Y1, &X2, &Y2);

RES = 0;
query (1, 0, N - 1);

printf ("%d\n", RES);
}
}

return 0;
}
``````