CSP田地丈量问题c语言

Question

我的代码显示运行错误，不知道哪里有问题，希望有人可以讲解一下

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7639375
• 这篇博客你也可以参考下：CSP试题—— 称检测点查询
• 除此之外, 这篇博客: 第23次CSP认证题解中的 第五题 箱根山岳险天下（50分） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 这题依然是看的其他人的题解，主要是参考的CSDN上另一位博主的代码，传送门
  用到的知识是树链剖分线段树。
  因为没有用LCT（动态树），所以只能拿50分。（异或操作强制在线，树链剖分要知道树的形态）。LCT目前我还没学，我上面发的那个博主写了，b站也有一个题解。大家可以自行搜索。

  #include <bits/stdc++.h>
  
  #define mid ((l+r)>>1)
  #define lson rt<<1,l,mid
  #define rson rt<<1|1,mid+1,r
  
  using namespace std;
  
  typedef long long ll;
  
  const int maxm = 300000 + 10;
  
  struct req {
      ll type, x2, s, l, r, y2;
  
      req(ll type, ll x2, ll s, ll l, ll r, ll y2)
              : type(type), x2(x2), s(s), l(l), r(r), y2(y2) {}
  };
  
  vector<req> R;
  ll m, p, T;
  //ll e = 0, beg[maxm], nex[maxm], to[maxm];
  ll dep[maxm], siz[maxm], fa[maxm], son[maxm];
  ll id[maxm], top[maxm], cnt = 0;
  ll sum[maxm << 2], lazy[maxm << 2];
  ll now, res, tot = 0,rt;
  ll A = 0;
  vector<ll> edge[maxm];
  vector<pair<ll, ll> > E[maxm];
  
  //inline void add(ll x, ll y) {
  //    to[++e] = y;
  //    nex[e] = beg[x];
  //    beg[x] = e;
  //}
  
  inline void dfs1(ll x) {//x当前节点，f父亲，deep深度
      siz[x] = 1;
      ll maxson = 0;
  
      for (ll y:edge[x]) {
  //        ll y = to[i];
          if (y == fa[x])
              continue;
          dfs1(y);
          siz[x] += siz[y];
          if (siz[y] > maxson) {
              son[x] = y;
              maxson = siz[y];
          }
      }
  }
  
  inline void dfs2(ll x, ll topf) {//x当前节点，topf当前链的最顶端的节点
      id[x] = ++cnt;
      top[x] = topf;
      if (!son[x])
          return;
      dfs2(son[x], topf);
      for (ll y:edge[x]) {
  //        ll y = to[i];
          if (y == fa[x] || y == son[x])
              continue;
          dfs2(y, y);
      }
  }
  
  inline void pushdown(ll rt) {
      if (lazy[rt] != 1) {
          lazy[rt << 1] = (lazy[rt] * lazy[rt << 1]) % p;
          lazy[rt << 1 | 1] = (lazy[rt] * lazy[rt << 1 | 1]) % p;
  
          sum[rt << 1] = (lazy[rt] * sum[rt << 1]) % p;
          sum[rt << 1 | 1] = (lazy[rt] * sum[rt << 1 | 1]) % p;
          lazy[rt] = 1;
      }
  }
  
  inline void insert(ll rt, ll l, ll r, ll v, ll y) {
      if (l == r) {
          sum[rt] = y;
          sum[rt] %= p;
          lazy[rt] = 1;
          return;
      } else {
          if (lazy[rt] != 1)
              pushdown(rt);
          if (v <= mid)
              insert(lson, v, y);
          if (v > mid)
              insert(rson, v, y);
          sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
      }
  }
  
  inline void query(ll rt, ll l, ll r, ll L, ll R) {
      if (L <= l && r <= R) {
          res += sum[rt];
          res %= p;
          return;
      } else {
          if (lazy[rt] != 1)
              pushdown(rt);
          if (L <= mid)
              query(lson, L, R);
          if (R > mid)
              query(rson, L, R);
      }
  }
  
  inline void update(ll rt, ll l, ll r, ll L, ll R, ll k) {
      if (L <= l && r <= R) {
          lazy[rt] = (lazy[rt] * k) % p;
          sum[rt] = (sum[rt] * k) % p;
      } else {
          if (lazy[rt] != 1)pushdown(rt);
          if (L <= mid)update(lson, L, R, k);
          if (R > mid)update(rson, L, R, k);
          sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
      }
  }
  
  inline ll qRange(ll x, ll y) {
      ll ans = 0;
      while (top[x] != top[y]) {
          if (dep[top[x]] < dep[top[y]])swap(x, y);
          res = 0;
          query(1, 1, tot, id[top[x]], id[x]);
          ans += res;
          ans %= p;
          x = fa[top[x]];
      }
  
      if (dep[x] > dep[y])swap(x, y);
      res = 0;
      query(1, 1, tot, id[x], id[y]);
      ans += res;
      return ans % p;
  }
  
  inline void updRange(ll x, ll y, ll k) {
      k %= p;
      while (top[x] != top[y]) {
          if (dep[top[x]] < dep[top[y]]) swap(x, y);
          update(1, 1, tot, id[top[x]], id[x], k);
          x = fa[top[x]];
      }
      if (dep[x] > dep[y]) swap(x, y);
      update(1, 1, tot, id[x], id[y], k);
  }
  
  inline ll find(ll x, ll y) {
      ll l = 0, r = E[x].size() - 1, ans = 0;
      while (l <= r) {
          ll mi = (l + r) >> 1;
          if (E[x][mi].first <= y) {
              ans = E[x][mi].second;
              l = mi + 1;
          } else
              r = mi - 1;
      }
      return ans;
  }
  
  
  int main() {
      ll type;
      scanf("%lld%lld%lld", &m, &p, &T);
      rt = now = 0;
      tot = 0;
      for (int i = 1; i <= m << 2; i++) {
          lazy[i] = 1;
          sum[i] = 0;
      }
      dep[0] = 0;
      for (ll t = 1, x2, y2, s, l, r; t <= m; t++) {
          scanf("%lld", &type);
          x2 = y2 = s = l = r = 0;
          if (type == 1) {
              scanf("%lld", &x2);
              if (x2 == 0) {
                  now = fa[now];
              } else {
                  s = ++tot;
                  fa[tot] = now;
                  dep[tot] = dep[now] + 1;
                  edge[now].push_back(tot);
  //                add(now, tot);
  //                add(tot, now);
                  E[dep[tot]].push_back({t, tot});
                  now = tot;
              }
          } else if (type == 2) {
              scanf("%lld%lld%lld%lld", &s, &l, &r, &y2);
          } else if (type == 3) {
              scanf("%lld%lld%lld", &s, &l, &r);
          }
          R.push_back(req(type, x2, s, l, r, y2));
      }
      A = 0;
      tot++;
      dfs1(rt);
      dfs2(rt, rt);
      for (req re: R) {
          if (re.type == 1) {
              if (re.x2) {
                  insert(1, 1, tot, id[re.s], re.x2 ^ A);
              }
          } else {
              ll x = find(re.l, re.s);
              ll y = find(re.r, re.s);
              if (re.type == 2) {
                  updRange(x, y, re.y2 ^ A);
              } else {
                  res = qRange(x, y);
                  printf("%lld\n", res);
                  if (T)
                      A = res;
              }
          }
      }
      return 0;
  }