珂朵莉树

引入

珂朵莉树 (Chtholly Tree)，又名老司机树 (Old Driver Tree)。起源于CF896C。

这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。

前置

需要了解 STL 的 set 的基本用法。比如：

insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
erase(x) 删除值为 x 的所有元素，返回删除元素的个数。
erase(pos) 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last) 删除迭代器在 \([first,last]\) 范围内的所有元素。
clear() 清空 set。

解决什么问题

通常是维护序列的操作，使一段区间内的东西变得一样，注意一定是数据随机。

一般的情况下只要是有区间赋值操作，都可以骗分，但是数据不随机的话复杂度是不正确的。

对于 add，assign，sum 操作，用 set 实现的珂朵莉树的复杂度为 \(O(n \log \log n)\)，用链表实现的复杂度为 \(O(n\log n)\)。

操作

下面以模板题来介绍。

Willem, Chtholly and Seniorious - 洛谷

给定 \(n\) 个数， \(m\) 次操作 \((n,m\le 10^5)\)。

支持：

区间加
区间赋值
区间第 \(k\) 小
区间幂次和

珂朵莉树的核心思想就是用一个结构体来存放一个值相同的子段信息，以此在区间的操作上降低复杂度，因为有区间赋值的操作，所以让他的复杂度降低了不少。

我们首先来看一下珂朵莉树如何存储信息。

结点存储

struct node
{
    int l, r;
    mutable int v;
    node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}//新建一个变量，如果只有L，R默认为-1，V默认为0
    bool operator < (const node &o) const{return l < o.l;}//重载运算符，按左端点从小到大排序
};
set<node> s;

可以看到里面有一个 mutable，他的意思是“可修改的”，因为在 set 里面的元素是不能直接修改的，我们在加上 mutable 后就可以不取出插入完成修改，而是可以直接修改里面的 \(v\) 值。

\(l,r\) 就是表示当前点存放的是区间 \([l,r]\) 的信息。

分裂区间

珂朵莉树的各种操作都是基于这个分裂区间的操作，因为我们有可能修改的区间左右端点是在一个结点当中包含的，比如要修改 \([3,4]\)，但是我们只有 \([1,6]\)，这个时候我们就需要把区间分成 \([1,2][3,4][5,6]\) 了。

假设我们需要分出一个以 \(x\) 为左端点的区间。

我们在实现的过程中，可以用 set 的 lower_bound() 函数来找到第一个左端点不大于 \(x\) 的区间结点，然后特判一下：如果当前结点存的区间左端点正好是 \(x\)，那么就不用分了，直接返回就好了；否则，我们找到前面一个区间，因为 \(x\) 肯定是包含在前一个区间，然后我们把他的信息 \((l,r,v)\) 都拿出来，防止等等删除后会出现错误，然后删除当前区间，再把 \((l,x- 1,v)\) 给插入，然后插入 \((x,r,v)\)，这个时候我们就可以返回后面区间的迭代器了，由于 insert 后返回的是一个 pair 类型，first 是当前元素的迭代器，而 second 是一个 bool 类型的变量，表示此次操作是否成功，所以我们这样写：

#define IT set<node>::iterator
IT split(int p)
{
    IT it = s.lower_bound(node(p));//找到第一个左端点不小于p的元素
    if(it != s.end() && it -> l == p) return it;//如果不是最后一个元素，并且左端点就是p就不用分裂直接返回
    it --;//前移一个单位
    int L = it -> l, R = it -> r, V = it -> v;//取出所有的元素
    s.erase(it);//将当前区间删除掉
    s.insert(node(L, p - 1, V));//插入分裂的左半区间
    return s.insert(node(p, R, V)).first;//插入分裂的右半区间
}

注意：使用 split 函数的时候一定要先分裂 \(r + 1\)，再分裂 \(l\)，不然有可能会 RE。

区间加

我们上面说过 set 内的元素存放的都是一个区间，每个区间内的值都是一样的，所以我们在进行区间加的时候，我们先把左右端点的区间分裂出来，然后在直接对于我们得到的两个迭代器进行遍历，把中间所有的元素都直接加上 \(val\) 就好了。

inline void add(int l, int r, int val)
{
    IT itr = split(r + 1), itl = split(l);//分裂区间
    for(; itl != itr; itl ++) itl -> v += val;//暴力修改
    return ;
}

区间覆盖

