第三帖了

RT，线段树维护区间和，平方和，支持区间加和区间对固定数取模（这两个操作其实是固定在一起的，相当于 $a_i \to (a_i + k)\%p$ 应该可以做到 $O(n\log n)$ 吧？

但是蒟蒻的算法严重超时了，非常不解。

#pragma GCC optimized(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline void read(int &x)
{
    x = 0;
    int f = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        f |= ch == '-';
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x = f ? -x : x;
    return;
}
#define N 500005
int n, q, p, num[N];
struct node
{
    int l, r, val, maxx, tag;
    ll sum;
};
class segment_tree
{
    public:
    node tree[N << 2];
    inline void pushup(int root)
    {
        tree[root].val = tree[root << 1].val + tree[root << 1 | 1].val;
        tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
        tree[root].maxx = max(tree[root << 1].maxx, tree[root << 1 | 1].maxx);
        return;
    }
    void build(int root, int l, int r)
    {
        tree[root].l = l;
        tree[root].r = r;
        if(l == r)
        {
            tree[root].val = tree[root].maxx = num[l];
            tree[root].sum = 1ll * num[l] * num[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(root << 1, l, mid);
        build(root << 1 | 1, mid + 1, r);
        pushup(root);
        return;
    }
    void addtag(int root, int v)
    {
        tree[root].maxx += v;
        tree[root].sum += 1ll * (tree[root].r - tree[root].l + 1) * v * v + 1ll * 2 * tree[root].val * v;
        tree[root].val += (tree[root].r - tree[root].l + 1) * v;
        tree[root].tag += v;
        return;
    }
    void pushdown(int root)
    {
        if(tree[root].tag)
        {
            addtag(root << 1, tree[root].tag);
            addtag(root << 1 | 1, tree[root].tag);
            tree[root].tag = 0;
        }
        return;
    }
    void updateadd(int root, int L, int R, int v)
    {
        if(L <= tree[root].l && tree[root].r <= R)
        {
            addtag(root, v);
            return;
        }
        pushdown(root);
        int mid = (tree[root].l + tree[root].r) >> 1;
        if(L <= mid)
        {
            updateadd(root << 1, L, R, v);
        }
        if(mid < R)
        {
            updateadd(root << 1 | 1, L, R, v);
        }
        pushup(root);
        return;
    }
    void updatemod(int root, int L, int R)
    {
        if(tree[root].l == tree[root].r)
        {
            tree[root].val %= p;
            tree[root].sum = 1ll * tree[root].val * tree[root].val;
            tree[root].maxx = tree[root].val;
            return;
        }
        pushdown(root);
        if(tree[root].maxx < p)
        {
            return;
        }
        int mid = (tree[root].l + tree[root].r) >> 1;
        if(L <= mid && tree[root << 1].maxx >= p)
        {
            updatemod(root << 1, L, R);
        }
        if(mid < R && tree[root << 1 | 1].maxx >= p)
        {
            updatemod(root << 1 | 1, L, R);
        }
        pushup(root);
        return;
    }
    pair<int, ll> query(int root, int L, int R)
    {
        if(L <= tree[root].l && tree[root].r <= R)
        {
            return make_pair(tree[root].val, tree[root].sum);
        }
        pushdown(root);
        int mid = (tree[root].l + tree[root].r) >> 1;
        pair<int, ll> tmp, ret = make_pair(0, 0ll);
        if(L <= mid)
        {
            tmp = query(root << 1, L, R);
            ret.first += tmp.first, ret.second += tmp.second;
        }
        if(mid < R)
        {
            tmp = query(root << 1 | 1, L, R);
            ret.first += tmp.first, ret.second += tmp.second;
        }
        return ret;
    }
};
segment_tree T;
signed main()
{
//  freopen("pockets.in", "r", stdin);
//  freopen("pockets.out", "w", stdout);
    srand(time(0));
    std::mt19937 rng(rand());
    std::uniform_int_distribution<int> rd(1, 1e9);
    read(n), read(q), read(p);
    for(int i = 1; i <= n; i++)
    {
        read(num[i]);
    }
    T.build(1, 1, n);
    int opt, x, y, v, len;
    while(q--)
    {
        read(opt);
        switch(opt)
        {
            case 1:
            {
                read(x), read(y), read(v);
                T.updateadd(1, x, y, v);
                T.updatemod(1, x, y);
                break;
            }
            case 2:
            {
                read(x), read(y), read(v);
                len = rd(rng) % v;
                if((T.query(1, x, x + len) == T.query(1, y, y + len)) && (T.query(1, x + len, x + v - 1) == T.query(1, y + len, y + v - 1)))
                {
                    printf("ye5\n");
                }
                else
                {
                    printf("n0\n");
                }
                break;
            }
            default:
            {
                return -1;
            }
        }
    }
    return 0;
}