ODT 求条

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mod = 1e9 + 7, N = 3e5 + 10;

int n, m, a[N];

struct ODT_node {
    int l, r;
    mutable int val;
    bool operator < (const ODT_node x) const {return l < x.l;}
};
 
struct ODT {
    set<ODT_node> t;
    void build(int a[], int n) {
        int x = a[1], pos = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] != x) {
                t.insert({pos,  i - 1, x});
                pos = i; x = a[i];
            }
        }
        t.insert({pos,  n, a[n]});
    }
    set<ODT_node>::iterator find(int x) {
        auto it = t.lower_bound({x,  0, 0});
        if (it == t.end()  || it->l > x)  it--;
        return it;
    }
    set<ODT_node>::iterator split(int x) {
        auto it = t.lower_bound({x,  0, 0});
        if (it != t.end()  && it->l == x) return it;
        if (it == t.begin())  return t.end();
        it--;
        int l = it->l, r = it->r, val = it->val;
        t.erase(it);  t.insert({l,  x - 1, val});
        return t.insert({x,  r, val}).first;
    }
    set<ODT_node>::iterator merge(set<ODT_node>::iterator it, bool dir) {
        if (dir)  {
            if (it == t.begin())    return t.end();
            auto prev_it = prev(it);
            if (prev_it->val == it->val) {
                int l = prev_it->l, r = it->r, val = it->val;
                t.erase(prev_it);   t.erase(it); 
                return t.insert({l,  r, val}).first;
            }
            return it;
        }
        auto next_it = next(it);
        if (next_it == t.end())	return t.end();
        if (next_it->val == it->val) {
            int l = it->l, r = next_it->r, val = it->val;
            t.erase(next_it);   t.erase(it);
            return t.insert({l,  r, val}).first;
        }
        return it;
    }
    void assign(int l, int r, int val) {
        auto ir = split(r + 1), il = split(l);
        t.erase(il,  ir);
        auto it = t.insert({l,  r, val}).first;
        it = merge(it, 1);    merge(it, 0);
    }
    int ask_sum(int l, int r) {
        auto ir = split(r + 1), il = split(l);
        int res = 0;
        for (auto it = il; it != ir; it ++ )
            res += (it->r - it->l + 1) % mod * it->val % mod;
        merge(find(r), 1);  merge(find(l), 0);
        return res;
    }
    void add(int l, int r, int val) {
        auto ir = split(r + 1), il = split(l);
        for (auto it = il; it != ir; it ++ )
            it->val = (it->val + val) % mod;
        merge(find(r), 1);  merge(find(l), 0);
    }
    void copy(int l, int r, int l2, int r2) {
        set<ODT_node>::iterator ir1, il1, ir2, il2, mr, ml;
        ir1 = split(r + 1), il1 = split(l);
        vector<ODT_node> tmp;
        for (auto it = il1; it != ir1; it ++ )
            tmp.push_back(*it);
        merge(find(l), 1);  merge(find(r + 1), 0);
        ir2 = split(r2 + 1), il2 = split(l2);
        t.erase(il2,  ir2);
        int eps = l2 - l;
        for (int k = 0, l = tmp.size(); k < l; k ++ ) {
            ODT_node i = tmp[k];    i.l += eps;  i.r += eps;
            t.insert(i);
        }
        merge(find(l2), 1);  merge(find(r2), 0);
    }
    void swap(int l, int r, int l2, int r2) {
        set<ODT_node>::iterator ir1, il1, ir2, il2, mr, ml;
        ir1 = split(r + 1), il1 = split(l);
        vector<ODT_node> tmp1, tmp2;
        for (auto it = il1; it != ir1; it ++ )
            tmp1.push_back(*it); 
        ir2 = split(r2 + 1), il2 = split(l2);
        for (auto it = il2; it != ir2; it ++ )
            tmp2.push_back(*it);
        t.erase(il1, ir1);  t.erase(find(l2), find(r2 + 1));
        int eps = l2 - l;
        for (int k = 0, l = tmp1.size(); k < l; k ++ ) {
            ODT_node i = tmp1[k];    i.l += eps;  i.r += eps;
            t.insert(i);
        }
        for (int k = 0, l = tmp2.size(); k < l; k ++ ) {
            ODT_node i = tmp2[k];    i.l -= eps;  i.r -= eps;
            t.insert(i);
        }
        merge(find(l), 1);  merge(find(l2), 0);
        merge(find(r), 1);  merge(find(r2), 0);
    }
    void reverse(int l, int r) {
        auto ir = split(r + 1), il = split(l);
        vector<ODT_node> tmp;
        for (auto it = il; it != ir; it ++ )
            tmp.push_back(*it);
        t.erase(il, ir);
        for (int k = tmp.size() - 1; k >= 0; k -- ) {
            ODT_node i = tmp[k];
            t.insert({l + r - i.r, l + r - i.l, i.val});
        }
        merge(find(l), 1);  merge(find(r), 0);
    }
}tree;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    tree.build(a, n);

    for (int i = 1, op, l, r, val, l2, r2; i <= m; i ++ ) {
        cin >> op >> l >> r;
        switch (op) {
        case 1:
            cout << tree.ask_sum(l, r) << '\n';
            break;
        case 2:
            cin >> val;
            tree.assign(l, r, val);
            break;
        case 3:
            cin >> val;
            tree.add(l, r, val);
            break;
        case 4:
            cin >> l2 >> r2;
            tree.copy(l, r, l2, r2);
            break;
        case 5:
            cin >> l2 >> r2;
            tree.swap(l, r, l2, r2);
            break;
        case 6:
            tree.reverse(l, r);
        }
    }
    for (int i = 1; i <= n; i ++ )
        cout << tree.ask_sum(i, i) << ' ';
    return 0;
}