今天七夕,有没有人陪我调离散化+线段树/se
查看原帖
今天七夕,有没有人陪我调离散化+线段树/se
646208
Hughpig楼主2025/8/29 18:23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define up(l,r,i) for(int i=(l);(i)<=(r);++i)
#define pb push_back
#define all(x) x.begin(),x.end()

void ios_optimize(){ios::sync_with_stdio(0);cin.tie(0);}
ll ls(ll u){return u<<1;}
ll rs(ll u){return u<<1|1;}

constexpr int N=1e7+9;

ll n,X,Y,ans;

struct seg{
    ll x,y,l;
    friend bool operator <(seg a,seg b){
        return a.y>b.y;
    }
}a[N];

vector<long double> v,p;

int tr[N*4],tag[N*4];

void pushup(int u){
    tr[u]=min(tr[ls(u)],tr[rs(u)]);
}

void build(int u,int l,int r){
    tag[u]=0;tr[u]=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(u);
}

void pushdown(int u){
    if(tag[u]){
        tag[ls(u)]=tag[rs(u)]=1;
        tr[ls(u)]=tr[rs(u)]=1;
        tag[u]=0;
    }
}

void update(int u,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        tr[u]=1;tag[u]=1;
        return;
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(L<=mid) update(ls(u),l,mid,L,R);
    if(R>mid) update(rs(u),mid+1,r,L,R);
    pushup(u);
}

bool query(int u,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tr[u];
    pushdown(u);
    int mid=(l+r)>>1;
    bool res=1;
    if(L<=mid) res&=query(ls(u),l,mid,L,R);
    if(R>mid) res&=query(rs(u),mid+1,r,L,R);
    return res;
}

int main()
{
    cin>>n>>X>>Y;
    up(1,n,i){
        cin>>a[i].x>>a[i].y>>a[i].l;
    }
    sort(a+1,a+n+1);
    up(1,n,i){
        v.pb((long double)(a[i].x-X)/(long double)(Y-a[i].y));
        v.pb((long double)(a[i].x+a[i].l-X)/(long double)(Y-a[i].y));
    }
    p=v;sort(all(p));
    p.erase(unique(all(p)),p.end());
    for(auto &x:v)x=lower_bound(all(p),x)-p.begin()+1;
    build(1,1,n*2);
    up(1,n,i){
        int l=v[(i-1)*2],r=v[(i-1)*2+1];
        if(!query(1,1,n*2,l,r)){
            ++ans;
            update(1,1,n*2,l,r);
        }
    }
    cout<<ans;
	return 0;
}

2025/8/29 18:23
加载中...