//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "线段树优化建边+Tarjan缩点": {
        "prefix": "acm-3.7炸弹",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<queue>",
            "#include<map>",
            "#define LL long long",
            "#define Re register int",
            "#define mp make_pair",
            "using namespace std;",
            "const int N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7;",
            "int o,n,Ans,head[N<<2];LL X[N],R[N];",
            "struct QAQ{int x,to,next;}a[M];map<pair<int,int>,int>vis;",
            "inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}",
            "template<typename T>inline void in(T &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)",
            "\tint O;",
            "\tstruct QAQ{int in;}tr[N<<2];",
            "\tinline void build(Re p,Re L,Re R){",
            "\t\tif(L==R){tr[p].in=L;return;}",
            "\t\ttr[p].in=++O;",
            "\t\tbuild(pl,L,mid),build(pr,mid+1,R);",
            "\t\tadd(tr[p].in,tr[pl].in),add(tr[p].in,tr[pr].in);",
            "\t}",
            "\tinline void change(Re p,Re L,Re R,Re l,Re r,Re x){",
            "//\t\tprintf(\"(x=%d) -> (l=%d,r=%d) w=%d\\n\",x,l,r,w);return;",
            "\t\tif(l<=L&&R<=r){add(x,tr[p].in);return;}",
            "\t\tif(l<=mid)change(pl,L,mid,l,r,x);",
            "\t\tif(r>mid)change(pr,mid+1,R,l,r,x);",
            "\t}",
            "}TR;",
            "inline int find1(LL x,Re r){",
            "\tRe l=1;",
            "\twhile(l<r){",
            "\t\tRe Mid=l+r>>1;",
            "\t\tif(X[Mid]<x)l=Mid+1;",
            "\t\telse r=Mid;",
            "\t}",
            "\treturn r;",
            "}",
            "inline int find2(LL x,Re l){",
            "\tRe r=n;",
            "\twhile(l<r){",
            "\t\tRe Mid=l+r+1>>1;",
            "\t\tif(X[Mid]>x)r=Mid-1;",
            "\t\telse l=Mid;",
            "\t}",
            "\treturn l;",
            "}",
            "struct Tuopu{",
            "\tint o,n,L[N<<2],R[N<<2],ru[N<<2],pan[N<<2],head[N<<2];queue<int>Q;",
            "\tstruct QAQ{int to,next;}a[M];",
            "\tinline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}",
            "\tinline void dfs(Re x){",
            "\t\tif(pan[x])return;",
            "\t\tpan[x]=1;",
            "\t\tfor(Re i=head[x],to;i;i=a[i].next)",
            "\t\t\tdfs(to=a[i].to),L[x]=min(L[x],L[to]),R[x]=max(R[x],R[to]);",
            "\t}",
            "\tinline void sakura(){for(Re i=1;i<=n;++i)if(!ru[i])dfs(i);}",
            "}T2;",
            "int Q_o,ip[N<<2];",
            "struct Tarjan{",
            "\tint n,t,dfn_o,Q[N<<2],low[N<<2],dfn[N<<2],pan[N<<2];",
            "\tinline void tarjan(Re x){",
            "\t\tdfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;",
            "\t\tfor(Re i=head[x],to;i;i=a[i].next)",
            "\t\t\tif(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);",
            "\t\t\telse if(pan[to])low[x]=min(low[x],dfn[to]);",
            "\t\tif(low[x]==dfn[x]){",
            "\t\t\t++Q_o,T2.L[Q_o]=n+1,T2.R[Q_o]=-1;",
            "\t\t\twhile(1){",
            "\t\t\t\tip[Q[t]]=Q_o,pan[Q[t]]=0;",
            "\t\t\t\tif(x==Q[t--])break;",
            "\t\t\t}",
            "\t\t}",
            "\t}",
            "\tinline void sakura(){",
            "\t\tfor(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);",
            "\t\tfor(Re i=1,x,y;i<=o;++i)",
            "\t\t\tif((x=ip[a[i].x])!=(y=ip[a[i].to])&&!vis[mp(x,y)])",
            "\t\t\t\tvis[mp(x,y)]=1,++T2.ru[y],T2.add(x,y);",
            "\t}",
            "}T1;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),TR.O=n,TR.build(1,1,n);",
            "\tfor(Re i=1;i<=n;++i)in(X[i]),in(R[i]);",
            "\tfor(Re i=1;i<=n;++i)TR.change(1,1,n,find1(X[i]-R[i],i),find2(X[i]+R[i],i),i);",
            "\tT1.n=TR.O,T1.sakura();",
            "\tfor(Re i=1;i<=n;++i)T2.L[ip[i]]=min(T2.L[ip[i]],i),T2.R[ip[i]]=max(T2.R[ip[i]],i);;",
            "\tT2.n=Q_o,T2.sakura();",
            "\tfor(Re i=1;i<=n;++i)(Ans+=(LL)i*(T2.R[ip[i]]-T2.L[ip[i]]+1)%P)%=P;",
            "\tprintf(\"%d\\n\",Ans);",
            "}",
            ""
        ],
        "description": "插入 线段树优化建边+Tarjan缩点"
    }
}