也就是区间赋值。

我们上面进行了多次修改后可能所有的元素 \(l=r\) 了，也就是基本都是一个元素只代表一个点了，这样复杂度就成了 \(O(nm)\) 的了，但是由于有区间赋值的操作，我们可以把当前修改的区间直接变成一个元素，然后插进 set 里，这样在随机的数据下珂朵莉树的复杂度就变优了。

inline void assign_val(int l, int r, int val)
{
    IT itr = split(r + 1), itl = split(l);//分裂区间
    s.erase(itl, itr);//暴力删除
    s.insert(node(l, r, val));//插入新区间
}

区间第 K 大的值

我们可以开一个 vector 然后对其进行排序，然后遍历每一个元素，来找到第 \(k\) 大的元素。

inline int ranks(int l, int r, int k)
{
    vector<pair<int, int> > vp;
    IT itr = split(r + 1), itl = split(l);//分裂区间
    for(; itl != itr; itl ++) vp.push_back(pair<int, int>(itl -> v, itl -> r - itl -> l + 1));//放入vector，值，区间内数的个数
    sort(vp.begin(), vp.end());//从小到大排序
    for(vector<pair<int, int> >::iterator it = vp.begin(); it != vp.end(); it ++)//遍历
    {
        k -= it -> second;//减去数的个数
        if(k <= 0) return it -> first;//返回值
    }
}

区间求次幂和

我们可以直接遍历，然后计算区间内的数的个数，然后直接求和。

inline int sum(int l, int r, int ex, int mod)
{
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for(; itl != itr; itl ++) res = (res + (int)(itl -> r - itl -> l + 1) * ksm(itl -> v, ex, mod)) % mod;
    return res;
}

模板题完整代码

#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define P 1000000007
#define N 1000100

using namespace std;

int n, m, seed, vmax, a[N];
struct node
{
    int l, r;
    mutable int v;
    node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}//新建一个变量，如果只有L，R默认为-1，V默认为0
    bool operator < (const node &o) const{return l < o.l;}//重载运算符，按左端点从小到大排序
};
set<node> s;

inline int ksm(int a, int b, int mod)//取模快速幂
{
    int res = 1;
    int ans = a % mod;
    while(b)
    {
        if(b & 1) res = res * ans % mod;
        ans = ans * ans % mod;
        b >>= 1;
    }
    return res;
}

IT split(int p)
{
    IT it = s.lower_bound(node(p));//找到第一个左端点不小于p的元素
    if(it != s.end() && it -> l == p) return it;//如果不是最后一个元素，并且左端点就是p就不用分裂直接返回
    it --;//前移一个单位
    int L = it -> l, R = it -> r, V = it -> v;//取出所有的元素
    s.erase(it);//将当前区间删除掉
    s.insert(node(L, p - 1, V));//插入分裂的左半区间
    return s.insert(node(p, R, V)).first;//插入分裂的右半区间
}

inline void add(int l, int r, int val)
{
    IT itr = split(r + 1), itl = split(l);//分裂区间
    for(; itl != itr; itl ++) itl -> v += val;//暴力修改
    return ;
}

inline void assign_val(int l, int r, int val)
{
    IT itr = split(r + 1), itl = split(l);//分裂区间
    s.erase(itl, itr);//暴力删除
    s.insert(node(l, r, val));//插入新区间
}

inline int ranks(int l, int r, int k)
{
    vector<pair<int, int> > vp;
    IT itr = split(r + 1), itl = split(l);//分裂区间
    for(; itl != itr; itl ++) vp.push_back(pair<int, int>(itl -> v, itl -> r - itl -> l + 1));//放入vector，值，区间内数的个数
    sort(vp.begin(), vp.end());//从小到大排序
    for(vector<pair<int, int> >::iterator it = vp.begin(); it != vp.end(); it ++)//遍历
    {
        k -= it -> second;//减去数的个数
        if(k <= 0) return it -> first;//返回值
    }
}

inline int sum(int l, int r, int ex, int mod)
{
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for(; itl != itr; itl ++) res = (res + (int)(itl -> r - itl -> l + 1) * ksm(itl -> v, ex, mod)) % mod;
    return res;
}

inline int rnd()
{
    int res = seed;
    seed = (seed * 7 + 13) % P;
    return res;
}

