刷题记（珂朵莉树/老司机树）

CONTENT: 珂朵莉树/老司机树
DETAIL: 珂朵莉树/老司机树

BB

晚上喝咖啡，还睡了一会儿，然后整个晚上睡不着QAQ，莫名其妙通了个宵QAQ
jjdl（jiajun dl）去年提起过ODT这个东西，莫名神奇！

Introduction

珂朵莉树
https://www.cnblogs.com/yzhang-rp-inf/p/9443659.html

Willem, Chtholly and Seniorious - CodeForces 896C

Description
给定四个操作：区间赋值、区间加、询问区间k大数、询问区间幂之和
保证数据随机
Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    int l, r;
    mutable ll val;
    inline int len() const {
        return r - l + 1;
    }
    bool operator < (const Node& b) const {
        return l < b.l;
    }
};

set<Node> st;

inline ll quickPow(ll a, int b, int MOD) {
    ll ans = 1, base = a;
    while(b) {
        if(b & 1) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        b >>= 1;
    }
    return ans;
}

inline set<Node>::iterator split(int pos) {
    auto it = st.lower_bound(Node{pos, 0, 0});
    if(it != st.end() && it->l == pos) {
        return it;
    }
    --it;
    ll v = it->val;
    int l = it->l, r = it->r;
    st.erase(it);
    st.insert(Node{l, pos - 1, v});
    return st.insert(Node{pos, r, v}).first;
}

inline void assignVal(int l, int r, ll v) {
    auto itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert(Node{l, r, v});
}

inline void add(int l, int r, ll k) {
    auto itr = split(r + 1), itl = split(l);
    for(auto it = itl; it != itr; it++) {
        it->val += k;
    }
}

inline ll pow(int l, int r,int x, int y) {
    auto itr = split(r + 1), itl = split(l);
    ll sum = 0;
    for(auto it = itl; it != itr; it++) {
        sum = (sum + it->len() * quickPow(it->val % y, x, y) % y) % y;
    }
    return sum;
}

inline ll kth(int l, int r, int k) {
    auto itr = split(r + 1), itl = split(l);
    vector<pair<ll, int> > vec;
    for(auto it = itl; it != itr; it++) {
        vec.emplace_back(make_pair(it->val, it->len()));
    }
    sort(vec.begin(), vec.end());

    for(auto ele : vec) {
        k -= ele.second;
        if(k <= 0) {
            return ele.first;
        }
    }
    return -1;
}

int seed;
inline int rnd() {
    int ret = seed;
    seed = ((ll)seed * 7 + 13) % 1000000007;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, vmax;
    while(cin >> n >> m >> seed >> vmax) {
        st.clear();
        for(int i = 1; i <= n; i++) {
            st.emplace(Node{i, i, rnd() % vmax + 1});
        }
        for(int i = 1; i <= m; i++) {
            int op = (rnd() % 4) + 1;
            int l = (rnd() % n) + 1;
            int r = (rnd() % n) + 1;
            int x, y;
            if (l > r) {
                swap(l, r);
            }
            if (op == 3)
                x = (rnd() % (r - l + 1)) + 1;
            else
                x = (rnd() % vmax) + 1;
            if (op == 4)
                y = (rnd() % vmax) + 1;

            if(op == 1) {
                add(l, r, x);
            } else if(op == 2) {
                assignVal(l, r, x);
            } else if(op == 3) {
                cout << kth(l, r, x) << "\n";
            } else {
                cout << pow(l, r, x, y) << "\n";
            }
        }
        cout.flush();
    }
}

[SCOI2010]序列操作 - luogu P2572

Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
Sample Input

10
0 0 1 1 0 1 0 1 1
0 2
0 5
2 2
0 4
3 6
3 7
2 8
0 5
5 6
3 9

Sample Output

Solution
本题摆明了线段树，不过因为数据太水ODT可以过！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    int l, r;
    mutable int val;
    inline int len() const {
        return r - l + 1;
    }
    bool operator < (const Node& b) const {
        return l < b.l;
    }
};

set<Node> st;

inline set<Node>::iterator split(int pos) {
    auto it = st.lower_bound(Node{pos, 0, 0});
    if(it != st.end() && it->l == pos) {
        return it;
    }
    --it;
    ll v = it->val;
    int l = it->l, r = it->r;
    st.erase(it);
    st.insert(Node{l, pos - 1, v});
    return st.insert(Node{pos, r, v}).first;
}

inline void assignVal(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert(Node{l, r, v});
}

inline void reverse(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    for(auto it = itl; it != itr; it++) {
        it->val ^= 1;
    }
}

inline int sum(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    int res = 0;
    for(auto it = itl; it != itr; it++) {
        res += (it->val == 1) * it->len();
    }
    return res;
}


inline int calc(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    int res = 0, cnt = 0;
    for(auto it = itl; it != itr; it++) {
        if(it->val) {
            cnt += it->len();
        } else {
            cnt = 0;
        }
        res = max(res, cnt);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    while(cin >> n >> m) {
        st.clear();
        for(int i = 1, val; i <= n; i++) {
            cin >> val;
            st.emplace(Node{i, i, val});
        }

        while(m--) {
            int op, l, r;
            cin >> op >> l >> r;
            l++;
            r++;
            switch(op) {
            case 0:
            case 1:
                assignVal(l, r, op);
                break;
            case 2:
                reverse(l, r);
                break;
            case 3:
                cout << sum(l, r) << "\n";
                break;
            case 4:
                cout << calc(l, r) << "\n";
                break;
            }
        }
        cout.flush();
    }
}