The origin of the Kodori tree?

The original name of Kodori tree is Old Driver Tree (ODT), which is a data structure proposed by a CF competition in 2017, because the title background protagonist is "what are you doing at the end of the day? Are you free? Can you save it?" The protagonist of the data structure is cordolly, so the data structure is called cordolly tree.

What is the cordole tree?

Kodori tree is a data structure that stores interval information in an almost violent form. The method is to store several intervals represented by structure through set, and the elements of each interval are the same.

What's the use of the cadoli tree?

As long as it is a question related to interval assignment operation, almost any query about interval information can be processed with Kodori tree

Under what circumstances can I use the Kodori tree without being stuck?

Kodori tree is a beautiful violence. Its beauty is based on the merging operation of intervals, that is, interval assignment. If a group of data is constructed so that it contains almost no interval assignment operation, the Kodori tree will be easily blocked

Therefore, the Kodori tree requires that the topic must have interval assignment operation, and the data has a high degree of randomness

Kodori tree definition

As mentioned earlier, the Kodori tree stores intervals through structures, so we need to write a structure

struct ran{
    int l, r;
    mutable ll v;
    bool operator <(const ran &x)const{//Operator overload for sorting set
        return l < x.l;//It is arranged from small to large at the left end of the interval
    }
};

What is mutable? Why use mutable

mutable keyword defines a mandatory variable

When calling a function, only parameters are often passed, but the operation within the function will not change its actual value. The Kodori tree often involves operations that need to modify v. if it is a general data type, we will add &, but for structures, we need to add mutable when defining.

set<ran>tr;//Definition of Kodori tree

Pre knowledge of set

• Define set: set < ran > st;

• Insert: tr.insert(ran(l, r, v));

  insetr function actually has a return value. It will return a pair < set:: iterator, bool >, and the first value is the iterator of the inserted element

• delete

  • Delete a single element: tr.erase(it); it is the iterator of the element to be deleted
  • Delete the elements of a continuous interval: tr.erase(itl, itr);, The left and right ITR intervals are left and right ltr to be closed

• Two points: tr.lower_bound() returns an iterator

• Iterators: subscripts that are similar to arrays

  It's not very convenient to write, so you can use macro definition: #define it set < ran >:: iterator, and directly It it when you use it; Just do it

Two great artifacts of cordoli

split function

This function is a decomposition function. We need to find the interval of pos from all intervals in set and split it into two intervals, one is [l, pos - 1], the other is [pos, r]. The main purpose is to make POS as the beginning of an interval and return the iterator of this interval

It split(int pos){
    It it = tr.lower_bound({pos, -1, 0});//Find the iterator for the desired pos
    if(it != tr.end() && it->l == pos)return it;//See if the l of this iterator is the required pos. if so, just return it directly
    --it;//If not, it must be in the previous one
    int l = it->l;
    int r = it->r;
    ll v = it->v;
    tr.erase(it);//Let's delete this interval
    tr.insert({l, pos - 1, v});//Re insert two intervals [l, pos - 1], [POS, R]
    return tr.insert({pos, r, v}).first;//Returns the iterator of the interval starting with pos
}

emerge function

If we continue to perform the split function, the number of elements in the set will be in a high range, which will lead to TLE. Therefore, we need an interval merging operation, that is, an operation for interval assignment

void emerge(int l, int r, ll x){
    It itr = split(r + 1), itl = split(l);//Find the iterator position of r+1 first, and then find the iterator position of l
    tr.erase(itl, itr);//Delete this paragraph iterator
    tr.insert({l, r, x});//Reinsert the desired interval
}

You can ask why you want to find r+1. This is because when you delete set, the parameters are closed on the left and open on the right. Therefore, if you want to delete all the intervals of [l, r], itr should point to r+1

E. Physical Education Lessons

Title Description:

There are still n days (numbered from 1 to n) between now and the end of the semester. They are working days at the beginning. Next, the school staff will issue q instructions in turn, and each instruction can be described with three parameters L, R and K:

• If k=1, all days from l to r (including endpoints) become non working days.
• If k=2, all days from l to r (including endpoints) become working days.

Help Alex count the remaining working days after each instruction is issued.

Idea:

For the Kodori board question, you only need to use ans to count the contribution of the answer in real time

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;

