萌新刚学扫描线,WA20/快哭了
查看原帖
萌新刚学扫描线,WA20/快哭了
171487
cmll02楼主2021/7/16 16:24
/*
+
++
+++
++++
+++++
++++++
+++++++
++++++++
+++++++++
++++++++++
+++++++++++
++++++++++++
+++++++++++++
++++++++++++++
+++++++++++++++
++++++++++++++++
+++++++++++++++++
++++++++++++++++++
+ +++++++++++++++++
+  ++++++++++++++ ++
+   +++++++++++++  ++
+    ++++++++++++   ++
+     +++++++++++    ++
+      ++++++++++     ++
+       +++++++++      ++
+        ++++++++       ++
+         +++++++++++++++++
+          +++++++++++++++++
+           ++++++++++++++
+            +++++++++++
+             ++++++++
+              +++++
+               ++
+               +
+               +
+              ++
+             +++
+            ++++
+           +++++
+           +++++
+           +++++
+           +++++
+     +     +++++
+    +++    +++++
+   ++ ++   +++++
+  ++   ++  +++++
+ ++  +  ++ +++++
+++  +++  +++++++
++  ++ ++  ++++++
 
 
 ++++++++      +++++++++++     +++      +++        ++++++++        ++++++++
+++++++++     +++++++++++++    +++      +++       +++    +++      +++    +++
+++          +++   +++   +++   +++      +++      +++   ++++++    +++      +++
+++          +++   +++   +++   +++      +++      +++ +++  +++           +++
+++          +++   +++   +++   +++ ++   +++ ++   ++++++   +++         +++
+++++++++    +++   +++   +++   +++ ++   +++ ++    +++    +++        +++    ++
 ++++++++    +++   +++   +++   +++++    +++++      ++++++++       +++++++++++
*/
//扫描线不会QAQ
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
#define newe(n) struct Edge{int v,w,nxt;}e[n*2+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v,int w){e[cnt]=(Edge){v,w,h[u]};h[u]=cnt++;}
#define mgs int fa[1<<22],sz[1<<22],t[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int u(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
inline int re1d()
{
    char c=getchar();
    while(c<48||c>49)c=getchar();
    return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
typedef int arr[1000005];
arr minn,tag,cc;
typedef int qwq[1000005];
struct QueryX{
    int id,l,r,mul;
    bool operator<(const QueryX &b)const
    {
        return id!=b.id?id<b.id:mul<b.mul;
    }
}xx[1000050],yy[1000005];
int ccx=0,ccy=0;
//const int Nqwq=10005;
int uniqx[1000005],uniqy[1000005];
int tmpx[1000005],tmpy[1000005],tmpX[1000005],tmpY[1000005];
void build(int o,int l,int r)
{
    if(l==r)
    {
        minn[o]=tag[o]=0;
        cc[o]=1;
        return;
    }
    int m=l+r>>1;
    build(o<<1,l,m);
    build(o<<1|1,m+1,r);
    minn[o]=tag[o]=0;
    cc[o]=cc[o<<1]+cc[o<<1|1];
}
void pushdown(int o,int l,int r)
{
    if(l==r)
    {
        minn[o]+=tag[o];
        tag[o]=0;
        cc[o]=1;
        return;
    }
    tag[o<<1]+=tag[o];
    tag[o<<1|1]+=tag[o];
    minn[o<<1]+=tag[o];
    minn[o<<1|1]+=tag[o];
    tag[o]=0;
}
void maintain(int o,int l,int r)
{
    if(l==r)
    {
        minn[o]+=tag[o];
        tag[o]=0;
        cc[o]=1;
        return;
    }
    if(minn[o<<1]==minn[o<<1|1])minn[o]=minn[o<<1]+tag[o],cc[o]=cc[o<<1]+cc[o<<1|1];
    else if(minn[o<<1]<minn[o<<1|1])minn[o]=minn[o<<1]+tag[o],cc[o]=cc[o<<1];
    else minn[o]=minn[o<<1|1]+tag[o],cc[o]=cc[o<<1|1];
}
void update(int o,int l,int r)
{
    if(l==r)
    {
        minn[o]+=tag[o];
        tag[o]=0;
        cc[o]=1;
        return;
    }
    minn[o]+=tag[o];
}
void add(int o,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R)
    {
        tag[o]+=x;
        minn[o]+=x;
        return;
    }
    pushdown(o,l,r);
    int m=l+r>>1;
    if(L<=m)add(o<<1,l,m,L,R,x);//else update(o<<1,l,m);
    if(m<R)add(o<<1|1,m+1,r,L,R,x);//else update(o<<1|1,m+1,r);
    maintain(o,l,r);
}
inline int query(int o,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
    {
	    if(minn[o]==0)return cc[o];
	    return 0;
    }
//    pushdown(o,l,r);
	int ans=0;
    int m=l+r>>1;
    if(L<=m)ans+=query(o<<1,l,m,L,R);//else update(o<<1,l,m);
    if(m<R)ans+=query(o<<1|1,m+1,r,L,R);//else update(o<<1|1,m+1,r);
    return ans;
//    maintain(o,l,r);
}
std::set<int> sx[200005],sy[200005]; 
signed main()
{
	int n=read();
	rg(n)tmpx[i]=uniqx[i]=read(),uniqy[i]=tmpy[i]=read();gr
    std::sort(uniqx+1,uniqx+n+1);
    std::sort(uniqy+1,uniqy+n+1);
    int lenx=std::unique(uniqx+1,uniqx+n+1)-uniqx-1;
    int leny=std::unique(uniqy+1,uniqy+n+1)-uniqy-1;
    rg(n)tmpx[i]=std::lower_bound(uniqx+1,uniqx+1+lenx,tmpx[i])-uniqx;
	tmpy[i]=std::lower_bound(uniqy+1,uniqy+1+leny,tmpy[i])-uniqy;
	sx[tmpx[i]].insert(tmpy[i]);sy[tmpy[i]].insert(tmpx[i]);gr
	rg(lenx)if(*sx[i].begin()==*sx[i].rbegin())continue;xx[++ccx]=(QueryX){*sx[i].begin(),i,i,1};
	xx[++ccx]=(QueryX){*sx[i].rbegin(),i,i,-1};gr
	rg(leny)int l=*sy[i].begin(),r=*sy[i].rbegin();
	if(r-l>1)xx[++ccx]=(QueryX){i,l+1,r-1,0};gr
    std::sort(xx+1,xx+1+ccx);
    int cx=0,curx=1,ans=0,qaq;
    build(1,1,lenx);
    rg(leny)
    for(;curx<=ccx;curx++)
    {
        if(xx[curx].id!=i)break;
        if(xx[curx].mul)add(1,1,lenx,xx[curx].l,xx[curx].r,xx[curx].mul);
       else qaq=query(1,1,lenx,xx[curx].l,xx[curx].r),ans+=xx[curx].r-xx[curx].l-qaq+1;
    }
    gr oldl(ans+n);
    return 0;
}

2021/7/16 16:24
加载中...