线段树(进阶?)

线段树动态开点适用于数列长度n很大,但是操作次数有限的情况,而且动态开点所占用的内存更少,开2*n就够// root 表示整棵线段树的根结点cnt 表示当前结点个数 int n, cnt, root; int sum[n * 2], ls[n * 2], rs[n * 2]; //int sz[n*2],lazy[n*2] ////---------------修改节点(单点修改/新建结点/区间修改(这个加一个参数y,修改[x,y]区间))------------------- // 用法update(root, 1, n, x, f); 其中 x 为待修改节点的编号 void update(int p, int s, int t, int x, int f) { // 引用传参 if (!p) p cnt; // 当结点为空时创建一个新的结点 if (s t) { sum[p] f; return; } int m s ((t - s) 1); if (x m) update(ls[p], s, m, x, f); else update(rs[p], m 1, t, x, f); sum[p] sum[ls[p]] sum[rs[p]]; // pushup } ////--------------------------区间查询---------------------- // 用法query(root, 1, n, l, r); int query(int p, int s, int t, int l, int r) { if (!p) return 0; // 如果结点为空返回 0 if (s l t r) return sum[p]; int m s ((t - s) 1), ans 0; if (l m) ans query(ls[p], s, m, l, r); if (r m) ans query(rs[p], m 1, t, l, r); return ans; } ////区间修改也是一样的 ////不过下放标记时要注意如果缺少孩子就直接创建一个新的孩子或者使用标记永久化技巧 ////标记永久化---------------可以直接套到下面的题里---不用pushback和pushup void update(int x,int l,int r,int ql,int qr,int k){ if(!x)xidx; a[x](min(r,qr)-max(l,ql)1)*k; if(qllrqr){ z[x]k;return; } int mid(lr)1; if(qlmid)update(lc[x],l,mid,ql,qr,k); if(qrmid)update(rc[x],mid1,r,ql,qr,k); } int query(int x,int l,int r,int ql,int qr,int mk){ if(qllrqr)return a[x](r-l1)*mk; int mid(lr)1,ans0; if(qlmid)ansquery(lc[x],l,mid,ql,qr,mkz[x]); if(qrmid)ansquery(rc[x],mid1,r,ql,qr,mkz[x]); return ans; } ////下面的代码是缺少孩子则创建 ///////////////////////// //https://www.luogu.com.cn/problem/P13825 //题目概要:长度为n的序列,第i位初值为i,对区间修改,求区间和 //操作次数:1e5 //n的大小 1e9 #include bits/stdc.h using namespace std; #define ll unsigned long long const ll inf 0x3f3f3f3f; const ll N 6e6 10; const ll mod 1e9 7; ll n, m, root; ll sum[N], lc[N], rc[N], cnt, lazy[N]; void pushup(ll p) { sum[p] sum[lc[p]] sum[rc[p]]; } void pushdown(ll p, ll l, ll r, ll mid) { if (lazy[p]) { //不过下放标记时要注意如果缺少孩子就直接创建一个新的孩子 if (!lc[p])lc[p] cnt; if (!rc[p])rc[p] cnt; lazy[lc[p]] lazy[p]; lazy[rc[p]] lazy[p]; sum[lc[p]] (mid - l 1) * lazy[p]; sum[rc[p]] (r - mid) * lazy[p]; lazy[p] 0; } } ////------------------ void update(ll p, ll s, ll t, ll l, ll r, ll f) { if (p 0) { p cnt; } if (s l t r) { sum[p] (t - s 1) * f; lazy[p] f; return; } ll mid s ((t - s) 1); pushdown(p, s, t, mid); if (l mid)update(lc[p], s, mid, l, r, f); if (r mid)update(rc[p], mid 1, t, l, r, f); pushup(p); } //查询 ll ask(ll p, ll s, ll t, ll l, ll r) { //if (p 0)return 0; if (s l t r) { return sum[p]; } ll mid s ((t - s) 1); pushdown(p, s, t, mid); ll res 0; if (l mid)res ask(lc[p], s, mid, l, r); if (r mid)res ask(rc[p], mid 1, t, l, r); return res; } void solve() { cin n m; // for (int i 1; i n; i) { // update(root, 1, n, i, i, i); // } while (m--) { ll opt; cin opt; if (opt 1) { ll x, y, k; cin x y k; update(root, 1, n, x, y, k); } else { ll x, y; cin x y; ll res ask(root, 1, n, x, y); res (x y) * (y - x 1) / 2; cout res \n; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t 1; //cin t; while (t--) { solve(); } return 0; }线段树优化建图#include bits/stdc.h using namespace std; #define ll long long const ll inf 0x3f3f3f3f3f3f3f; const ll N 2e5 10; const ll mod 1e9 7; //一个点向一段连续的区间中的点连边--:入树 // 一个连续的区间向一个点连边--:出树 /*https://codeforces.com/problemset/problem/786/B 题目大意有 n 个点、q 次操作。每一种操作为以下三种类型中的一种 - 操作一连一条 u → v 的有向边权值为 w。 - 操作二对于所有 i ∈ [l,r] 连一条 u → i 的有向边权值为 w。 - 操作三对于所有 i ∈ [l,r] 连一条 i → u 的有向边权值为 w。 求从点 s 到其他点的最短路。 1 ≤ n, q ≤ 10^5, 1 ≤ w ≤ 10^9.*/ /*这段话是我在看了题解后写的(如果不对的话我会修改) 对于点和点的遍很好操作 对于点到区间:如果让点和区间内的每一个点都练一条边,会TLE,于是使用线段树优化. 首先,对于线段树中的每一个大区间会有两个子区间,则设定大区间到子区间的代价为0(这里是单向的路径) 点只需要连接到指定的区间内,就可以到达区间,但是这样只能到达线段树的叶子节点 为了从线段树回到图,应该再对每一个叶子节点,都连接一条到达图中他所对应区间的顶点 eg叶子节点区间[l,l1)-点l --这里也是单向边 如此,就能够使用logn的复杂度建好一个点到区间的边 对于区间到点,同理,建一个出树(上面那个叫入树) 建完图之后跑dj就行 */ struct node { ll v, w; bool operator(const node x)const { return w x.w; } }; vectornodee[N 3]; vectorllls(N 3), rs(N 3); vectorlldst(N 3, inf), vis(N 3, false); ll cnt, n, q, s; //建立入树 void build_in(ll p, ll l, ll r) { if (!p)p cnt;//动态开点 if (l r) { //叶子节点,节点编号:p,区间[l,l1) //建立p-l的单向路径,w为0 e[p].push_back({ l,0 }); return; } ll mid l r 1; build_in(ls[p], l, mid); build_in(rs[p], mid 1, r); //建立大区间到子区间的单向路径 e[p].push_back({ ls[p],0 }); e[p].push_back({ rs[p],0 }); } //建立出树 void build_out(ll p, ll l, ll r) { if (!p)p cnt;//动态开点 if (l r) { //叶子节点,节点编号:p,区间[l,l1) //建立l-p的单向路径,w为0 e[l].push_back({ p,0 }); return; } ll mid l r 1; build_out(ls[p], l, mid); build_out(rs[p], mid 1, r); //建立子区间到大区间的单向路径 e[ls[p]].push_back({ p,0 }); e[rs[p]].push_back({ p,0 }); } //将入树和图之间建边,pos-[ql,qr] //p是当前结点编号,l,r是入树结点的左右端点 //ql,qr,是需要建边的区间端点,pos是要建边的端点 //--我直接在函数内建立边 void add_in(ll p, ll l, ll r, ll ql, ll qr, ll pos, ll w) { if (l ql r qr) { e[pos].push_back({ p,w }); return; } ll mid l r 1; if (ql mid)add_in(ls[p], l, mid, ql, qr, pos, w); if (qr mid)add_in(rs[p], mid 1, r, ql, qr, pos, w); } //将出树和图之间建边,[ql,qr]-pos void add_out(ll p, ll l, ll r, ll ql, ll qr, ll pos, ll w) { if (l ql r qr) { e[p].push_back({ pos,w }); return; } ll mid l r 1; if (ql mid)add_out(ls[p], l, mid, ql, qr, pos, w); if (qr mid)add_out(rs[p], mid 1, r, ql, qr, pos, w); } //DJ void dj() { dst[s] 0; priority_queuenodepq; pq.push({ s,dst[s] }); while (!pq.empty()) { node tmp pq.top(); pq.pop(); ll u tmp.v; ll W tmp.w; if (vis[u])continue; vis[u] true; for (const auto re : e[u]) { ll v re.v; ll w re.w; if (vis[v] || dst[v] W w)continue; dst[v] W w; pq.push({ v,dst[v] }); } } } void solve() { cin n q s; cnt n;//因为前n个点是常规点,所以线段树要从n1开始开点 ll root_in 0, root_out 0; //建立入树 build_in(root_in, 1, n); //建立出树 build_out(root_out, 1, n); while (q--) { ll opt; cin opt; if (opt 1) { ll u, v, w;//我喜欢写u-v cin u v w; e[u].push_back({ v,w }); } if (opt 2) { ll u, l, r, w; cin u l r w; add_in(root_in, 1, n, l, r, u, w); } if (opt 3) { ll v, l, r, w; cin v l r w; add_out(root_out, 1, n, l, r, v, w); } } dj(); for (int i 1; i n; i) { if (dst[i] inf)cout -1 ; else cout dst[i] ; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t 1; //cin t; while (t--) { solve(); } return 0; }