signed main()
{
    cin >> n >> m >> seed >> vmax;
    for(int i = 1; i <= n; i ++)
    {
        a[i] = (rnd() % vmax) + 1;
        s.insert(node(i, i, a[i]));
    }
    s.insert(node(n + 1, n + 1, 0));
    for(int i = 1; i <= m; i ++)
    {
        int op = (rnd() % 4) + 1;
        int l = (rnd() % n) + 1;
        int r = (rnd() % n) + 1;
        if(l > r) swap(l, r);
        int x, y;
        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) assign_val(l, r, x);
        else if(op == 3) cout << ranks(l, r, x) << endl;
        else cout << sum(l, r, x, y) << endl;
    }
    return 0;
}

题目练习

大多数没写数据随机的题目都把 ODT 卡掉了 ┭┮﹏┭┮

luoguP4979

先说好 ODT 被卡了啊。

对于 A 操作就直接 assign 即可。

对于 B 操作，我们可以先判断区间内的元素是不是一样，然后再去判断左右端点是不是在 \(1\) 或者 \(n\) 上，有的话就跳过后面的判断，直接输出；后面用 split 函数分出来 \(r + 1,l - 1\) 判断一下两个的值是不是相同就好了。


#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 1000100

using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}

int n, m;
char a[N];
struct node
{
    int l, r;
    mutable char s;
    node(int L, int R = -1, char S = ' ') : l(L), r(R), s(S) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r;
    char S = it -> s;
    s.erase(it);
    s.insert(node(L, p - 1, S));
    return s.insert(node(p, R, S)).first;
}

inline void assign_val(int l, int r, char val)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
    return ;
}

inline int ask(int l, int r)
{
    int ff = 1;
    IT itr = split(r + 1), itl = split(l);
    char S = itl -> s;
    for(; itl != itr; itl ++) if(itl -> s != S) ff = 0;
    if(ff == 1) return 1;
    else return 0;
}

signed main()
{
    n = read();
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s.insert(node(i, i, a[i]));
    }
    m = read();
    for(int i = 1; i <= m; i ++)
    {
        char op, val;
        cin >> op;
        int l = read(), r = read();
        if(op == 'A') cin >> val, assign_val(l, r, val);
        if(op == 'B')
        {
            int flag = ask(l, r);
            if(!flag) {cout << "No" << '\n'; continue;}
            if(l == 1 || l == n || r == 1 || r == n) {cout << "Yes" << endl; continue;}
            IT itr = split(r + 1), itl = split(l - 1);
            if(itl -> s != itr -> s) cout << "Yes" << '\n';
            else cout << "No" << '\n';
        }
    }
    return 0;
}

P1204

我们把所有的点分为两个值 \(1\) 代表当前时间有人挤奶，反之则为 \(0\)，然后我们对于每一个时间段看成区间赋值就好了。

注意从挤奶的第一个人的开始时间算起，不然会 WA 前三个。

而且首先别忘了插入一个初始区间。

#include <bits/stdc++.h>

#define IT set<node>::iterator
#define INF INT_MAX
#define int long long
#define N 1000100

using namespace std;

int n, m, maxn, minn = INF, x[N], y[N];

struct node
{
    int l, r;
    mutable int v;
    node(int L, int R = -1, int val = 0):l(L), r(R), v(val) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r, V = it -> v;
    s.erase(it);
    s.insert(node(L, p - 1, V));
    return s.insert(node(p, R, V)).first;
}

inline void assign(int l, int r, int v)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
    return ;
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> x[i] >> y[i], maxn = max(maxn, y[i]), minn = min(minn, x[i]);
    s.insert(node(minn, maxn, 0));
    for(int i = 1; i <= n; i ++)
        assign(x[i], y[i] - 1, 1);
    IT it = s.begin();
    int mx0 = 0, mx1 = 0, t1 = 0, t0 = 0, last = 0;
    for(; it != s.end(); it ++)
    {
        int len = (it -> r - it -> l + 1);
        // cout << "len : " << len << "  v: " << it -> v << endl;
        if(it -> v == 0 && last == 0) t0 += len;
        if(it -> v == 0 && last == 1) mx1 = max(mx1, t1), last = t1 = 0, t0 += len;
        if(it -> v == 1 && last == 1) t1 += len;
        if(it -> v == 1 && last == 0) mx0 = max(mx0, t0), last = 1, t0 = 0, t1 += len;
    }
    cout << mx1 << " " << mx0 << endl;
    return 0;
}

