)
线段树动态开点
适用于数列长度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)x=++idx; a[x]+=(min(r,qr)-max(l,ql)+1)*k; if(ql<=l&&r<=qr){ z[x]+=k;return; } int mid=(l+r)>>1; if(ql<=mid)update(lc[x],l,mid,ql,qr,k); if(qr>mid)update(rc[x],mid+1,r,ql,qr,k); } int query(int x,int l,int r,int ql,int qr,int mk){ if(ql<=l&&r<=qr)return a[x]+(r-l+1)*mk; int mid=(l+r)>>1,ans=0; if(ql<=mid)ans+=query(lc[x],l,mid,ql,qr,mk+z[x]); if(qr>mid)ans+=query(rc[x],mid+1,r,ql,qr,mk+z[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,l+1)->点l --这里也是单向边 如此,就能够使用logn的复杂度建好一个点到区间的边 对于区间到点,同理,建一个出树(上面那个叫入树) 建完图之后跑dj就行 */ struct node { ll v, w; bool operator<(const node& x)const { return w > x.w; } }; vector<node>e[N << 3]; vector<ll>ls(N << 3), rs(N << 3); vector<ll>dst(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,l+1) //建立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,l+1) //建立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_queue<node>pq; 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个点是常规点,所以线段树要从n+1开始开点 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; }
