JOISC 2019 Day1 T1 考试 题解

有个人每个人的属性可以用两个数字来表示

有组询问形如表示询问有多少人

空间比较小

显然本题有一个简单的三维偏序做法,不再赘述

考虑先计算出的人数然后再容斥掉的人数

怎么计算的人数呢

先算出的再减去的

至于正确性画个图你就知道了

以上所有内容都可以用二维数点实现复杂度

#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 200050,M = 200050;
int n,m;
int ans[M];
struct BIT{
    int d[N*3],n,r;
    inline void init(int nn){ n=nn;for (int i = 0; i <= n; ++i) d[i] = 0; }
    inline void add(int x){ while (x <= n) ++d[x],x+=x&-x; }
    inline int ask(int x){ r=0; while (x>0) r+=d[x],x-=x&-x; return r; }
}T;
struct Point{
    int x,y;
    Point(int xx=0,int yy=0){ x=xx,y=yy; }
    inline bool operator < (Point w) const{ return x > w.x; }
}p[N]; int cntp;
struct Ask{
    int id,f,x,y;
    Ask(int iid=0,int ff=0,int xx=0,int yy=00){ id=iid,f=ff,x=xx,y=yy; }
    inline bool operator < (Ask w) const{ return x > w.x; }
}ask[N<<1]; int cntq;

inline void solve(int Mx){
    int i,now = 1;
    T.init(Mx);
    sort(p+1,p+cntp+1); sort(ask+1,ask+cntq+1);
    for (i = 1; i <= cntq; ++i){
        while (now <= cntp && ask[i].x <= p[now].x) T.add(p[now].y),++now;
        ans[ask[i].id] += ask[i].f * (now - 1 - T.ask(ask[i].y-1));
    }
}
#define addq(idd,ff,vx,vy) ++cntq,ask[cntq].id = idd,ask[cntq].f = ff,ask[cntq].x = vx,ask[cntq].y = vy
#define addp(vx,vy) ++cntp,p[cntp].x = vx,p[cntp].y = vy
#define getpos(x) (int)(lower_bound(v+1,v+lv+1,x)-v)
LL v[N*3],lv;
int px[N],py[N];
int qx[M],qy[M],qz[M];
signed main(){
    int i;
    read(n),read(m);
    for (i = 1; i <= n; ++i) read(px[i]),read(py[i]);
    for (i = 1; i <= m; ++i) read(qx[i]),read(qy[i]),read(qz[i]);

    cntp = cntq = lv = 0;
    for (i = 1; i <= n; ++i) v[++lv] = py[i];
    for (i = 1; i <= m; ++i) v[++lv] = qy[i];
    sort(v+1,v+lv+1),lv = unique(v+1,v+lv+1)-v-1;
    for (i = 1; i <= n; ++i) addp(px[i],getpos(py[i]));
    for (i = 1; i <= m; ++i) addq(i,1,qx[i],getpos(qy[i]));
    solve(lv+5);

    cntp = cntq = 0;
    for (i = 1; i <= n; ++i) addp(px[i]+py[i],getpos(py[i]));
    int l1,r1,l2,r2;
    for (i = 1; i <= m; ++i) if (qz[i] > qx[i] + qy[i]){
        l1 = qx[i] + qy[i],r1 = qz[i];
        l2 = getpos(qy[i]);
        addq(i,-1,l1,l2);
        addq(i,1,r1,l2);
    }
    solve(lv+5);
    cntp = cntq = lv = 0;
    for (i = 1; i <= n; ++i) v[++lv] = px[i];
    for (i = 1; i <= m; ++i) if (qz[i] > qx[i] + qy[i]) v[++lv] = qx[i]-1;
    sort(v+1,v+lv+1),lv = unique(v+1,v+lv+1)-v-1;
    for (i = 1; i <= n; ++i) addp(px[i]+py[i],lv - getpos(px[i]) + 10);
    for (i = 1; i <= m; ++i) if (qz[i] > qx[i] + qy[i]){
        l1 = qx[i] + qy[i],r1 = qz[i];
        l2 = lv - getpos(qx[i]-1) + 10;
        addq(i,1,l1,l2);
        addq(i,-1,r1,l2);
    }
    solve(lv+50);

    for (i = 1; i <= m; ++i) write(ans[i]),putchar('\n');
    return 0;
}