Sol

考虑对于操作时间建立线段树，二进制分组

那么现在主要的问题就是怎么合并信息

你发现一个性质，就是每个修改只会在整个区间内增加两个端点

那么我们二进制分组可以得到每个区间内最多只有区间长度级别段，每一段的修改都是一样的

那么可以直接一层层归并上来

最后询问就是二分每一个线段树的节点的询问段即可

修改复杂度 \(\Theta(n log n)\) 询问复杂度 \(\Theta(n log^2 n)\)

# include 
    
     using namespace std;typedef long long ll;namespace IO {    const int maxn((1 << 21) + 1);    char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf, *oT = obuf + maxn - 1, c, st[55];    int f, tp;        char Getc() {        return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);    }    void Flush() {        fwrite(obuf, 1, oS - obuf, stdout);        oS = obuf;    }    void Putc(char x) {        *oS++ = x;        if (oS == oT) Flush();    }        template 
     
       void In(Int &x) {        for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;        for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);        x *= f;    }        template 
      
        void Out(Int x) {        if (!x) Putc('0');        if (x < 0) Putc('-'), x = -x;        while (x) st[++tp] = x % 10 + '0', x /= 10;        while (tp) Putc(st[tp--]);    }}using IO :: In;using IO :: Out;using IO :: Putc;using IO :: Flush;const int maxn(1e5 + 5);int n, q, m, a[maxn], type, cnt, nowl[maxn << 2], nowr[maxn << 2], tot, ans;struct Mdy {    int r, a, b;} mdy[maxn * 30];void Modify(int x, int l, int r, int ql, int qr, int a, int b) {    if (l == r) {        nowl[x] = tot + 1;        if (ql > 1) mdy[++tot] = (Mdy){ql - 1, 1, 0};        mdy[++tot] = (Mdy){qr, a, b};        if (qr < n) mdy[++tot] = (Mdy){n, 1, 0};        nowr[x] = tot;        return;    }    register int mid = (l + r) >> 1, l1, r1, l2, r2;    cnt <= mid ? Modify(x << 1, l, mid, ql, qr, a, b) : Modify(x << 1 | 1, mid + 1, r, ql, qr, a, b);    if (cnt < r) return;    nowl[x] = tot + 1, l1 = nowl[x << 1], r1 = nowr[x << 1], l2 = nowl[x << 1 | 1], r2 = nowr[x << 1 | 1];    while (l1 <= r1 && l2 <= r2) {        mdy[++tot] = (Mdy){min(mdy[l1].r, mdy[l2].r), (ll)mdy[l1].a * mdy[l2].a % m, ((ll)mdy[l1].b * mdy[l2].a + mdy[l2].b) % m};        if (mdy[l1].r == mdy[l2].r) ++l1, ++l2;        else mdy[l1].r < mdy[l2].r ? ++l1 : ++l2;    }    nowr[x] = tot;}inline void Calc(int x, int p) {    register int l = nowl[x], r = nowr[x], cur = 0, mid;    while (l <= r) mdy[mid = (l + r) >> 1].r >= p ? cur = mid, r = mid - 1 : l = mid + 1;    ans = ((ll)ans * mdy[cur].a + mdy[cur].b) % m;}void Query(int x, int l, int r, int ql, int qr, int p) {    if (ql <= l && qr >= r) {        Calc(x, p);        return;    }    register int mid = (l + r) >> 1;    if (ql <= mid) Query(x << 1, l, mid, ql, qr, p);    if (qr > mid) Query(x << 1 | 1, mid + 1, r, ql, qr, p);}int main() {    register int i, j, op, p, l, r;    In(type), In(n), In(m);    for (i = 1; i <= n; ++i) In(a[i]);    In(q);    while (q--) {        In(op);        if (op == 1) {            In(l), In(r), In(i), In(j);            if (type & 1) l ^= ans, r ^= ans;            ++cnt, Modify(1, 1, 100000, l, r, i, j);        }        else {            In(l), In(r), In(p);            if (type & 1) l ^= ans, r ^= ans, p ^= ans;            ans = a[p], Query(1, 1, 100000, l, r, p);            Out(ans), Putc('\n');        }    }    return Flush(), 0;}