P3740

我们把每一张海报看作是一个区间覆盖操作，然后我们直接暴力 ODT。

注意一开始要插入一个 \([1,n]\) 的区间，然后最后遍历，开个 map 存放一下那个没出现过就好了。

#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 1000100

using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}

unordered_map<int, int> mp;
int n, m, ans;
struct node
{
    int l, r;
    mutable int val;
    node(int L, int R = -1, int v = 0): l(L), r(R), val(v) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r, val = it -> val;
    s.erase(it);
    s.insert(node(L, p - 1, val));
    return s.insert(node(p, R, val)).first;
}

inline void assign(int l, int r, int v)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
    return ;
}

signed main()
{
    n = read(), m = read();
    // cout << "cao" << endl;
    s.insert(node(1, n, 0));
    for(int i = 1; i <= m; i ++)
    {
        int l = read(), r = read();
        assign(l, r, i);
    }
    int last = 0;
    IT it = s.begin();
    for(; it != s.end(); it ++)
    {
        int c = it -> val;
        if(!mp[c]) ans ++, mp[c] = 1;
    }
    cout << ans - 1 << endl;
    return 0;
}

CF343D

一共有三种操作：

修改整个子树权值。
修改根节点到某一点路径上的所有点权。
查询某个点的值。

我们想到处理树上问题可以用树剖转化为序列，然后进行区间操作。

我们先用树剖两个 DFS 处理出所有的点的信息如表示 DFS 序的 \(dfn\) 数组，表示子树大小的 \(siz\) 数组等，然后就利用 DFS 序 \(dfn\) 数组进行区间操作。

对于操作一，我们直接 assign 从 \(dfn[x]\) 到 \(dfn[x] + siz[x] - 1\) 区间赋值为 \(1\)。

对于操作二，我们直接从当前点不断跳链头，修改当前点到链头中间的所有值。

对于操作三，直接查询即可。


#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 500005

using namespace std;

inline int read(){int f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}

int n, m, head[N], cnt = 0;
struct edge{int v, next;} e[N << 1];
int siz[N], dfn[N], son[N], dep[N], fa[N], top[N], tot = 0;
struct node
{
    int l, r;
    mutable int s;
    node(int L, int R = -1, int S = 0): l(L), r(R), s(S) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

inline void add(int u, int v) {e[++ cnt] = (edge){v, head[u]}, head[u] = cnt;}

inline void dfs1(int x, int f)
{
	dep[x] = dep[f] + 1;
	fa[x] = f;
    siz[x] = 1;
    for(int i = head[x]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(!dep[v])
        {
            dfs1(v, x);
            siz[x] += siz[v];
            if(siz[v] > siz[son[x]]) son[x] = v;
        }
    }
	return ;
}

inline void dfs2(int x, int tp)
{
    dfn[x] = ++ tot;
    top[x] = tp;
    if(son[x]) dfs2(son[x], tp);
    for(int i = head[x]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(v != fa[x] && v != son[x]) dfs2(v, v);
    }
}

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if (it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r;
    int S = it -> s;
    s.erase(it);
    s.insert(node(L, p - 1, S));
    return s.insert(node(p, R, S)).first;
}

inline void assign(int l, int r, int v)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
	return ;
}

inline void query(int p)
{
    IT it = split(p);
    cout << it -> s << endl;
	return ;
}

inline void cal(int p)
{
    int fpos = top[p];
    while(fpos != 1)
    {
        assign(dfn[fpos], dfn[p], 0);
        p = fa[fpos], fpos = top[p];
    }
    assign(dfn[1], dfn[p], 0);
	return ;
}

signed main()
{
    n = read();
    for(int i = 1; i < n; i ++)
    {
        int u = read(), v = read();
        add(u, v);
		add(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    s.insert(node(0, 500001, 0));
    int m = read();
    while(m --)
    {
        int op = read(), p = read();
        if(op == 1) assign(dfn[p], dfn[p] + siz[p] - 1, 1);
        if(op == 2) cal(p);
        if(op == 3) query(dfn[p]);
    }
    return 0;
}

P4344

三种操作：

区间赋值为 \(0\)
取出一个区间的 \(1\) 修补另一个区间的 \(0\)
查询区间内最长的连续 \(1\) 的长度。

对于操作一就是 ODT 的基本操作，直接赋值。

对于操作二，我们直接统计第一个区间内 \(1\) 的个数，然后再遍历第二个区间直接赋值。

对于操作三，我们直接暴力统计就好。


#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 1000100

using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}

int n, m;
struct node
{
    int l, r;
    mutable int v;
    node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r, V = it -> v;
    s.erase(it);
    s.insert(node(L, p - 1, V));
    return s.insert(node(p, R, V)).first;
}

inline void assign(int l, int r, int v)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
    return ;
}