struct ran{
    int l, r;
    mutable int v;
    ran(int L, int R = -1, bool V = 0){
        l = L;r = R;v = V;
    };
    bool operator <(const ran &x)const{
        return l < x.l;
    }
};
#define It set<ran>::iterator
set<ran>tr;
ll ans;
It split(int pos){
    It it = tr.lower_bound(ran(pos));
    if(it != tr.end() && it->l == pos)return it;
    --it;
    int l = it->l;
    int r = it->r;
    int v = it->v;
    tr.erase(it);
    tr.insert(ran(l, pos - 1, v));
    return tr.insert(ran(pos, r, v)).first;
}
void emerge(int l, int r, int v){
    It itr = split(r + 1);
    It itl = split(l);
    It it = itl;
    for(;it != itr;++it){
        ans -= it->v * (it->r - it->l + 1);
    }
    tr.erase(itl, itr);
    tr.insert(ran(l, r, v));
    ans += (r - l + 1) * v;
}


void work(){
    cin >> n >> m;
    ans = n;
    tr.insert(ran(1, n, 1));
    for(int i = 1; i <= m; ++i){
        int l, r, v;
        cin >> l >> r >> v;
        emerge(l, r, v - 1);
        cout << ans << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

C. Willem, Chtholly and Seniorious

Title Description:

Please write a strange data structure that supports:

• 1 l r x: add x to all numbers in [l, r] interval
• 2 l r x: change all numbers in [l, r] interval to X
• 3 l r x: output the x-th number after sorting the [l, r] interval from small to large
• 4 l r x y: output the value of the sum modulus y of the power X of each number in the [l, r] interval

In addition, data needs to be generated manually according to seed

Idea:

This question is the origin of the Kodori tree

Operations 1, 3 and 4 are pure violence. Operation 2 is the consolidation interval operation of cortori

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define It set<ran>::iterator
typedef long long ll;
typedef pair <ll,ll> pii;

#define MAX 300000 + 50
int n, m;
ll mod;
ll ar[MAX];
int op, l, r;
ll x;
struct ran{
    int l, r;
    mutable ll v;
    bool operator <(const ran &x)const{
        return l < x.l;
    }
};

set<ran>tr;
It split(int pos){
    It it = tr.lower_bound({pos, -1, 0});
    if(it != tr.end() && it->l == pos)return it;
    --it;
    int l = it->l;
    int r = it->r;
    ll v = it->v;
    tr.erase(it);
    tr.insert({l, pos - 1, v});
    return tr.insert({pos, r, v}).first;
}

void emerge_add(int l, int r, ll x = 1){
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl)itl->v += x;
}

void emerge_bian(int l, int r, ll x = 0){
    It itr = split(r + 1), itl = split(l);
    tr.erase(itl, itr);
    tr.insert({l, r, x});
}

ll get_rank(int l, int r, ll rkn){
    vector<pii>v;
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl)v.push_back(m_p(itl->v, itl->r - itl->l + 1));
    sort(v.begin(), v.end());
    for(auto [vv, len] : v){
        rkn -= len;
        if(rkn <= 0)return vv;
    }
    return 0;
}

ll q_pow(ll a, ll b, ll mod){
    ll ans = 1;
    a %= mod;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

ll get_ans(int l, int r, ll x, ll mod){
    ll ans = 0;
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl){
        ans = (ans + ((ll)(itl->r - itl->l + 1) * q_pow(itl->v, (ll)x, mod)) % mod) % mod;
    }
    return ans;
}


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

void work(){
    cin >> n >> m >> seed >> vmax;
    for(int i = 1; i <= n; ++i){
//        cin >> ar[i];
        ar[i] = (rnd() % vmax) + 1;
        tr.insert({i, i, ar[i]});
    }
    tr.insert({n+1, n+1, 0});
    for(int i = 1; i <= m; ++i){
//        for(auto [l, r, v] : tr){
//            cout << l << ' ' << r << ' '<< v << endl;
//        }
//        cout << endl << endl;
        op = (int)(rnd() % 4) + 1;
        l = (int)(rnd() % n) + 1;
        r = (int)(rnd() % n) + 1;
        if(l > r)swap(l, r);
        if(op == 3)x = (int)(rnd() % (r - l + 1)) + 1;
        else x = (int)(rnd() % vmax) + 1;
//        cin >> op >> l >> r >> x;
        if(op == 1){
            emerge_add(l, r, x);
        }
        else if(op == 2){
            emerge_bian(l, r, x);
        }
        else if(op == 3){
            cout << get_rank(l, r, x) << endl;
        }
        else {
//            cin >> mod;
            mod = rnd() % vmax + 1;
            cout << get_ans(l, r, x, mod) << endl;
        }
    }
    
}


int main(){
    work();
    return 0;
}