题解 | #不会有人520打算竞吧？#

https://ac.nowcoder.com/acm/contest/58568/J

随机数据 ， 区间覆盖 ， 区间X次方和

很明显，珂朵莉

用DFS序把子树转成区间就好了

#include <bits/stdc++.h>
#define endl "\n"
#define ls p << 1
#define rs p << 1 | 1
#define int long long
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define io                            \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);                  \
    std::cout.tie(0)
using namespace std;
typedef pair<int, int> PII;
typedef unsigned long long u64;

mt19937_64 mrand(random_device{}());

template <typename T>
inline void read(T& x) {
    int f = 1;
    x = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }
}
// long long long
// Êý×鿪¹» N+10
// ÓÐÏòͼ or ÎÞÏòͼ
// ¶à×éÊý¾Ý,³õʼ»¯
// LLLLLLLLLLLLL

const int N = 1e6 + 10;
const int inf = 8e18;
const int mod = 1e9 + 7;

struct my {
    int l, r;
    mutable int v;
    my(int l, int r = 0, int v = 0)
        : l(l), r(r), v(v) {
    }

    bool operator<(const my& a) const {
        return l < a.l;
    }
};
int n, m, seed, vmax, a[N];
int le[N], re[N];
int h[N], e[N], ne[N];
int idx, back[N], cnt;

set<my> s;

set<my>::iterator split(int pos) {
    set<my>::iterator it = s.lower_bound(my(pos));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    if (it->r < pos)
        return s.end();

    int l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(my(l, pos - 1, v));
    return s.insert(my(pos, r, v)).first;
}
void assign(int l, int r, int x) {
    set<my>::iterator itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(my(l, r, x));
}
int qmi(int a, int b, int p) {
    int res = 1;
    a = a % p;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b = b >> 1;
    }
    return res;
}
int calP(int l, int r, int x, int y) {
    set<my>::iterator itr = split(r + 1), itl = split(l);
    int ans = 0;
    for (auto i = itl; i != itr; ++i) {
        ans = (ans + qmi(i->v, x, y) * (i->r - i->l + 1) % y) % y;
    }
    return ans;
}
int rnd() {
    int res = seed;
    seed = (seed * 7 + 13) % mod;
    return res;
}
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int x, int fa) {
    ++cnt;
    le[x] = cnt;
    back[cnt] = x;

    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa)
            continue;
        dfs(j, x);
    }
    re[x] = cnt;
}

signed main() {
    io;
    mem(h, -1);
    cin >> n >> m >> seed >> vmax;
    For(i, 1, n) {
        a[i] = (rnd() % vmax) + 1;
        // s.insert(my(i, i, a[i]));
    }
    For(i, 2, n) {
        int x = (rnd() % (i - 1)) + 1;
        add(i, x);
        add(x, i);
    }
    dfs(1, 1);
    For(i, 1, n) {
        int x = le[i];
        s.insert(my(x, x, a[i]));
    }

    For(i, 1, m) {
        int op, l, r, x, y;
        op = (rnd() % 2) + 1;
        l = (rnd() % n) + 1;

        x = (rnd() % vmax) + 1;
        int a, b;
        a = le[l];
        b = re[l];

        if (op == 1) {
            assign(a, b, x);
        } else {
            cout << calP(a, b, x, mod) << endl;
        }
    }

    return 0;
}