苍天阻我寻你，此情坚贞如一（线段树 + 二分）

苍天阻我寻你，此情坚贞如一

给定两个长度为的数组，满足，每个数字表示向前走步，如果是负数则后退嘛，设小执行数组，小执行数组。

有三种操作：

• 把数组中下标为的数修改为。
• 把数组中下标为的数修改为。
• 如果小起始位置在，小起始位置在，问如果他们各自按照数组执行，在第几步能够行动轨迹重合。

如何判定行动轨迹重合：

假设小走过的区间为，小走过的区间为，如果重合则有，

接下来如何确定小和小走过的区间，设数组的前缀和数组为，数组的前缀和数组为，

数组的前缀最小，前缀最大值数组为，数组的前缀最小，前缀最大值数组为，

由小，小的初始位置，可以确定。

所以有一个较为暴力的算法 二分 + 线段树 去答案，当时这样操作复杂度是的，对于的数据显然是不可行的。

考虑线段树上二分：

假设当前答案在区间为，如果答案在上，一定有这段区间的前缀最大，前缀最小得到的两个区间是不相交的，

另开四个变量来记录区间中的前缀最小， 最大，的前缀最小，最大，

用这四个变量跟区间的最大最小来判断，答案是否落在之间，直到递归到叶节点，进行判断是否符合条件即可。

#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6 + 10;

int a[N], b[N], sum[N], n, m;

struct Seg_tree {
  int maxn[N << 2], minn[N << 2], lazy[N << 2];

  void push_up(int rt) {
    minn[rt] = min(minn[ls], minn[rs]);
    maxn[rt] = max(maxn[ls], maxn[rs]);
  }

  void push_down(int rt) {
    if (!lazy[rt]) {
      return ;
    }
    lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
    minn[ls] += lazy[rt], minn[rs] += lazy[rt];
    maxn[ls] += lazy[rt], maxn[rs] += lazy[rt];
    lazy[rt] = 0;
  }

  void build(int rt, int l, int r) {
    if (l == r) {
      maxn[rt] = minn[rt] = sum[l];
      return ;
    }
    build(lson);
    build(rson);
    push_up(rt);
  }

  void update(int rt, int l, int r, int L, int R, int v) {
    if (l >= L && r <= R) {
      lazy[rt] += v;
      minn[rt] += v, maxn[rt] += v;
      return ;
    }
    push_down(rt);
    if (L <= mid) {
      update(lson, L, R, v);
    }
    if (R > mid) {
      update(rson, L, R, v);
    }
    push_up(rt);
  }

  pii query(int rt, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
      return {minn[rt], maxn[rt]};
    }
    push_down(rt);
    pii ans = {0x3f3f3f3f, -0x3f3f3f3f};
    if (L <= mid) {
      pii res = query(lson, L, R);
      ans.first = min(ans.first, res.first);
      ans.second = max(ans.second, res.second);
    }
    if (R > mid) {
      pii res = query(rson, L, R);
      ans.first = min(ans.first, res.first);
      ans.second = max(ans.second, res.second);
    }
    return ans;
  }
}A, B;

bool judge(int l1, int r1, int l2, int r2, int x, int y) {
  l1 = min(x, x + l1), r1 = max(x, x + r1);
  l2 = min(y, y + l2), r2 = max(y, y + r2);
  int L = max(l1, l2), R = min(r1, r2);
  return L <= R;
}

int query(int rt, int l, int r, int min_a, int max_a, int min_b, int max_b, int x, int y) {
  if (l == r) {
    int cur_mina = min(min_a, A.minn[rt]), cur_maxa = max(max_a, A.maxn[rt]);
    int cur_minb = min(min_b, B.minn[rt]), cur_maxb = max(max_b, B.maxn[rt]);
    if (judge(cur_mina, cur_maxa, cur_minb, cur_maxb, x, y)) {
      return l;
    }
    return -1;
  }
  A.push_down(rt), B.push_down(rt);
  int cur_mina = min(min_a, A.minn[ls]), cur_maxa = max(max_a, A.maxn[ls]);
  int cur_minb = min(min_b, B.minn[ls]), cur_maxb = max(max_b, B.maxn[ls]);
  if (judge(cur_mina, cur_maxa, cur_minb, cur_maxb, x, y)) {
    return query(lson, min_a, max_a, min_b, max_b, x, y);
  }
  else {
    return query(rson, cur_mina, cur_maxa, cur_minb, cur_maxb, x, y);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum[i] = sum[i - 1] + a[i];
  }
  A.build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
    sum[i] = sum[i - 1] + b[i];
  }
  B.build(1, 1, n);
  for (int i = 1, op, x, y; i <= m; i++) {
    scanf("%d %d %d", &op, &x, &y);
    if (op == 1) {
      A.update(1, 1, n, x, n, -a[x]);
      a[x] = y;
      A.update(1, 1, n, x, n, a[x]);
    }
    else if (op == 2) {
      B.update(1, 1, n, x, n, -b[x]);
      b[x] = y;
      B.update(1, 1, n, x, n, b[x]);
    }
    else {
      if (x == y) {
        puts("0");
        continue;
      }
      printf("%d\n", query(1, 1, n, 0x3f3f3f3f, 0, 0x3f3f3f3f, 0, x, y));
    }
  }
  return 0;
}