北京正规网站建设单价,免费注册qq号,可信赖的赣州网站建设,洪涛怎么样海城市建设网站珂朵莉树
简要
珂朵莉树的核心操作#xff1a;split
实际很简单#xff0c;一个集合中#xff0c;有一部分需要修改#xff0c;而另一部分不需要修改#xff0c;就把集合拆开#xff0c;拆成两部分。
珂朵莉树的推平操作#xff1a;assign
珂朵莉树的复杂度是由ass…珂朵莉树
简要
珂朵莉树的核心操作split
实际很简单一个集合中有一部分需要修改而另一部分不需要修改就把集合拆开拆成两部分。
珂朵莉树的推平操作assign
珂朵莉树的复杂度是由assign保证的。
由于数据随机有14\frac{1}{4}41的操作为assign。
set的大小快速下降最终趋于logn\log nlogn 使得这种看似暴力无比的数据结构复杂度接近mlognm\log nmlogn 。
struct node {int l, r;mutable ll v;node(int _l, int _r -1, ll _v 0) : l(_l), r(_r), v(_v) {}bool operator (const node t) const {return l t.l;}
};setnode::iterator split(int pos) {setnode::iterator it st.lower_bound(node(pos));if (it ! st.end() it-l pos) {return it;}it--;int l it-l, r it-r;ll v it-v;st.erase(it);st.insert(node(l, pos - 1, v));return st.insert(node(pos, r, v)).first;
}void assign(int l, int r, ll value) {setnode::iterator itr split(r 1), itl split(l);st.erase(itl, itr);st.insert(node(l, r, value));
}下面是一些可用珂朵莉树acacac题目好多题目都卡珂朵莉树了所以只能迫不得已写毒瘤线段树。
CF896C Willem, Chtholly and Seniorious
#include bits/stdc.h
#define int long longusing namespace std;typedef long long ll;
typedef pairint, int pii;struct node {int l, r;mutable ll v;node(int _l, int _r -1, ll _v 0) : l(_l), r(_r), v(_v) {}bool operator (const node t) const {return l t.l;}
};setnode st;setnode::iterator split(int pos) {setnode::iterator it st.lower_bound(node(pos));if (it ! st.end() it-l pos) {return it;}it--;int l it-l, r it-r;ll v it-v;st.erase(it);st.insert(node(l, pos - 1, v));return st.insert(node(pos, r, v)).first;
}void add(int l, int r, ll value) {setnode::iterator itr split(r 1), itl split(l);for (; itl ! itr; itl) {itl-v value;}
}void assign(int l, int r, ll value) {setnode::iterator itr split(r 1), itl split(l);st.erase(itl, itr);st.insert(node(l, r, value));
}ll rank_k(int l, int r, int k, bool reversed false) {if (reversed) {k r - l 2 - k;}setnode::iterator itr split(r 1), itl split(l);vectorpii ans;for (; itl ! itr; itl) {ans.push_back(make_pair(itl-v, itl-r - itl-l 1));}sort(ans.begin(), ans.end());for (auto it : ans) {k - it.second;if (k 0) {return it.first;}}return -1;
}ll quick_pow(ll a, int n, int mod) {ll ans 1;a % mod;while (n) {if (n 1) {ans ans * a % mod;}a a * a % mod;n 1;}return ans;
}ll sum(int l, int r, int n, int mod) {setnode::iterator itr split(r 1), itl split(l);ll ans 0;for (; itl ! itr; itl) {ans (ans 1ll * (itl-r - itl-l 1) * quick_pow(itl-v, n, mod) % mod) % mod;}return ans;
}int n, m, seed, vmax;const int mod 1e9 7;int rnd() {int ret seed;seed (1ll * seed * 7 13) % mod;return ret;
}signed main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%lld %lld %lld %lld, n, m, seed, vmax);for (int i 1; i n; i) {st.insert(node(i, i, rnd() % vmax 1));}for (int i 1; i m; i) {int op rnd() % 4 1, l rnd() % n 1, r rnd() % n 1, 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) {assign(l, r, x);}else if (op 3) {printf(%lld\n, rank_k(l, r, x));}else {printf(%lld\n, sum(l, r, x, y));}}return 0;
}CF915E Physical Education Lessons
#include bits/stdc.husing namespace std;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 t) const {return l t.l;}
};int n, m;setnode st;setnode::iterator split(int pos) {setnode::iterator it st.lower_bound(node(pos));if (it ! st.end() it-l pos) {return it;}it--;int l it-l, r it-r, v it-v;st.erase(it);st.insert(node(l, pos - 1, v));return st.insert(node(pos, r, v)).first;
}void assign(int l, int r, int value) {setnode::iterator itr split(r 1), itl split(l), it itl;for (; itl ! itr; itl) {n - (itl-r - itl-l 1) * itl-v;}st.erase(it, itr);st.insert(node(l, r, value));n (r - l 1) * value;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d, n, m);st.insert(node(1, n, 1));for (int i 1; i m; i) {int l, r, v;scanf(%d %d %d, l, r, v);assign(l, r, v 1 ^ 1);printf(%d\n, n);}return 0;
}CF343D Water Tree
#include bits/stdc.husing namespace std;const int N 5e5 10;int head[N], to[N 1], nex[N 1], cnt 1;int n, m, tot, son[N], sz[N], fa[N], top[N], rk[N], id[N], dep[N];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 t) const {return l t.l;}
};void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {sz[rt] 1, fa[rt] f, dep[rt] dep[f] 1;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs1(to[i], rt);sz[rt] sz[to[i]];if (!son[rt] || sz[to[i]] sz[son[rt]]) {son[rt] to[i];}}
}void dfs2(int rt, int tp) {top[rt] tp, rk[tot] rt, id[rt] tot;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}setnode st;auto split(int pos) {auto it st.lower_bound(node(pos));if (it ! st.end() it-l pos) {return it;}it--;int l it-l, r it-r, v it-v;st.erase(it);st.insert(node(l, pos - 1, v));return st.insert(node(pos, r, v)).first;
}void assign(int l, int r, int value) {auto itr split(r 1), itl split(l);st.erase(itl, itr);st.insert(node(l, r, value));
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d, n);for (int i 1; i n; i) {int x, y;scanf(%d %d, x, y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);st.insert(node(1, n, 0));scanf(%d, m);for (int i 1; i m; i) {int op, u;scanf(%d %d, op, u);if (op 1) {assign(id[u], id[u] sz[u] - 1, 1);}else if (op 2) {int x 1, y u;while (top[x] ! top[y]) {if (dep[top[x]] dep[top[y]]) {swap(x, y);}assign(id[top[x]], id[x], 0);x fa[top[x]];}if (dep[x] dep[y]) {swap(x, y);}assign(id[x], id[y], 0);}else {auto it st.lower_bound(node(id[u]));if (it-l id[u]) {it--;}printf(%d\n, it-v);}}return 0;
}
