2 条题解

  • 0
    @ 2025-10-8 16:49:12
    #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
      @ 2025-10-8 16:48:57
      #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

      *【扫描线】城市的地平线[USACO07OPEN] City Horizon S

      信息

      ID
      300
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      162
      已通过
      50
      上传者