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 xth 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; }