LOJ#3030. 「JOISC 2019 Day1」考试

看起来求一个奇怪图形（两条和坐标轴平行的线被切掉了一个角）内包括的点个数

too naive！

首先熟练的转化求不被这个图形包含的个数

……

也不好求

我们把c转化成max(c,a + b)

就会发现这条斜线把不合法的刚好分成了三个部分，也就是第一门小于a的，总分大于c的，和第二门小于b的总分大于c的，和总分小于c的

你可以发现前两个部分是不相交的，于是开个树状数组把询问按c排序做一遍就好了，然后点集按s + t排序，小于c的就从所在的两个树状数组删掉

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,Q;

pii p[MAXN];

int val[MAXN * 2],tot,ans[MAXN];

struct qry_node {

    int a,b,c,id;

}qry[MAXN];

struct BIT {

    int tr[MAXN * 2],s;

    int lowbit(int x) {

	return x & (-x);

    }

    void insert(int x,int v) {

	while(x <= s) {

	    tr[x] += v;

	    x += lowbit(x);

	}

    }

    int query(int x) {

	int res = 0;

	while(x > 0) {

	    res += tr[x];

	    x -= lowbit(x);

	}

	return res;

    }

}tr[2];

int getid(int x) {

    return lower_bound(val + 1,val + tot + 1,x) - val;

}

void Solve() {

    read(N);read(Q);

    for(int i = 1 ; i <= N ; ++i) {

	read(p[i].fi);read(p[i].se);

	val[++tot] = p[i].fi;val[++tot] = p[i].se;

    }

    sort(val + 1,val + tot + 1);

    tot = unique(val + 1,val + tot + 1) - val - 1;

    tr[0].s = tr[1].s = tot;

    sort(p + 1,p + N + 1,[](pii a,pii b){return a.fi + a.se < b.fi + b.se;});

    for(int i = 1 ; i <= Q ; ++i) {

	read(qry[i].a);read(qry[i].b);read(qry[i].c);

	qry[i].c = max(qry[i].c,qry[i].a + qry[i].b);

	qry[i].id = i;

	ans[i] = N;

    }

    sort(qry + 1,qry + Q + 1,[](qry_node a,qry_node b){return a.c < b.c;});

    for(int i = 1 ; i <= N ; ++i) {

	tr[0].insert(getid(p[i].fi),1);

	tr[1].insert(getid(p[i].se),1);

    }

    int t = 0;

    for(int i = 1 ; i <= Q ; ++i) {

	while(t < N && p[t + 1].fi + p[t + 1].se < qry[i].c) {

	    ++t;

	    tr[0].insert(getid(p[t].fi),-1);

	    tr[1].insert(getid(p[t].se),-1);

	}

	ans[qry[i].id] -= t;

	ans[qry[i].id] -= tr[0].query(getid(qry[i].a) - 1);

	ans[qry[i].id] -= tr[1].query(getid(qry[i].b) - 1);

    }

    for(int i = 1 ; i <= Q ; ++i) {

	out(ans[i]);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}