社区讨论
18pts AC on #1~#2 TLE on #3~#10求条(麻风良好)
P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhj3l3cj
- 此快照首次捕获于
- 2025/11/03 20:09 4 个月前
- 此快照最后确认于
- 2025/11/03 20:09 4 个月前
CPP
#include<bits/stdc++.h>
#define int long long
#define ls id<<1
#define rs id<<1|1
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<48){
if(c=='-') f=-1;
c=getchar();
}
while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
const int N=1e5+5;
int n,xx[2*N],yy[2*N],zhenx[2*N],zheny[2*N];
struct sw{
int x_1,y_1,x_2,y_2;
}a[2*N];
struct WS{
int l,r,op;
};
vector<WS> g[2*N];
struct note{
int l,r,tag,mx;
}tr[16*N];
inline void ADD(int id,int k){
tr[id].mx+=k;tr[id].tag+=k;
}
inline void pushdown(int id){
//printf("id=%lld\n",id);
ADD(ls,tr[id].tag);ADD(rs,tr[id].tag);
//printf("%lld += %lld\n",ls,tr[id].tag);
//printf("%lld += %lld\n",rs,tr[id].tag);
tr[id].tag=0;
}
inline void build(int id,int l,int r){
//printf("(%lld,%lld,%lld)\n",id,l,r);
//printf("[%lld,%lld]\n",l,r+1);
tr[id].l=l,tr[id].r=r,tr[id].tag=tr[id].mx=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
inline void update(int id,int l,int r,int k){
//printf("update[%lld,%lld],k=%lld\n",l,r+1,k);
if(l<=tr[id].l&&tr[id].r<=r){
//printf("[%lld,%lld] included\n",tr[id].l,tr[id].r+1);
ADD(id,k);
//printf("[%lld,%lld].mx:%lld\n",tr[id].l,tr[id].r+1,tr[id].mx);
return ;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(l<=mid){
//printf("go ls %lld\n",ls);
update(ls,l,r,k);
}
if(r>mid){
//printf("go rs %lld\n",rs);
update(rs,l,r,k);
}
tr[id].mx=max(tr[ls].mx,tr[rs].mx);
}
inline int query(int id,int l,int r){
if(!tr[id].l||!tr[id].r){
return 0;
}
//printf("id=%lld l=%lld r=%lld [%lld,%lld]\n",id,tr[id].l,tr[id].r,tr[id].l,tr[id].r+1);
if(tr[id].mx==0){
//printf("id=%lld (%lld,%lld) [%lld,%lld]\n",id,tr[id].l,tr[id].r,tr[id].l,tr[id].r+1);
//printf("[%lld,%lld] is empty\n",zhenx[tr[id].l],zhenx[tr[id].r+1]);
return zhenx[tr[id].r+1]-zhenx[tr[id].l];
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1,ans=0;
if(l<=mid) ans+=query(ls,l,r);
if(r>mid) ans+=query(rs,l,r);
return ans;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
a[i].x_1=read(),a[i].y_1=read(),a[i].x_2=read(),a[i].y_2=read();
xx[2*i-1]=a[i].x_1,xx[2*i]=a[i].x_2;yy[2*i-1]=a[i].y_1,yy[2*i]=a[i].y_2;
}
/*
for(int i=1;i<=2*n;i++){
printf("%lld ",xx[i]);
}
printf("\n");
for(int i=1;i<=2*n;i++){
printf("%lld ",yy[i]);
}
printf("\n");
*/
//cout<<"111"<<endl;
sort(xx+1,xx+2*n+1);sort(yy+1,yy+2*n+1);
int lenx=unique(xx+1,xx+2*n+1)-xx-1;
int leny=unique(yy+1,yy+2*n+1)-yy-1;
//cout<<"222"<<endl;
for(int i=1;i<=n;i++){
//cout<<"i="<<i<<endl;
int posx1=lower_bound(xx+1,xx+lenx+1,a[i].x_1)-xx;
int posx2=lower_bound(xx+1,xx+lenx+1,a[i].x_2)-xx;
int posy1=lower_bound(yy+1,yy+leny+1,a[i].y_1)-yy;
int posy2=lower_bound(yy+1,yy+leny+1,a[i].y_2)-yy;
//printf("(%lld,%lld)+(%lld,%lld)\n",posx1,posy1,posx2,posy2);
zhenx[posx1]=a[i].x_1;zhenx[posx2]=a[i].x_2;
zheny[posy1]=a[i].y_1;zheny[posy2]=a[i].y_2;
a[i].x_1=posx1,a[i].x_2=posx2,a[i].y_1=posy1,a[i].y_2=posy2;
g[posy1].push_back((WS){posx1,posx2,1});
g[posy2].push_back((WS){posx1,posx2,-1});
}
build(1,1,2*n-1);
/*
for(int i=1;i<=2*n;i++){
printf("%lld ",zhenx[i]);
}
printf("\n");
for(int i=1;i<=2*n;i++){
printf("%lld ",zheny[i]);
}
printf("\n");
*/
int ans=0;
for(int i=1;i<2*n;i++){
for(int j=0;j<g[i].size();j++){
//printf("add (%lld,%lld,%lld)\n",g[i][j].l,g[i][j].r-1,g[i][j].op);
update(1,g[i][j].l,g[i][j].r-1,g[i][j].op);
int que=query(1,1,2*n-1);
//printf("(%lld-%lld)*(%lld-%lld-%lld)\n",zheny[i+1],zheny[i],zhenx[2*n],zhenx[1],que);
ans=ans+(zheny[i+1]-zheny[i])*(zhenx[2*n]-zhenx[1]-que);
}
}
printf("%lld",ans);
return 0;
}
rt,dalao求条QaQ,尽力了
另外就是,我也不知道为什么,我N=1e5+5会RE,N=2e5+5会TLE
回复
共 1 条回复,欢迎继续交流。
正在加载回复...