2 条题解
-
0
#include<bits/stdc++.h> #define lc(p) (p<<1) #define rc(p) (p<<1|1) #define LL long long using namespace std; const int N=1e5+10; struct Line{LL p,st,ed,flg; }L[N];// 一条竖线:x坐标是p,y的范围是st至ed bool cmp(Line n1,Line n2){return n1.p<n2.p;} LL lsh[N]; struct trnode{int l,r,c;LL len;}tr[N<<3]; void pushup(int p) { if(tr[p].c>0) tr[p].len=lsh[tr[p].r]-lsh[tr[p].l]; else tr[p].len=tr[lc(p)].len+tr[rc(p)].len ; } void bt(int p,int l,int r) { tr[p]=trnode{l,r,0,0}; if(l+1==r)return ; int m=(l+r)>>1; bt(lc(p),l,m);bt(rc(p),m,r); } void change(int p,int l,int r,int c) { if(r<=lsh[tr[p].l] || lsh[tr[p].r]<=l)return; if(l<=lsh[tr[p].l] && lsh[tr[p].r]<=r) { tr[p].c+=c; pushup(p); return ; } change(lc(p),l,r,c),change(rc(p),l,r,c); pushup(p); } int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { LL X1,Y1,X2,Y2;scanf("%lld%lld%lld",&X1,&X2,&Y2);Y1=0; L[i] =Line{X1,Y1,Y2, 1}; L[n+i]=Line{X2,Y1,Y2,-1}; lsh[i]=Y1,lsh[n+i]=Y2; } sort(lsh+1,lsh+2*n+1);int ln=unique(lsh+1,lsh+2*n+1)-lsh-1; bt(1,1,ln); sort(L+1,L+2*n+1,cmp); LL ans=0; for(int i=1;i<2*n;i++) { change(1,L[i].st,L[i].ed,L[i].flg); ans+=(L[i+1].p-L[i].p)*tr[1].len; } printf("%lld\n",ans); return 0; } -
0
#include<bits/stdc++.h> #define lc(p) (p<<1) #define rc(p) (p<<1|1) #define LL long long using namespace std; const int N=1e5+10; struct Line{LL p,st,ed,flg; }L[N];// 一条竖线:x坐标是p,y的范围是st至ed bool cmp(Line n1,Line n2){return n1.p<n2.p;} LL lsh[N]; struct trnode{int l,r,c;LL len;}tr[N<<3]; void pushup(int p) { if(tr[p].c>0) tr[p].len=lsh[tr[p].r]-lsh[tr[p].l]; else tr[p].len=tr[lc(p)].len+tr[rc(p)].len ; } void bt(int p,int l,int r) { tr[p]=trnode{l,r,0,0}; if(l+1==r)return ; int m=(l+r)>>1; bt(lc(p),l,m);bt(rc(p),m,r); } void change(int p,int l,int r,int c) { if(r<=lsh[tr[p].l] || lsh[tr[p].r]<=l)return; if(l<=lsh[tr[p].l] && lsh[tr[p].r]<=r) { tr[p].c+=c; pushup(p); return ; } change(lc(p),l,r,c),change(rc(p),l,r,c); pushup(p); } int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { LL X1,Y1,X2,Y2;scanf("%lld%lld%lld",&X1,&X2,&Y2);Y1=0; L[i] =Line{X1,Y1,Y2, 1}; L[n+i]=Line{X2,Y1,Y2,-1}; lsh[i]=Y1,lsh[n+i]=Y2; } sort(lsh+1,lsh+2*n+1);int ln=unique(lsh+1,lsh+2*n+1)-lsh-1; bt(1,1,ln); sort(L+1,L+2*n+1,cmp); LL ans=0; for(int i=1;i<2*n;i++) { change(1,L[i].st,L[i].ed,L[i].flg); ans+=(L[i+1].p-L[i].p)*tr[1].len; } printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 300
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 162
- 已通过
- 50
- 上传者