3 条题解

  • 1
    @ 2025-11-24 20:24:09

    直接求范围内的点不好求,所以考虑换种思路:求不在范围内的点,用三角形三边所在直线将平面分割
    设查询为 X,Y,DX,Y,D
    红色区域内点集可表示为 {(x,y)x<X}\{(x,y)|x<X\}
    黄色区域内点集可表示为 {(x,y)y<Y}\{(x,y)|y<Y\}
    蓝色区域内点集可表示为 {(x,y)x+y>X+Y+D}\{(x,y)|x+y>X+Y+D\}(此处涉及高中数学直线一般式,但是可以通过看图理解)
    因此,根据容斥定理,可以得出

    答案=总数红色黄色蓝色+红色黄色+红色蓝色+黄色蓝色答案=总数-红色-黄色-蓝色+红色\cap黄色+红色\cap蓝色+黄色\cap蓝色

    其中单色区域较为好求,排序后双指针或二分均可 对于不同色块的交集,二维数点即可

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef array<int,4> ARR;
    typedef pair<int,int> PII;
    const int N = 1e6 + 5;
    int n,q,ans[N];
    ARR a[N],p[N];
    bool cmpx(ARR a,ARR b) { return a[0] < b[0];}
    bool cmpy(ARR a,ARR b) { return a[1] < b[1];}
    bool cmpl(ARR a,ARR b) { return a[2] > b[2];}
    struct BIT {
    	int tr[N];
    	void add(int x) {
    		for(;x < N;x += x & -x) tr[x] ++;
    	}
    	int ask(int x) {
    		int ans = 0;
    		for(;x;x -= x & -x) ans += tr[x];
    		return ans;
    	}
    } tr[3];
    void solve() {
    	cin >> n >> q;
    	for(int i = 1;i <= n;i ++) {
    		cin >> a[i][0] >> a[i][1];
    		a[i][2] = a[i][0] + a[i][1];
    	}
    	for(int i = 1;i <= q;i ++) {
    		cin >> p[i][0] >> p[i][1] >> p[i][2];
    		p[i][2] += p[i][0] + p[i][1];
    		ans[p[i][3] = i] = n;
    	}
    	sort(a + 1,a + n + 1,cmpx);
    	sort(p + 1,p + q + 1,cmpx);
    	for(int i = 1,j = 0;i <= q;i ++) {
    		while(j < n && a[j + 1][0] < p[i][0]) {
    			tr[0].add(a[++ j][1]);
    		}
    		ans[p[i][3]] -= j;// x < X
    		ans[p[i][3]] += tr[0].ask(p[i][1] - 1);// x < X && y < Y
    	}
    	sort(a + 1,a + n + 1,cmpy);
    	sort(p + 1,p + q + 1,cmpy);
    	for(int i = 1,j = 0;i <= q;i ++) {
    		while(j < n && a[j + 1][1] < p[i][1]) j ++;
    		ans[p[i][3]] -= j;// y < Y
    	}
    	sort(a + 1,a + n + 1,cmpl);
    	sort(p + 1,p + q + 1,cmpl);
    	for(int i = 1,j = 0;i <= q;i ++) {
    		while(j < n && a[j + 1][2] > p[i][2]) {
    			j ++;
    			tr[1].add(a[j][0]);
    			tr[2].add(a[j][1]);
    		}
    		ans[p[i][3]] -= j;// x + y > X + Y + D
    		ans[p[i][3]] += tr[1].ask(p[i][0] - 1);// x < X && x + y > X + Y + D
    		ans[p[i][3]] += tr[2].ask(p[i][1] - 1);// y < Y && x + y > X + Y + D
    	}
    	for(int i = 1;i <= q;i ++) {
    		cout << ans[i] << "\n";
    	}
    }
    signed main() {
    	freopen("triangular.in","r",stdin);
    	freopen("triangular.out","w",stdout);
    	ios::sync_with_stdio(0);
    	cin.tie(0),cout.tie(0);
    	int t = 1;
    //	cin >> t;
    	while(t --) solve();
    	return 0;
    }
    

    信息

    ID
    28
    时间
    5000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    57
    已通过
    7
    上传者