From 68e69c0021b4e393522d4630a3e2f5f2d4cf5591 Mon Sep 17 00:00:00 2001
From: xyjg <50234881+xyjg@users.noreply.github.com>
Date: Mon, 2 Sep 2019 19:45:54 +0800
Subject: [PATCH] Update divide-combine.md

---
 docs/ds/divide-combine.md | 72 ++++++++++++++---------------------------------
 1 file changed, 21 insertions(+), 51 deletions(-)

diff --git a/docs/ds/divide-combine.md b/docs/ds/divide-combine.md
index 4fc3b82b..2286f22e 100644
--- a/docs/ds/divide-combine.md
+++ b/docs/ds/divide-combine.md
@@ -178,46 +178,12 @@ const int N = 200010;
 
 int n, m, a[N], st1[N], st2[N], tp1, tp2, rt;
 int L[N], R[N], M[N], id[N], cnt, typ[N], bin[20], st[N], tp;
-
-char gc() {
-  static char *p1, *p2, s[1000000];
-  if (p1 == p2) p2 = (p1 = s) + fread(s, 1, 1000000, stdin);
-  return (p1 == p2) ? EOF : *p1++;
-}
-int rd() {
-  int x = 0;
-  char c = gc();
-  while (c < '0' || c > '9') c = gc();
-  while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = gc();
-  return x;
-}
-char ps[1000000], *pp = ps;
-void flush() {
-  fwrite(ps, 1, pp - ps, stdout);
-  pp = ps;
-}
-void push(char x) {
-  if (pp == ps + 1000000) flush();
-  *pp++ = x;
-}
-void write(int l, int r) {
-  static int sta[N], top;
-  if (!l)
-    push('0');
-  else {
-    while (l) sta[++top] = l % 10, l /= 10;
-    while (top) push(sta[top--] ^ '0');
-  }
-  push(' ');
-  if (!r)
-    push('0');
-  else {
-    while (r) sta[++top] = r % 10, r /= 10;
-    while (top) push(sta[top--] ^ '0');
-  }
-  push('\n');
-}
-
+//本篇代码原题应为 CERC2017 Intrinsic Interval
+//a数组即为原题中对应的排列
+//st1和st2分别两个单调栈，tp1、tp2为对应的栈顶，rt为析合树的根
+//L、R数组表示该析合树节点的左右端点，M数组的作用在析合树构造时有提到
+//id存储的是排列中某一位置对应的节点编号，typ用于标记析点还是合点
+//st为存储析合树节点编号的栈，tp为其栈顶 
 struct RMQ {  // 预处理 RMQ（Max & Min）
   int lg[N], mn[N][17], mx[N][17];
   void chkmn(int& x, int y) {
@@ -278,7 +244,7 @@ struct SEG {  // 线段树
       return query(ls, l, mid);
     else
       return query(rs, mid + 1, r);
-    // 如果不存在 0 的位置就会自动返回一个极大值
+    // 如果不存在 0 的位置就会自动返回当前你查询的位置 
   }
 } T;
 
@@ -289,7 +255,6 @@ struct Edge {
 void add(int u, int v) {  // 树结构加边
   E[o] = (Edge){v, hd[u]};
   hd[u] = o++;
-  // printf("%d %d\n",u,v);
 }
 void dfs(int u) {
   for (int i = 1; bin[i] <= dep[u]; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
@@ -348,7 +313,8 @@ void build() {
         R[st[tp]] = i, add(st[tp], now), now = st[tp--];
       } else if (judge(L[st[tp]], i)) {
         typ[++cnt] = 1;  // 合点一定是被这样建出来的
-        L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now];
+        L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now]; 
+        //这里M数组的作用是保证合点的儿子排列是单调的 
         add(cnt, st[tp--]), add(cnt, now);
         now = cnt;
       } else {
@@ -375,22 +341,26 @@ void query(int l, int r) {
   int z = lca(x, y);
   if (typ[z] & 1)
     l = L[go(x, dep[x] - dep[z] - 1)], r = R[go(y, dep[y] - dep[z] - 1)];
+    //合点这里特判的原因是因为这个合点不一定是最小的包含l，r的连续段.
+	//具体可以在上面的例图上试一下查询7,10 
   else
     l = L[z], r = R[z];
-  write(l, r);
+  printf("%d %d\n",l,r);
 }  // 分 lca 为析或和，这里把叶子看成析的
 
 int main() {
-  freopen("c.in", "r", stdin);
-  freopen("c.out", "w", stdout);
-  n = rd();
-  for (int i = 1; i <= n; ++i) a[i] = rd();
+  scanf("%d",&n);
+  for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);
   D.build();
   build();
   dfs(rt);
-  m = rd();
-  for (int i = 1; i <= m; ++i) query(rd(), rd());
-  return flush(), 0;
+  scanf("%d",&m);
+  for (int i = 1; i <= m; ++i) {
+  	int x,y;
+  	scanf("%d%d",&x,&y);
+  	query(x,y);
+  }
+  return  0;
 }
 // 20190612
 // 析合树
-- 
2.11.0