//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "扫描线（线段树）": {
        "prefix": "acm-8.3周长",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define y1 yyyy",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=5e4+3,M=2e4+3;",
            "int n,m,ans,Max=10000,x1[N],y1[N],x2[N],y2[N];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Segment_Tree{",
            "\t#define pl (p<<1)",
            "\t#define pr (p<<1|1)",
            "\t#define mid ((L+R)>>1)",
            "\tstruct QAQ{int S,cnt;}tr[M<<2];",
            "\tinline void pushup(Re p,Re L,Re R){",
            "\t\tif(tr[p].cnt)tr[p].S=R-L+1;",
            "\t\telse tr[p].S=(L==R)?0:tr[pl].S+tr[pr].S;",
            "\t}",
            "\tinline void change(Re p,Re L,Re R,Re l,Re r,Re v){",
            "\t\tif(l<=L&&R<=r){tr[p].cnt+=v,pushup(p,L,R);return;}",
            "\t\tif(l<=mid)change(pl,L,mid,l,r,v);",
            "\t\tif(r>mid)change(pr,mid+1,R,l,r,v);",
            "\t\tpushup(p,L,R);",
            "\t}",
            "}TR1,TR2;",
            "struct Line{",
            "\tint x,y1,y2,k;Line(Re X=0,Re Y1=0,Re Y2=0,Re K=0){x=X,y1=Y1,y2=Y2,k=K;}",
            "\tinline bool operator<(const Line &O)const{return x!=O.x?x<O.x:k>O.k;}",
            "}L1[N<<1],L2[N<<1];",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n);",
            "\tfor(Re i=1;i<=n;++i)",
            "\t\tin(x1[i]),in(y1[i]),in(x2[i]),in(y2[i]),x1[i]+=Max,y1[i]+=Max,x2[i]+=Max,y2[i]+=Max,",
            "\t\tL1[++m]=Line(x1[i],y1[i],y2[i],1),L2[m]=Line(y1[i],x1[i],x2[i],1),",
            "\t\tL1[++m]=Line(x2[i],y1[i],y2[i],-1),L2[m]=Line(y2[i],x1[i],x2[i],-1);",
            "\tsort(L1+1,L1+m+1),sort(L2+1,L2+m+1);",
            "\tfor(Re i=1,j=0;i<=m;i=j+1){",
            "\t\tRe last=TR1.tr[1].S;",
            "\t\t++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);",
            "\t\twhile(j+1<=m&&L1[j].x==L1[j+1].x&&L1[j].k==L1[j+1].k)++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);",
            "\t\tans+=abs(last-TR1.tr[1].S);",
            "\t}",
            "\tfor(Re i=1,j=0;i<=m;i=j+1){",
            "\t\tRe last=TR2.tr[1].S;",
            "\t\t++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);",
            "\t\twhile(j+1<=m&&L2[j].x==L2[j+1].x&&L2[j].k==L2[j+1].k)++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);",
            "\t\tans+=abs(last-TR2.tr[1].S);",
            "\t}",
            "\tprintf(\"%d\\n\",ans);",
            "}",
            ""
        ],
        "description": "插入 扫描线（线段树）"
    }
}