inline void change(int l1, int r1, int l2, int r2)
{
    int res = 0;
    IT itr = split(r1 + 1), itl = split(l1), it = itl;
    for(; itl != itr; itl ++)
        if(itl -> v == 1) res += (itl -> r - itl -> l + 1);
    s.erase(it, itr);
    s.insert(node(l1, r1, 0));
    if(!res) return ;
    itr = split(r2 + 1), itl = split(l2), it = itl;
    if(res >= r2 - l2 + 1)
    {
        s.erase(itl, itr);
        s.insert(node(l2, r2, 1));
        return ;
    }
    for(; itl != itr; itl ++)
    {
        if(itl -> v == 0)
        {
            res -= itl -> r - itl -> l + 1;
            if(res < 0) {assign(itl -> l, itl -> r + res, 1); break;}
            else itl -> v = 1;
        }
    }
    return ;
}

inline int ask(int l, int r)
{
    IT itr = split(r + 1), itl = split(l);
    int res = 0, t = 0;
    for(; itl != itr; itl ++)
    {
        if(itl -> v == 0) t += itl -> r - itl -> l + 1;
        else res = max(res, t), t = 0;
    }
    return max(res, t);
}

signed main()
{
    n = read(), m = read();
    s.insert(node(1, n, 1));
    for(int i = 1; i <= m; i ++)
    {
        int op = read(), l = read(), r = read();
        if(op == 0) assign(l, r, 0);
        if(op == 1) {int l2 = read(), r2 = read(); change(l, r, l2, r2);}
        if(op == 2) cout << ask(l, r) << endl;
    }
    return 0;
}

P2787

三个操作：

区间赋值
区间查询一个数的出现次数
区间排序

对于操作一直接 assign。

对于操作二，我们还是直接暴力遍历，如果相同就累加区间长度。

对于操作三，我们可以开一个桶，然后统计所有的出现次数，然后从小到大遍历，重新插入元素即可。


#include <bits/stdc++.h>

#define IT set<node>::iterator
#define int long long
#define N 1000100

using namespace std;

int n, m, cnt[110];
char a[N];
struct node
{
    int l, r;
    mutable char s;
    node(int L, int R = -1, char S = 0): l(L), r(R), s(S) {}
    bool operator < (const node &o) const{return l < o.l;}
};
set<node> s;

IT split(int p)
{
    IT it = s.lower_bound(node(p));
    if(it != s.end() && it -> l == p) return it;
    it --;
    int L = it -> l, R = it -> r;
    char S = it -> s;
    s.erase(it);
    s.insert(node(L, p - 1, S));
    return s.insert(node(p, R, S)).first;
}

inline int ask(int l, int r, char S)
{
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for(; itl != itr; itl ++)
        if(itl -> s == S)
            res += itl -> r - itl -> l + 1;
    return res;
}

inline void assign(int l, int r, char S)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, S));
    return ;
}

inline void resort(int l, int r)
{
    memset(cnt, 0, sizeof cnt);
	IT itr = split(r + 1), itl = split(l), it = itl;
	for(; itl != itr ; itl ++)
		cnt[itl -> s - 'A'] += itl -> r - itl -> l + 1;
	s.erase(it, itr);
	for(int i = 0; i < 26; i ++)
    {
		if(cnt[i])
		{
			s.insert(node(l, l + cnt[i] - 1, i + 'A'));
			l += cnt[i];
		}
    }
    return ;
}

signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s.insert(node(i, i, toupper(a[i])));
    }
    for(int i = 1; i <= m; i ++)
    {
        int l, r, op;
        char s1;
        cin >> op >> l >> r;
        if(op == 1) cin >> s1, cout << ask(l, r, toupper(s1)) << endl;
        if(op == 2) cin >> s1, assign(l, r, toupper(s1));
        if(op == 3) resort(l, r);
    }
    return 0;
}