A brief talk on cordola tree

Kodori tree

  Kodori is the happiest girl in the world qwq！！！

About her name

  The origin is here ：C. Willem, Chtholly and Seniorious

  Of course , $luogu$ It's the same question on the paper ：C. Willem, Chtholly and Seniorious

  Simply put, it lets you design a data structure , You can do the following ：

1. Add a number to all the numbers in the interval
2. Change all numbers in the interval to $x$
3. Find the interval number $k$ Small
4. Output... For each number in the interval $k$ Power sum module $p$, That is to say $(\sum _{i=l}^r{a}_i^x)\mathrm{m}\mathrm{o}\mathrm{d}p$

  And the data of this problem is guaranteed to be random .

  And this problem is the first one with Kodori tree Is the problem of positive solution , And the title of this problem is 《 What are you doing at the end of the day ？ Are you free ？ Can you save ？》 In the background of the heroine cortori , So this data structure is called Kodori tree 了 .

Algorithm analysis

  See this topic , All we think of are segment trees , Tree array , The data structure of classical maintenance interval problem such as block . However, it seems that several operations in this problem are not easy to maintain with these normal data structures , So we need to introduce such a mysterious data structure .

  First , We can clearly notice the The data is guaranteed to be random Because I made this sentence bold (bushi . And there is an operation called "all the trees in the interval become..." $x$ （ Later, we call this operation interval flattening ）, With this operation , The complexity of the Kodori tree is guaranteed .

Some properties

  Why do you say that , This requires us to look at some properties of the data when the data is random .

  First of all, let's consider , Randomly select two endpoints in an interval $l,r$ What is the expected length of the selected interval . Suppose the interval length is $n$, Now we have $\frac{1}{n}$ There is a chance that $l=L$, And then there is $\frac{1}{n}$ The probability of $r=R$, So the contribution to expectation this time is $\frac{1}{n^2}|R-L+1|$, So the expected length is ：

$$\begin{array}{rl}E=& \frac{1}{n^2}\sum _{l=1}^n\sum _{r=1}^n|r-l+1|\\ =& \frac{1}{n^2}\left(\sum _{l=1}^n\sum _{r=1}^{l-1}|r-l+1|+\sum _{l=1}^n\sum _{r=l}^n|r-l+1|\right)\\ =& \frac{1}{n^2}\left(\sum _{l=1}^n\sum _{r=1}^{l-1}(l-r-1)+\sum _{l=1}^n\sum _{r=l}^n(r-l+1)\right)\\ =& \frac{1}{n^2}\left(\sum _{l=1}^n\sum _{r=1}^{l-1}l-\sum _{l=1}^n\sum _{r=1}^{l-1}r-\sum _{l=1}^n\sum _{r=1}^{l-1}1+\sum _{l=1}^n\sum _{r=l}^{n}r-\sum _{l=1}^n\sum _{r=l}^{n}l+\sum _{l=1}^n\sum _{r=l}^{n}1\right)\\ =& \frac{1}{n^2}\left(\sum _{l=1}^{n}l(l-1)-\sum _{l=1}^n\frac{1}{2}l(l-1)-\sum _{l=1}^n(l-1)+\sum _{l=1}^n\frac{1}{2}(l+n)(n-l+1)-\sum _{l=1}^n(n-l+1)l+\sum _{l=1}^n(n-l+1)\right)\\ =& \frac{1}{n^2}\left(\frac{1}{2}\sum _{l=1}^n(l-1{)}^2+\frac{1}{2}\sum _{l=1}^n(n-l+1{)}^2\right)=\frac{1}{2n^2}\left(\sum _{l=0}^{n-1}{l}^2+\sum _{l=1}^n{l}^2\right)=\frac{1}{2n^2}\left(2\sum _{l=1}^n{l}^2-n^2\right)=\frac{1}{n^2}\sum _{l=1}^n{l}^2-\frac{1}{2}\\ =& \frac{n(n+1)(2n+1)}{6n^2}-\frac{1}{2}=\frac{2n^2+3n+1}{6n}-\frac{1}{2}=\frac{n}{3}+\frac{1}{6n}\\ \approx & \frac{1}{3}n\end{array}$$

  in other words , Each interval flattening we expect will cover $\frac{1}{3}$ The whole range of , This will make a large part of the numbers the same . So let's consider recording a continuous paragraph with the same number as a point （ Each point in the code will record a $l,r,val$, Respectively represent the same value of the left endpoint, the right endpoint and all numbers in this point ）, Let's calculate the expected number of points after many interval flattening .

  Obviously, we can guess that the number of points should be $O(\log n)$ Grade , But proving this is a bit of a hassle .

  We ask for the expected number of points , We first need to prove a lemma ： Make $p_j$ Indicates that the subscript is $j$ The number of is now the endpoint of a point and is in progress $k$ The probability that the sub interval is still the endpoint of a certain point after flattening , So there are $\frac{1}{n}\sum _{j=1}^n=O(\frac{1}{k})$.

  obviously , Each interval leveling operation does not cover a point $j$ The probability of ：

$$\sqrt[k]{p_j}=\frac{(j-1{)}^2+(n-j{)}^2}{n^2}$$

  That is to say, both points are selected in $j$ The probability before the point plus two points is selected at $j$ Probability after point , Then the formula to be proved above can be written as ：

$$\frac{1}{n}\sum _{j=1}^n=\frac{1}{n}\sum _{j=1}^n\frac{(j-1{)}^2+(n-j{)}^2}{n^2}$$

  Change a dollar , Make $x=\frac{j}{n}$, There is ：

$$\begin{array}{rl}{p}_j=& (\frac{j^2-2j+1}{n^2}+\frac{n^2+j^2-2nj}{n^2}{)}^k\\ =& (x^2-\frac{2}{n}x+\frac{1}{n^2}+1+x^2-2x{)}^k\\ =& (x^2-2x+1+x^2-\frac{2j-1}{n^2}{)}^k\\ \le & (x^2+(x-1{)}^2{)}^k\end{array}$$

  Bring it into the whole equation , Namely ：

$$\frac{1}{n}\sum _{j=1}^n{p}_j\le \sum _{j=1}^n(x^2+(x-1{)}^2{)}^k\approx {\int }_0^1(x^2+(x-1{)}^2{)}^{k}dx$$

  Then you can use a calculator or manual integration , So we can get the upper bound of this equation $O(\frac{1}{k})$.

  With this formula , We can know that the probability that each point in all the initial endpoints will still exist in the end is, on average $O(\frac{1}{k})$. With this, we can naturally deduce the interval expectation points ：

$$E(m)=O(n\cdot \frac{1}{k}+\sum _{i=1}^k\frac{1}{i})=O(\frac{n}{k}+\log k)$$

  That is to say, there was $n$ A little bit , The probability that each point will still exist in the end is $\frac{1}{k}$, Then the expected number of these points is $\frac{n}{k}$, Then on the penultimate $i$ New... Will be created in this operation $O(1)$ A little bit , So these points are in the rest $i$ The probability of remaining after the first operation is $O(\frac{1}{i})$, So the contribution of the new point is $\sum _{i=1}^k\frac{1}{i}$.

  And then it's over ！！！

  To test whether our proof is correct , We can write a piece of code to verify ：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read() 
#define MAXN 100100000
#define MOD 1000000007

struct Tnode{
    
	int l, r;
	mutable int v;
	Tnode(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {
    }
	bool operator < (const Tnode &rhs) const {
     return l < rhs.l; }
};
int n = 0;
int a[MAXN] = {
     0 };
set<Tnode> s;

set<Tnode> :: iterator split(int pos){
    
	set<Tnode> :: iterator it = s.lower_bound(Tnode(pos));
	if(it != s.end() and it->l == pos) return it;
	it--;
	if(it->r < pos) return s.end();
	int l = it->l, r = it->r, v = it->v;
	s.erase(it);
	s.insert(Tnode(l, pos - 1, v));
	return s.insert(Tnode(pos, r, v)).first;
}

void assign(int l, int r, int x){
    
	set<Tnode> :: iterator ir = split(r + 1), il = split(l);
	s.erase(il, ir);
	s.insert(Tnode(l, r, x));
}

signed main(){
    
	n = 1000000; srand(time(0));
	for(int i = 1; i <= n; i++){
    
		a[i] = rand() * rand() % n + 1;
		s.insert(Tnode(i, i, a[i]));
	}
	for(int i = 1; i <= n; i++){
    
		int l = rand() * rand() % n + 1;
		int r = rand() * rand() % n + 1;
		int x = rand() * rand() % n + 1;
		if(l > r) swap(l, r);
		assign(l, r, x);
	}
	cout << s.size() << '\n';
	return 0;
}

  In code $split()$ and $assign()$ The working principle of is described in detail below , I won't repeat it here .

  We use this code to run $10$ Average the times , stay $n=1e6$ when , The number of points is stable at $20\sim 30$ Between , It is in good agreement with the theoretical value , This further proves that our proof is correct .

Now let's look at the operation

  Now we know that our points are $O(\log n)$ Level , Now we can naturally think of using these points to partition , If we can make the time complexity of the operation of each section as $O(1)$ Then we can do $O(n\log n)$ Time to solve this problem （ But in fact, the complexity of maintaining a single operation here is $O(\log n)$ Of ）. Specifically, we maintain ：

  First create a structure ：

struct Tnode{
    
	int l, r;
	mutable int v;
	Tnode(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {
    }
	bool operator < (const Tnode &rhs) const {
     return l < rhs.l; }
};

  One of this structure “ spot ” There are three data in $l,r$ and $v$, It respectively represents the left end point and the right end point in this continuous interval , The same number as all the numbers in this paragraph . And then here's $mutable$ Keyword means that we can directly modify the inserted $set$ The elements of the $v$ value , Instead of taking the element out and adding it back $set$.

  And then another one $set$ To maintain the entire section ：

set<Tnode> s;

  In this way, we have an empty Kodori tree . Yes , It's that simple qwq.

  Then there are several important operations .

split

  This operation allows us to include the original point $pos$ The range of $[l,r]$ Divide into $[l,pos-1]$ and $[pos,r]$ These two intervals , And return the iterator of the latter .

  Let's use $lower\_bound()$ Function in $set$ It is found that the position of the left end point is greater than or equal to pos The node of . If the left endpoint of this node is exactly pos, Then we don't need to split , Go straight back to . If its left endpoint position is not $pos$, Then it must be greater than $pos$, Contains the location pos The node of is the previous node ,$it-=1$. The rest is easy , Violent split and then insert . Don't forget to return the value .

set<Tnode> :: iterator split(int pos){
    
	set<Tnode> :: iterator it = s.lower_bound(Tnode(pos));        //  Find the left endpoint greater than or equal to pos The range of 
	if(it != s.end() and it->l == pos) return it;                 //  If the left end of this point is pos You don't have to split Just go straight back 
	it--;                                                         //  The left endpoint is not pos That's more than pos, contain pos It must be the previous point 
	if(it->r < pos) return s.end();
	int l = it->l, r = it->r, v = it->v;
	s.erase(it);                                                  //  Violent deletion 
	s.insert(Tnode(l, pos - 1, v));                               //  Add a little violence 
	return s.insert(Tnode(pos, r, v)).first;                      //  Violence plus points plus returns 
}

assign

  This is the most important operation to reduce complexity in the Kodori tree ： Interval leveling . Because the implementation of this operation is too simple , So just look at the code ：

void assign(int l, int r, int x){
    
	set<Tnode> :: iterator ir = split(r + 1), il = split(l);        //  hold l Between people split Into a whole paragraph 
	s.erase(il, ir);                                                //  Delete all the nodes in the middle 
	s.insert(Tnode(l, r, x));                                       //  Create a new node and insert it 
}

  The rest is violence and fragmentation , Let's not go into details . The complete code is posted below ：

  End of the flower ！！！

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read() 
#define MAXN 100100
#define MOD 1000000007

struct Tnode{
    
	
	int l, r;
	mutable int v;
	
	Tnode(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {
    }
	
	bool operator < (const Tnode &rhs) const {
     return l < rhs.l; }
	
};

int n = 0; int m = 0;
int seed = 0; int vmax = 0;
int a[MAXN] = {
     0 };

set<Tnode> s;

set<Tnode> :: iterator split(int pos){
    
	set<Tnode> :: iterator it = s.lower_bound(Tnode(pos));
	if(it != s.end() and it->l == pos) return it;
	it--;
	if(it->r < pos) return s.end();
	int l = it->l, r = it->r, v = it->v;
	s.erase(it);
	s.insert(Tnode(l, pos - 1, v));
	return s.insert(Tnode(pos, r, v)).first;
}

void add(int l, int r, int x) {
    
    set<Tnode>::iterator ir = split(r + 1), il = split(l);
    for (set<Tnode>::iterator it = il; it != ir; ++it) it->v += x;
}

void assign(int l, int r, int x){
    
	set<Tnode> :: iterator ir = split(r + 1), il = split(l);
	s.erase(il, ir);
	s.insert(Tnode(l, r, x));
}

struct Trank{
    
	
	int num, cnt;
	
	bool operator < (const Trank & rhs) const {
     return num < rhs.num; }
	
	Trank(int num, int cnt) : num(num), cnt(cnt) {
    }
	
};

int rk(int l, int r, int x){
    
	set<Tnode> :: iterator ir = split(r + 1), il = split(l);
	vector<Trank> v;
	for(set<Tnode> :: iterator i = il; i != ir; i++)
		v.push_back(Trank(i->v, i->r - i->l + 1));
	sort(v.begin(), v.end());
	int i = 0;
	for(i = 0; i < v.size(); i++)
		if(v[i].cnt < x) x -= v[i].cnt;
		else break;
	return v[i].num;
}

int power(int x, int y, int p){
    
	int r = 1, base = x % p;
	while(y){
    
		if(y & 1) r = r * base % p;
		base = base * base % p;
		y >>= 1;
	}
	return r;
}

int calp(int l, int r, int x, int y){
    
	set<Tnode> :: iterator ir = split(r + 1), il = split(l);
	int ans = 0;
	for(set<Tnode> :: iterator i = il; i != ir; i++)
		ans = (ans + power(i->v, x, y) * (i->r - i->l + 1) % y) % y;
	return ans; 
}

int rd(){
    
	int res = seed;
	seed = (seed * 7 + 13) % MOD;
	return res;
}

signed main(){
    
	cin >> n >> m >> seed >> vmax;
	for(int i = 1; i <= n; i++){
    
		a[i] = (rd() % vmax) + 1;
		s.insert(Tnode(i, i, a[i]));
	}
	for(int i = 1; i <= m; i++){
    
		int op = (rd() % 4) + 1;
		int  l = (rd() % n) + 1;
		int  r = (rd() % n) + 1;
		if(l > r) swap(l, r);
		if(op == 1){
    
			int x = (rd() % vmax) + 1;
			add(l, r, x);
		}
		else if(op == 2){
    
			int x = (rd() % vmax) + 1;
			assign(l, r, x);
		}
		else if(op == 3){
    
			int x = (rd() % (r - l + 1)) + 1;
			cout << rk(l, r, x) << '\n';
		}
		else{
    
			int x = (rd() % vmax) + 1;
			int y = (rd() % vmax) + 1;
			cout << calp(l, r, x, y) << '\n';
		}
	}
	return 0;
}