解題思路

1. 動態規劃轉移：

   • 設 dp[i] 表示搭乘第 i 條公車以到達其終點 d[i] 的方式數量。
   • 對於第 i 條路線 [s[i], d[i]]，我們需要找出可以搭乘的其他路線，其終點落在 [s[i], d[i]-1] 之間，這些路線的終點範圍允許我們轉乘至第 i 條路線。
   • 對於每一條公車路線 i，我們可以找到終點落在 [s[i], d[i]-1] 內的路線範圍，然後將這些路線的 dp 值累加起來作為 dp[i] 的值。

2. 排序公車路線：

   • 為了方便進行動態規劃，我們可以先根據每條公車的終點 d[i] 對路線進行排序。
   • 排序後，可以在處理每一條公車時，只考慮在其之前（終點較小）的路線，以方便進行狀態轉移。

3. 利用線段樹進行區間和查詢：

   • 為了在每次查詢可以快速計算 dp[p1] 到 dp[p2] 的和，我們可以使用線段樹來維護區間和。
   • 當處理每條公車路線時，根據其終點的範圍 [s[i], d[i]-1]，我們可以用線段樹來查詢 dp[p1] 到 dp[p2] 的和，然後將結果加上 dp[i]。

實作細節

1. 線段樹維護區間和：

   • 使用線段樹來維護 dp 值的區間和，每次更新 dp[i] 後，在線段樹中更新對應位置的值。
   • 查詢時，根據起點和終點範圍，利用線段樹高效地查詢區間和，並對隨時對結果取模。

2. 線段樹空間優化：

   • 一開始先不要一次創造從0到m的節點，因為如果沒有節點，那就是0，不需要浪費空間
   • 更新節點時，如果遇到沒有節點，再動態產生節

時間與空間複雜度分析

時間複雜度

• query 函數：線段樹的查詢操作時間複雜度為 O(log⁡n)。
• update 函數：更新操作的時間複雜度同樣為 O(log⁡n)。
• 主程式中，對 a 進行排序需要 O(nlog⁡n)。
• 針對每個區間進行一次查詢和更新，因此每個區間的操作時間為 O(log⁡m)。因此，主迴圈的時間複雜度為 O(nlog⁡m)。

綜合來看，程式的總時間複雜度為：O(nlog⁡n+nlog⁡m)

空間複雜度

• 由於這是一棵線段樹，最壞情況下最多需要 O(m) 節點。每個節點佔用常數空間，因此線段樹的空間複雜度為 O(m)。
• 儲存 a 向量的空間複雜度為 O(n)。

綜合來看，程式的總空間複雜度為：O(m+n)，雖然如此，但因為是動態線段樹，大部分情況下不會用到所有節點，所以實際不會用到這麼多空間

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
int p;

class SegmentTree {
private:
  //線段樹結構
  struct Node {
    int value;
    Node *left;
    Node *right;
    Node() : value(0), left(nullptr), right(nullptr) {}
  };
  //線段樹的根
  Node *root;
  //線段樹的大小
  int n;

  // 區間查詢的遞迴函式
  int query(Node *node, int start, int end, int L, int R) {
    if (!node)
      return 0; // 如果節點尚未建立，則視為0
    if (R < start || end < L)
      return 0; // 區間不相交
    if (L <= start && end <= R)
      return node->value; // 完全在區間內

    int mid = (start + end) / 2;
    int leftSum = query(node->left, start, mid, L, R);
    int rightSum = query(node->right, mid + 1, end, L, R);
    return (leftSum + rightSum) % p;
  }

  // 動態更新的遞迴函式，使idx的值增加val
  void update(Node *&node, int start, int end, int idx, int val) {
    if (!node)
      node = new Node(); // 動態生成節點
    if (start == end) {
      node->value = (node->value+val) % p; // 更新葉節點的值
    } else {
      int mid = (start + end) / 2;
      if (idx <= mid) {
        update(node->left, start, mid, idx, val);
      } else {
        update(node->right, mid + 1, end, idx, val);
      }
      int leftValue = node->left ? node->left->value : 0;
      int rightValue = node->right ? node->right->value : 0;
      node->value = (leftValue + rightValue) % p;//更新此節點的值為其左右子節點相加
    }
  }

public:
  SegmentTree(int size) : n(size) { root = nullptr; }

  // 公開的查詢接口
  int query(int L, int R) { return query(root, 0, n - 1, L, R); }

  // 公開的更新接口
  void update(int idx, int val) { update(root, 0, n - 1, idx, val); }
};
//用來按終點排序
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }

signed main() {
  int n, m;
  cin >> n >> m >> p;

  // 初始化 dp[0] = 1 在線段樹中
  SegmentTree segTree(m + 1);
  segTree.update(0, 1); // 設定 dp[0] = 1

  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i].second;
  }
  sort(a.begin(), a.end(), cmp);

  for (int i = 0; i < n; i++) {
    int num = segTree.query(a[i].first, a[i].second - 1);//出發到終點前一站的總和
    segTree.update(a[i].second, num % p); 
  }

  cout << segTree.query(m, m);
}