题解：P7134 小 H 的序列

fly_fire · 2025-03-19 21:24:40 · 题解

solution

这个查询操作看起来十分像珂朵莉树的起源题对吧，所以自然想到珂朵莉树解决。

操作一似乎不能直接推平，考虑把每个区间转存到数组里面，再把操作区间删掉，然后把相邻且值相同的区间合并之后再加到珂朵莉树中。

询问操作就是很典的珂树了，把每个树里的的区间一起计算 v ^ {p}，再乘上区间长度，累加到答案。

（怎么感觉能珂树的题都比较容易实现）

一些小细节

1.查询操作的累加应该写作 cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;，不要模错地方，不要把 cnt 放到乘长度的括号里（因为这句盯了好久）。

2.正如大佬所说，就这样子写的话会因为每个查询里面有很多一样的数被重复计算而 T 一个点，所以要给快速幂加上记忆化。

code

#include<bits/stdc++.h>

#define int unsigned long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;

int n, m;

struct Node {
    int l, r;
    mutable int v;

//  Node(int x, int y, int z) {
//      l = x, r = y, v = z;
//  }

    bool operator < (const Node & x) const {
        return l < x.l;
    } 
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    if (r < x) return odt.end();    
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, v});
}

int MOD[maxn], Val[maxn];
int qpow(int a, int p, int mod) {
    int ans = 1LL, A = a;

    if (MOD[A] == mod) return Val[A];

    while (p) {
        if (p & 1) ans *= a, ans %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }

    Val[A] = ans, MOD[A] = mod;

//  cout << ans << '\n'; 
    return ans % mod;
}

void update(int l, int r, int x, int y, int d) {
//  cout << l << ' ' << r << ' ' << x << ' ' << y << ' ' << d << '\n';
    auto itr = split(r + 1), itl = split(l);Node its[maxn];
    int tot = 1, nowx = 0;
    for (auto i = itl;i != itr;i++) {
        int v = i -> v;
        its[++tot] = *i;
        if (v <= y && v >= x) its[tot].v = d;
    }

    odt.erase(itl, itr);

    for (int i = 1;i <= tot;i++) {
        if (i == 1 || its[i].v != its[i - 1].v) {
            if (nowx) odt.insert({nowx, its[i - 1].r, its[i - 1].v});
            nowx = its[i].l;
        }
    }
    odt.insert({nowx, r, its[tot].v});
}

int len(auto it) {
    return it -> r - it -> l + 1;
}

int query(int l, int r, int p, int mod) {
//  cout << l << ' ' << r << ' ' << p << ' ' << mod << '\n';
    auto itr = split(r + 1), itl = split(l);
//  cout << itl -> l << ' ' << itr -> r;
    int cnt = 0;
    for (;itl != itr;itl++) {
//      cout << itl -> l << ' ' << itl -> r << ' ' << itl -> v << ' ' << len(itl) << '\n';
//      (((cnt += qpow(itl -> v, p, mod)) %= mod) *= len(itl)) %= mod;
        cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
//      cout << qpow(itl -> v, p, mod) << "nailong " << cnt << '\n';
    }
//  cout << cnt << '\n';
    return cnt;
}

signed main() {
    n = read(), m = read();

    for (int i = 1;i <= n;i++) odt.insert({i, i, read()});

    int Ans = 0;

    while (m--) {
        int op = read(), l = read(), r = read(), u = read(), v = read(), t;
        if (op == 0) t = read(), update(l, r, u, v, t);
        else Ans ^= query(l, r, u, v);

//      for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
    }

    write(Ans), putchar(10);

    return 0;
}