莫隊2 這次需要帶修改了

莫隊1 走上騙分之路

實現修改

莫隊是不支持修改的, 但是有后人加以改進, 就有了代修版本.

我們現在有一個東西叫時間軸 (類似函數式線段樹的每個根都是關于某次之前的根修改或查詢的), 每次詢問都記錄一下當前的時間軸, 每次修改都在時間軸上新建一個版本.

typedef struct _qryy {
  int l, r;
  int t, i;
} qryy;

這次要可以 \(O(1)\) 給 \(([l, r], t)\) 擴展到 \(([l \pm 1, r], t)\), \(([l, r \pm 1], t)\) 和 \(([l, r], t \pm 1)\).

現在的排序第一關鍵字是 \(l\) 所在的塊, 第二關鍵字是 \(r\), 第三關鍵字是 \(t\).

然后在記錄修改的位置和值.

typedef struct _updd {
  int x, k;
} updd;

這次舉例單點修區間和

1 x k \(a_{x} := a_{x} + k\)
2 x y 求 \(\displaystyle \sum_{i \in [x, y]} a_{i}\)

樹狀數組1.

顯然這是樹狀數組/線段樹板子, 但是我們還是在討論莫隊.

VJudge LuoGu

由于莫隊本身復雜度玄學, Defad只得到了 70 分, 當然也可能是Defad在分塊時分的不夠好或各種玄學優化不會, 得分比Defad高可以在評論區發一下您怎么優化的.

int cmp(const void *a, const void *b) {
  qryy *x = (qryy*)(a), *y = (qryy*)(b);
  if (pos[x->l] ^ pos[y->l]) {
    return x->l - y->l;
  } else if (pos[x->r] ^ pos[y->r]) {
    return pos[x->r] - pos[y->r];
  } else {
    return x->t - y->t;
  }
}

void get_ans() {
  int l = 1, r = 0, t = 0;
  qsort(q + 1, cntq, sizeof(q[0]), cmp);
  f1 (i, 1, cntq, 1) {
    while (l < q[i].l) {
      s -= a[l] + upd[l];
      l++;
    }
    while (q[i].l < l) {
      l--;
      s += a[l] + upd[l];
    }
    while (r < q[i].r) {
      r++;
      s += a[r] + upd[r];
    }
    while (q[i].r < r) {
      s -= a[r] + upd[r];
      r--;
    }
    while (t < q[i].t) {
      t++;
      if (q[i].l <= c[t].x && c[t].x <= q[i].r) {
        s += c[t].k; // 更新 sum
      }
      upd[c[t].x] += c[t].k; // 版本前進
    }
    while (q[i].t < t) {
      if (q[i].l <= c[t].x && c[t].x <= q[i].r) {
        s -= c[t].k; // 更新 sum
      }
      upd[c[t].x] -= c[t].k; // 版本回退
      t--;
    }
    ans[q[i].i] = s;
  }
}

例題

VJudge LuoGu

例題也差不多, 但是單點賦值和單點加不同, 單點賦值可以給點值和修改值交換, 下次版本回退可以在換回來.

本題似乎塊長開到 \(N^{\cfrac{2}{3}}\) 并且在排序時看 \(l\) 所在塊和 \(r\) 所在塊和 \(t\) 才可通過.

int cmp(const void *a, const void *b) {
  qryy *x = (qryy*)(a), *y = (qryy*)(b);
  if (pos[x->l] ^ pos[y->l]) {
    return x->l - y->l;
//} else if (x->r ^ y->r) { // 用這個相比下方的會TLE
//  return x->r - y->r;
  } else if (pos[x->r] ^ pos[y->r]) {
    return pos[x->r] - pos[y->r];
  } else {
    return x->t - y->t;
  }
}

void get_ans() {
  int l = 1, r = 0, t = 0;
  qsort(q + 1, cntq, sizeof(q[0]), cmp);
  f1 (i, 1, cntq, 1) {
    while (l < q[i].l) {
      s -= (--clr[a[l++]] == 0);
    }
    while (q[i].l < l) {
      s += (++clr[a[--l]] == 1);
    }
    while (r < q[i].r) {
      s += (++clr[a[++r]] == 1);
    }
    while (q[i].r < r) {
      s -= (--clr[a[r--]] == 0);
    }
    while (t < q[i].t) {
      t++;
      if (q[i].l <= c[t].x && c[t].x <= q[i].r) {
        s -= (--clr[a[c[t].x]] == 0);
        s += (++clr[c[t].k] == 1);
      }
      c[t].k ^= a[c[t].x];
      a[c[t].x] ^= c[t].k;
      c[t].k ^= a[c[t].x];
    }
    while (q[i].t < t) {
      if (q[i].l <= c[t].x && c[t].x <= q[i].r) {
        s -= (--clr[a[c[t].x]] == 0);
        s += (++clr[c[t].k] == 1);
      }
      c[t].k ^= a[c[t].x];
      a[c[t].x] ^= c[t].k;
      c[t].k ^= a[c[t].x];
      t--;
    }
    ans[q[i].i] = s;
  }
}