小学网站建设,招商网站建设哪家好,Wordpress 采集 gofair,网站编程基础数据结构专题2 - step 1
线段树
1. Cube - HDU 3584
三维的空间中有 n n n 个元素#xff0c;初始时每个空间元素均为0。更新操作是0变1#xff0c;1变0#xff0c;是一个立方体型区域内的所有元素都更新。然后查询是问某个点的元素是0还是1. ( 1 n 100 , m…数据结构专题2 - step 1
线段树
1. Cube - HDU 3584
三维的空间中有 n n n 个元素初始时每个空间元素均为0。更新操作是0变11变0是一个立方体型区域内的所有元素都更新。然后查询是问某个点的元素是0还是1. ( 1 n 100 , m 10000 1n100, m 10000 1n100,m10000)
三维树状数组维护三维差分数组所有加法减法都是异或就可以了。
对于 n n n 维差分或者是 n n n 维前缀和公式一定有 2 n 2^n 2n 项根据 x 2 , y 2 , z 2 . . . x_2, y_2,z_2... x2,y2,z2... 这些东西出现次数的奇偶性就可以判断出来符号了.
#includebits/stdc.h
using namespace std;
const int N 110;
int tr[N][N][N];
int n, m;
int lowbit(int x)
{return x -x;
}
void add(int x, int y, int z)
{for(int i x; i n; i lowbit(i)){for(int j y; j n; j lowbit(j)){for(int k z; k n; k lowbit(k)){tr[i][j][k] ^ 1;}}}
}
int sum(int x, int y, int z)
{int res 0;for(int i x; i; i - lowbit(i)){for(int j y; j; j - lowbit(j)){for(int k z; k; k - lowbit(k)){res ^ tr[i][j][k];}}}return res;
}
void modify(int x1, int y1, int z1, int x2, int y2, int z2)
{add(x1, y1, z1);add(x1, y1, z2 1);add(x1, y2 1, z1);add(x1, y2 1, z2 1);add(x2 1, y1, z1);add(x2 1, y1, z2 1);add(x2 1, y2 1, z1);add(x2 1, y2 1, z2 1);
}
int main()
{while(cin n m){memset(tr, 0, sizeof tr);int op, x1, y1, z1, x2, y2, z2;for(int i 1; i m; i){scanf(%d, op);if(!op){scanf(%d%d%d, x1, y1, z1);printf(%d\n, sum(x1, y1, z1));}else{scanf(%d%d%d%d%d%d, x1, y1, z1, x2, y2, z2);modify(x1, y1, z1, x2, y2, z2);}}}return 0;
}2. Assignment
长度为 n ( n ≤ 1 0 5 ) n(n \le 10^5) n(n≤105) 的序列找到有多少个连续区间满足区间内的最大值减最小值小于 k k k
这种需要枚举所有连续子序列的问题基本都是暴力枚举一个端点然后看另一个端点有多少个是满足的. 固定一个端点之后区间的极差一定是单调的因此二分就可以了.
其实现在看来只需要双指针就可以了
注意这个题是多组输入因此求 s t st st 表的时候要小心不要超过 n n n 的边界.
#includebits/stdc.h
using namespace std;
const int N 100010, M 18;
int lg[N], a[N], n, k;
int Fmax[N][M], Fmin[N][M];
typedef long long ll;
void pre()
{for(int j 0; j M; j){for(int i 1; i n; i){if(!j) Fmin[i][j] Fmax[i][j] a[i];else if(i (1 (j - 1)) n){Fmax[i][j] max(Fmax[i][j - 1], Fmax[i (1 (j - 1))][j - 1]);Fmin[i][j] min(Fmin[i][j - 1], Fmin[i (1 (j - 1))][j - 1]);}else{Fmax[i][j] Fmax[i][j - 1], Fmin[i][j] Fmin[i][j - 1];}}}
}
int query(int l, int r)
{int len lg[r - l 1];return max(Fmax[l][len], Fmax[r - (1 len) 1][len]) - min(Fmin[l][len], Fmin[r - (1 len) 1][len]);
}
int main()
{for(int i 1; i N; i) lg[i] log2(i);int T;scanf(%d, T);while(T--){scanf(%d%d, n, k);for(int i 1; i n; i) scanf(%d, a[i]);pre();ll ans 0;for(int i 1; i n; i){int l 1, r i;while(r l){int mid (l r) / 2;if(query(mid, i) k) l mid 1;else r mid;}ans (i - l 1);}printf(%lld\n, ans);}return 0;
}3. GCD
给你 n n n 个数 Q Q Q 次询问问你 ( l , r ) (l,r) (l,r) 区间的 g c d gcd gcd 是多少并且有多少子串的 g c d gcd gcd 和询问的 g c d gcd gcd 是相同的。
$n \le 10^5,Q \le 10^5, a_i \le 10^9 $
任意区间的 g c d gcd gcd 可以用 s t st st 表快速求得。然后我们预处理出每一个 g c d gcd gcd 有多少个。方法是这样的暴力枚举右端点那么前面的 g c d gcd gcd 一定是一段一段的. 那么我们可以把前面一段一段的 gcd 存下来每次加进来一个数前面会有若干区间的 gcd 下降. 把gcd相同的区间合并成一个区间.
小心答案爆 int.
#includebits/stdc.h
using namespace std;
const int N 100010, M 18;
typedef long long ll;
typedef pairint, int P;
#define x first
#define y secondint a[N], f[N][M], lg[N];unordered_mapint, ll mp;
int n, m, kase;
void pre()
{mp.clear();for(int j 0; j M; j){for(int i 1; (i (1 j) - 1) n; i){if(!j) f[i][j] a[i];else f[i][j] __gcd(f[i][j - 1], f[i (1 j - 1)][j - 1]);}}vectorP vec;for(int i 1; i n; i){for(auto p : vec){p.x __gcd(p.x, a[i]);}vec.push_back({a[i], 1});vectorP tmp;for(auto p : vec){if(tmp.size() tmp.back().x p.x) tmp.back().y p.y;else tmp.push_back(p);mp[p.x] p.y;}vec tmp;}
}int query(int l, int r)
{int len lg[r - l 1];return __gcd(f[l][len], f[r - (1 len) 1][len]);
}int main()
{for(int i 1; i N; i) lg[i] log2(i);int T;scanf(%d, T);while(T--){scanf(%d\n, n);for(int i 1; i n; i){scanf(%d, a[i]);}pre();printf(Case #%d:\n, kase);scanf(%d, m);for(int i 1; i m; i){int l, r;scanf(%d%d, l, r);int d query(l, r);printf(%d %lld\n, d, mp[d]);}}return 0;
}
4. City Driving (值得再写) n ( n ≤ 1 0 5 ) n(n \le 10^5) n(n≤105) 个点 n n n 条无向边的连通图 Q ( Q ≤ 1 0 4 ) Q(Q \le 10^4) Q(Q≤104) 个询问问两点之间的最短路是多少。
基环树任意删掉一条边假设是 ( a , b ) (a, b) (a,b). 若询问 u , v u, v u,v 的最小值则答案在 d i s t ( u , v ) , d i s t ( u , a ) w ( a , b ) d i s t ( b , v ) dist(u, v), dist(u, a) w(a, b) dist(b, v) dist(u,v),dist(u,a)w(a,b)dist(b,v) 与 d i s t ( u , b ) w ( a , b ) d i s t ( a , v ) dist(u, b) w(a, b) dist(a, v) dist(u,b)w(a,b)dist(a,v) 三者取最小值.
无向图基环树一定要记录from。不然找自环的时候找的就是无向边的自环.自行分析
最近公共祖先还得再写几次一写一堆bug
#includebits/stdc.h
using namespace std;
const int N 100010, M N * 2;
int h[N], e[M], ne[M], w[M], idx;inline void add(int a, int b, int c)
{e[idx] b, ne[idx] h[a], w[idx] c, h[a] idx;
}int n, m;
bool st[N], ins[N];
int rmid, rma, rmb;void dfs_c(int u, int from)
{st[u] ins[u] true;for(int i h[u]; i ! -1; i ne[i]){//无向图基环树一定要记录from。不然找自环的时候找的就是无向边的自环.if(i (from ^ 1)) continue;int v e[i];if(!st[v]) dfs_c(v, i);else if(ins[v]){rmid i, rma u, rmb v;}}ins[u] false;
}//小心记录两个depth一个用作lca的查询一个用作查询到根节点的距离。因为这个树的边是有权重的.
int fa[N][18], dep[N], ndep[N];void bfs()
{queueint que;for(int i 1; i n; i) ndep[i] dep[i] -1;dep[1] 1, ndep[1] 0;que.push(1);for(int k 0; k 18; k) fa[1][k] 1;while(que.size()){int u que.front(); que.pop();for(int i h[u]; i ! -1; i ne[i]){if(i rmid || (i ^ 1) rmid) continue;int v e[i];if(dep[v] -1){dep[v] dep[u] 1;ndep[v] ndep[u] w[i];fa[v][0] u;for(int k 1; k 18; k) fa[v][k] fa[fa[v][k - 1]][k - 1];que.push(v);}}}
}int lca(int a, int b)
{if(dep[a] dep[b]) swap(a, b);for(int k 17; k 0; k--){if(dep[a] dep[fa[b][k]]) b fa[b][k];}if(a b) return a;for(int k 17; k 0; k--){if(fa[a][k] ! fa[b][k]) a fa[a][k], b fa[b][k];}return fa[a][0];
}int dist(int u, int v)
{int anc lca(u, v);//printf(** u %d dep[u] %d, v %d dep[v] %d, anc %d\n, u, dep[u], v, dep[v], anc);return ndep[u] ndep[v] - 2 * ndep[anc];
}int main()
{while(cin n, n){for(int i 1; i n; i){h[i] -1, st[i] false;}idx 0;for(int i 1; i n; i){int a, b, c;scanf(%d%d%d, a, b, c);a, b;add(a, b, c), add(b, a, c);}dfs_c(1, -1);bfs();//printf(** remove id %d, rma %d, rmb %d\n, rmid, rma, rmb);scanf(%d, m);for(int i 1; i m; i){int u, v;scanf(%d%d, u, v);u, v;int ans dist(u, v);ans min(dist(u, rma) w[rmid] dist(rmb, v), ans);ans min(dist(u, rmb) w[rmid] dist(rma, v), ans);printf(%d\n, ans);}}return 0;
}
5. Rikka with Phi (值得再写)
给出一个长度为 n n n 的数组 A A A接下来有 m m m 次操作
1 l r对所有区间 [ l , r ] [l,r] [l,r] 中的整数 i i i把 A [ i ] A[i] A[i] 变成 φ ( A [ i ] ) φ(A[i]) φ(A[i]) (指欧拉函数)
2 l r x对所有区间 [ l , r ] [l,r] [l,r] 中的整数 i i i把 A [ i ] A[i] A[i] 变成 x x x
3 l r询问 [ l , r ] [l,r] [l,r] 的区间和 n , m ( n ≤ 3 × 1 0 5 , m ≤ 3 × 1 0 5 ) n,m(n≤3×10^5,m≤3×10^5) n,m(n≤3×105,m≤3×105) 1 ≤ A [ i ] ≤ 1 0 7 1≤A[i]≤10^7 1≤A[i]≤107
保证任何时刻 1 ≤ A i ≤ 1 0 7 1 \le A_i \le 10^7 1≤Ai≤107
几个减少代码量的技巧
由于数组元素任意时刻都保证是正的因此可以记录一个 x x x. 如果 x 0 x 0 x0则说明当前区间所有元素并非全部相等。若 x 0 x 0 x0则区间所有元素都等于 x x x.第一个修改操作若当前区间元素都相等则可转化为第二个修改操作.
#includebits/stdc.h
#define lson u 1
#define rson u 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef __int128_t i128;
typedef __uint128_t u128;using namespace std;
const int N 300010;const int M 10000010;
int prime[M], cnt, phi[M];
bool st[M];
void sieve(int n)
{phi[1] 1;for(int i 2; i n; i){if(!st[i]) prime[cnt] i, phi[i] i - 1;for(int j 0; prime[j] * i n; j){st[i * prime[j]] true;if(i % prime[j] 0){phi[i * prime[j]] phi[i] * prime[j];break;}phi[i * prime[j]] phi[i] * (prime[j] - 1);}}
}struct node
{int l, r, x;bool lazy;u64 sum;
}tr[N * 4];
int a[N];void pushup(int u)
{tr[u].sum tr[lson].sum tr[rson].sum;if(tr[lson].x tr[lson].x tr[rson].x){tr[u].x tr[lson].x;}else tr[u].x 0;
}void build(int u, int l, int r)
{tr[u] {l, r};if(l r){tr[u].x a[l];tr[u].sum a[l];}else{int mid l r 1;build(lson, l, mid), build(rson, mid 1, r);pushup(u);}
}void pushdown(int u)
{if(tr[u].lazy){tr[lson].lazy tr[rson].lazy true;tr[lson].x tr[rson].x tr[u].x;tr[lson].sum 1ll * tr[lson].x * (tr[lson].r - tr[lson].l 1);tr[rson].sum 1ll * tr[rson].x * (tr[rson].r - tr[rson].l 1);}tr[u].lazy false;
}void modify1(int u, int x, int L, int R)
{if(L tr[u].l tr[u].r R){tr[u].lazy true;tr[u].x x;tr[u].sum 1ll * x * (tr[u].r - tr[u].l 1);}else{pushdown(u);int mid tr[u].l tr[u].r 1;if(L mid) modify1(lson, x, L, R);if(R mid) modify1(rson, x, L, R);pushup(u);}
}void modify2(int u, int L, int R)
{if(L tr[u].l tr[u].r R){if(tr[u].x){modify1(u, phi[tr[u].x], L, R);}else{pushdown(u);int mid tr[u].l tr[u].r 1;modify2(lson, L, R), modify2(rson, L, R);pushup(u);}}else{pushdown(u);int mid tr[u].l tr[u].r 1;if(L mid) modify2(lson, L, R);if(R mid) modify2(rson, L, R);pushup(u);}
}u64 query(int u, int L, int R)
{if(L tr[u].l tr[u].r R){return tr[u].sum;}pushdown(u);int mid tr[u].l tr[u].r 1;u64 res 0;if(L mid) res query(lson, L, R);if(R mid) res query(rson, L, R);return res;
}int main()
{sieve(M - 1);int T;scanf(%d, T);while(T--){int n, m;scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, a[i]);build(1, 1, n);for(int i 1; i m; i){int op, l, r, x;scanf(%d%d%d, op, l, r);if(op 1){modify2(1, l, r);}else if(op 2){scanf(%d, x);modify1(1, x, l, r);}else{printf(%llu\n, query(1, l, r));}}}return 0;
}
6. P4145 上帝造题的七分钟 2
第一行一个整数 n n n代表数列中数的个数。
第二行 n n n 个正整数表示初始状态下数列中的数。
第三行一个整数 m m m表示有 m m m 次操作。
接下来 m m m 行每行三个整数 k l r。 k 0 k0 k0 表示给 [l,r] 中的每个数开平方下取整。 k 1 k1 k1 表示询问 [l,r] 中各个数的和。
数据中有可能 l r lr lr所以遇到这种情况请交换 l l l 和 r r r。
#includebits/stdc.h#define lson u 1
#define rson u 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef __int128_t i128;
typedef __uint128_t u128;const u32 mod 1e9 7;using namespace std;
const int N 100010;struct node
{int l, r;u64 sum, x;
}tr[N * 4];u64 a[N];void pushup(int u)
{tr[u].sum tr[lson].sum tr[rson].sum;if(tr[lson].x tr[lson].x tr[rson].x){tr[u].x tr[lson].x;}else tr[u].x 0;
}void build(int u, int l, int r)
{tr[u] {l, r};if(l r){tr[u].sum tr[u].x a[l];}else{int mid l r 1;build(lson, l, mid), build(rson, mid 1, r);pushup(u);}
}void modify(int u, int L, int R)
{if(tr[u].l tr[u].r) tr[u].x tr[u].sum sqrt(tr[u].x);else if(L tr[u].l tr[u].r R){if(tr[u].x 1){return;}else{int mid tr[u].l tr[u].r 1;if(L mid) modify(lson, L, R);if(R mid) modify(rson, L, R);pushup(u);}}else{int mid tr[u].l tr[u].r 1;if(L mid) modify(lson, L, R);if(R mid) modify(rson, L, R);pushup(u);}
}u64 query(int u, int L, int R)
{if(L tr[u].l tr[u].r R){return tr[u].sum;}int mid tr[u].l tr[u].r 1;u64 res 0;if(L mid) res query(lson, L, R);if(R mid) res query(rson, L, R);return res;
}int main()
{int n;scanf(%d, n);for(int i 1; i n; i){scanf(%llu, a[i]);}build(1, 1, n);int m;scanf(%d, m);for(int i 1; i m; i){int k, l, r;scanf(%d%d%d, k, l, r);if(l r) swap(l, r);if(k 0){modify(1, l, r);}else{printf(%llu\n, query(1, l, r));}}return 0;
}7. 247. 亚特兰蒂斯 - AcWing题库
用懒标记维护的版本。minlen 表示当前区间涵盖所有区间 c n t cnt cnt 最小的时候区间长度之和.
这样子维护的其实是覆盖 0 0 0 次的区间长度之和. 最后总长度减去它就可以了.
#includebits/stdc.h
#define x first
#define y second
#define lowbit(x) ((x) (-x))
#define all(x) x.begin(), x.end()
#define pcount __builtin_popcount
#define lcount __builtin_clz
#define rcount __builtin_ctz
#define qcin std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define tempt templateclass T
#define lson u 1
#define rson u 1 | 1typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;using namespace std;
const int N 10010;struct node
{int l, r, mincnt;int lazy;double minlen, len;
}tr[N * 8];struct seg
{double x, y1, y2;int t;bool operator (const seg s) const{return x s.x;}
}segs[N * 2];vectordouble ys;int find(double x)
{return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}void pushup(int u)
{tr[u].mincnt min(tr[lson].mincnt, tr[rson].mincnt);double minlen 0;if(tr[u].mincnt tr[lson].mincnt) minlen tr[lson].minlen;if(tr[u].mincnt tr[rson].mincnt) minlen tr[rson].minlen;tr[u].minlen minlen;
}void pushdown(int u)
{tr[lson].mincnt tr[u].lazy, tr[rson].mincnt tr[u].lazy;tr[lson].lazy tr[u].lazy, tr[rson].lazy tr[u].lazy;tr[u].lazy 0;
}void build(int u, int l, int r)
{double len ys[r 1] - ys[l];tr[u] {l, r, 0, 0, len, len};if(l r) return;else{int mid l r 1;build(lson, l, mid), build(rson, mid 1, r);}
}void modify(int u, int L, int R, int t)
{if(L tr[u].l tr[u].r R){tr[u].mincnt t;tr[u].lazy t;}else{pushdown(u);int mid tr[u].l tr[u].r 1;if(L mid) modify(lson, L, R, t);if(R mid) modify(rson, L, R, t);pushup(u);}
}int kase;
int main()
{int n;while(cin n, n){int sz 0;ys.clear();for(int i 1; i n; i){double x1, y1, x2, y2;scanf(%lf%lf%lf%lf, x1, y1, x2, y2);segs[sz] {x1, y1, y2, 1};segs[sz] {x2, y1, y2, -1};ys.push_back(y1), ys.push_back(y2);}sort(ys.begin(), ys.end());ys.erase(unique(ys.begin(), ys.end()), ys.end());sort(segs, segs 2 * n);build(1, 0, ys.size() - 2);double ans 0;for(int i 0; i 2 * n; i){if(i){double len tr[1].len;if(!tr[1].mincnt) len - tr[1].minlen;ans len * (segs[i].x - segs[i - 1].x);}modify(1, find(segs[i].y1), find(segs[i].y2) - 1, segs[i].t);//printf(%f %d %f\n, tr[1].len, tr[1].mincnt, tr[1].minlen);}printf(Test case #%d\nTotal explored area: %.2f\n\n, kase, ans);}return 0;
}8. Legacy (值得再写)
三种操作 1 a b c在建立权值为 c c c 的 a → b a\rightarrow b a→b 的单向边 2 a b c d建立 a → [ b , c ] a\rightarrow [b,c] a→[b,c] 权值为 d d d 的单向边 3 a b c d建立 [ b , c ] → a [b,c]\rightarrow a [b,c]→a 权值为 d d d 的单向边
给你一个起点问你起点到其他点的最短路长度 1 ≤ n , q ≤ 1 0 5 1 ≤ n, q ≤ 10^5 1 ≤ n, q ≤ 105
借助线段树建立为每个区间建立一个结点有一个需要注意的问题为了保证某个点可以走到它对应的所有区间并且它所有对应的区间能走到它并且不能形成长度为 0 0 0 的环。因此可以建立两棵线段树一棵从父结点向子结点连长度为 0 0 0 的边一棵从子结点向父结点连长度为 0 0 0 的边. 子结点之间相互连长度为 0 0 0 的边.
当然我们不用真的建立两棵线段树只需要把对应的线段树编号找到就可以了. 第一个线段树的编号加 4 n 4n 4n 就是第二棵线段树的编号.
#includebits/stdc.h
#define x first
#define y second
typedef long long ll;using namespace std;
const int N 100010, M 6000010;
const ll INF 0x3f3f3f3f3f3f3f3fll;struct node
{int l, r;
}tr[N * 4];int h[N * 8], e[M], ne[M], id[N], idx;
ll w[M], d[N * 8];int n, q, s;
typedef pairll, int P;
bool st[N * 8];void add(int a, int b, ll c)
{e[idx] b, ne[idx] h[a], w[idx] c, h[a] idx;
}void build(int u, int l, int r)
{tr[u] {l, r};if(l r){id[l] u;add(u, u 4 * n, 0), add(u 4 * n, u, 0);}else{int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);add(u, u 1, 0), add(u, u 1 | 1, 0);add((u 1) 4 * n, u 4 * n, 0), add((u 1 | 1) 4 * n, u 4 * n, 0);}
}void modify(int u, int l, int r, int x, ll c, int op)
{if(l tr[u].l tr[u].r r){if(op 2) add(x, u, c), add(x 4 * n, u 4 * n, c);else add(u, x, c), add(u 4 * n, x 4 * n, c);}else{int mid tr[u].l tr[u].r 1;if(l mid) modify(u 1, l, r, x, c, op);if(r mid) modify(u 1 | 1, l, r, x, c, op);}
}void dijkstra()
{memset(d, 0x3f, sizeof d);d[id[s]] 0;priority_queueP, vectorP, greaterP que;que.push({0, id[s]});while(que.size()){int u que.top().y; que.pop();if(st[u]) continue;st[u] true;for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(d[v] d[u] w[i]){d[v] d[u] w[i];que.push({d[v], v});}}}
}
int main()
{memset(h, -1, sizeof h);scanf(%d%d%d, n, q, s);build(1, 1, n);for(int i 1; i q; i){int op, a, b, c, d;scanf(%d%d%d%d, op, a, b, c);if(op 1){//注意是 id[a] 而不是 aadd(id[a], id[b], c);add(id[a] 4 * n, id[b] 4 * n, c);}else if(op 2){scanf(%d, d);//注意是 id[a] 而不是 amodify(1, b, c, id[a], d, 2);}else{scanf(%d, d);//注意是 id[a] 而不是 amodify(1, b, c, id[a], d, 3);}}dijkstra();for(int i 1; i n; i){//注意是 d[id[i]] 不是 d[i]printf(%lld%c, d[id[i]] INF ? -1LL : d[id[i]], i n ? \n : );}return 0;
}9. Ch’s gift (值得再写)
题意给定一棵树。询问 s , t s,t s,t 之间路径上的点权和点权在 [ a , b ] [a,b] [a,b] 内才有效否则该点权为 0 0 0
从每个节点向父结点建立可持久化权值线段树查询的时候就是 r o o t [ s ] r o o t [ t ] − r o o t [ l c a ( s , t ) ] − r o o t [ f a [ l c a ( s , t ) ] ] root[s] root[t]-root[lca(s,t)]-root[fa[lca(s,t)]] root[s]root[t]−root[lca(s,t)]−root[fa[lca(s,t)]].
终于调出来了
第一个错误主席树由于维护的是权值查询的是点权之和。因此从子结点向父结点建立版本的时候要 tr[p].sum nums[x]不是 tr[p].sum nums[x]
第二个错误注意找 [ a , b ] [a,b] [a,b] 区间的时候一个是找 ≥ a \ge a ≥a 的最小值一个是找 ≤ b \le b ≤b 的最大值不能全用 lower_bound 处理.
#includebits/stdc.h
using namespace std;
const int N 100010, M N * 2;
typedef long long ll;
int h[N], e[M], ne[M], idx;
ll w[N];int fa[N][18];
int n, m;void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx;
}int q[N], dep[N];
void bfs()
{memset(dep, -1, sizeof dep);dep[0] 0, dep[1] 1;int hh 0, tt -1;q[tt] 1;while(hh tt){int u q[hh];for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(dep[v] ! -1) continue;dep[v] dep[u] 1;fa[v][0] u;for(int j 1; j 18; j) fa[v][j] fa[fa[v][j - 1]][j - 1];q[tt] v;}}
}int lca(int a, int b)
{if(dep[a] dep[b]) swap(a, b);for(int k 17; k 0; k--){if(dep[fa[a][k]] dep[b]){a fa[a][k];}}if(a b) return a;for(int k 17; k 0; k--){if(fa[a][k] ! fa[b][k]){a fa[a][k], b fa[b][k];}}return fa[a][0];
}struct node
{int l, r;ll sum;
}tr[N * 4 N * 17];int cnt;
vectorll nums;
int root[N];
int find(ll x)
{return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
void pushup(int u)
{tr[u].sum tr[tr[u].l].sum tr[tr[u].r].sum;
}int build(int l, int r)
{int p cnt;if(l r){tr[p] {l, r, 0};return p;}int mid l r 1;tr[p].l build(l, mid), tr[p].r build(mid 1, r);pushup(p);return p;
}int insert(int p, int l, int r, int x)
{int q cnt;tr[q] tr[p];if(l r){tr[q].sum nums[x];return q;}int mid l r 1;if(x mid) tr[q].l insert(tr[p].l, l, mid, x);else tr[q].r insert(tr[p].r, mid 1, r, x);pushup(q);return q;
}ll query(int s, int t, int anc, int anc_fa, int l, int r, int L, int R)
{if(L l r R) return tr[s].sum tr[t].sum - tr[anc].sum - tr[anc_fa].sum;int mid l r 1;ll res 0;if(L mid) res query(tr[s].l, tr[t].l, tr[anc].l, tr[anc_fa].l, l, mid, L, R);if(R mid) res query(tr[s].r, tr[t].r, tr[anc].r, tr[anc_fa].r, mid 1, r, L, R);return res;
}void dfs(int u, int fa)
{root[u] insert(root[fa], 0, nums.size() - 1, find(w[u]));for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(v fa) continue;dfs(v, u);}
}int main()
{while(cin n m){memset(h, -1, sizeof h);idx 0, cnt 0;nums.clear();for(int i 1; i n; i){scanf(%lld, w[i]);nums.push_back(w[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());for(int i 1; i n; i){int a, b;scanf(%d%d, a, b);add(a, b), add(b, a);}bfs();root[0] build(0, nums.size() - 1);dfs(1, 0);for(int i 1; i m; i){int s, t;ll a, b;scanf(%d%d%lld%lld, s, t, a, b);int anc lca(s, t);int anc_fa fa[anc][0];a find(a), b upper_bound(nums.begin(), nums.end(), b) - nums.begin() - 1;ll ans query(root[s], root[t], root[anc], root[anc_fa], 0, nums.size() - 1, a, b);printf(%lld%c, ans, i m ? \n : );}}return 0;
}11. ROT-Tree Rotations (值得再写)
题意给定一颗有 n n n 个叶节点的二叉树。每个叶节点都有一个权值 p i p_i pi注意根不是叶节点所有叶节点的权值构成了一个 1 ∼ n 1 \sim n 1∼n 的排列。对于这棵二叉树的任何一个结点保证其要么是叶节点要么左右两个孩子都存在。现在你可以任选一些节点交换这些节点的左右子树。在最终的树上按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 n n n 的排列你需要最小化这个排列的逆序对数。输出这个逆序对数。
线段树合并裸题每个叶节点建立权值线段树看看交换与不交换对答案的贡献分别是多少
我们要求的是逆序对最小对于一个节点逆序对有三种
在左子树中。在右子树中。跨越了左右子树。
我们清楚交换子树只会对第三种情况产生影响。因此我们只需要在合并线段树的过程中统计交换子树的逆序对个数 u u u 和不交换子树的逆序对个数 v v v取 m i n ( u , v ) min(u,v) min(u,v) 累加到答案中就行了。
现在的问题是如何找第三种情况下的逆序对。
很明显对于除了叶节点的每一个节点
如果不交换 u [ p . r s ] . s i z e ∗ [ q . l s ] . s i z e u[p.rs].size*[q.ls].size u[p.rs].size∗[q.ls].size如果交换 v [ p . l s ] . s i z e ∗ [ q . r s ] . s i z e v[p.ls].size*[q.rs].size v[p.ls].size∗[q.rs].size
重点每一次合并线段树时递归到除了叶节点的所有节点都要累加逆序对个数 u,v。
#includebits/stdc.h
using namespace std;
const int N 100010;
typedef long long ll;
struct node
{int l, r, sz;
}tr[N * 50];
int n, idx;
ll res1, res2, ans;int modify(int l, int r, int x)
{int q idx;tr[q].sz 1;if(l r) return q;int mid l r 1;if(x mid) tr[q].l modify(l, mid, x);else tr[q].r modify(mid 1, r, x);return q;
}int merge(int p, int q, int l, int r)
{if(!p || !q) return p ? p : q;if(l r){tr[p].sz tr[q].sz;return p;}else{res1 1ll * tr[tr[p].r].sz * tr[tr[q].l].sz;res2 1ll * tr[tr[p].l].sz * tr[tr[q].r].sz;int mid l r 1;tr[p].l merge(tr[p].l, tr[q].l, l, mid);tr[p].r merge(tr[p].r, tr[q].r, mid 1, r);tr[p].sz tr[tr[p].l].sz tr[tr[p].r].sz;return p;}
}int dfs()
{int x;scanf(%d, x);if(!x){int l dfs(), r dfs();res1 res2 0;int p merge(l, r, 1, n);ans min(res1, res2);return p;}else{int p modify(1, n, x);return p;}
}int main()
{scanf(%d, n);dfs();printf(%lld\n, ans);
}
11.
给出 A [ ] A[] A[], 要求支持: 1 询问 A [ l . . r ] A[l..r] A[l..r] 中最⼤的数 2 删除 A [ x ] A[x] A[x], 并且 x 1 x1 x1 以后的元素整体前移 3 在末尾增加⼀个数
用 splay 肯定是可以的。不过线段树更简单
每个位置记录一个 0 / 1 0/1 0/1. 0 0 0 表示数字被删掉 1 1 1 表示数字没被删。记录当前 [ 1... r ] [1...r] [1...r] 未被删掉数的数量是 s u m [ r ] sum[r] sum[r]. 那么用线段树二分在 [ 1 , n ] [1,n] [1,n] 上面找第 s u m [ r ] sum[r] sum[r] 小的数字.
12.
对长度为 n n n 的数列进行 m m m 次操作, 操作为: 1 a [ l . . r ] a[l..r] a[l..r] 每⼀项都加⼀个常数 C C C, 其中 0 ≤ C ≤ 1 0 11 0 ≤ C ≤ 10^{11} 0≤C≤1011 2 求 F [ a [ l ] ] F [ a [ l 1 ] ] . . . F [ a [ r ] ] m o d 10000 F[a[l]]F[a[l1]]...F[a[r]] \mod 10000 F[a[l]]F[a[l1]]...F[a[r]]mod10000 的余数 其中 F [ i ] F[i] F[i] 表示斐波那契数列. 即 F [ 0 ] F [ 1 ] 1 F[0]F[1]1 F[0]F[1]1, F [ n 2 ] F [ n 1 ] F [ n ] F[n2]F[n1]F[n] F[n2]F[n1]F[n]
每一项保存 F [ a [ i ] ] F[a[i]] F[a[i]] 与 F [ a [ i 1 ] ] F[a[i 1]] F[a[i1]] 即可然后用 lazy tag 记下来幂次.
然后操作的时候就是 ( F [ a i ] F [ a i 1 ] ) ( 0 1 1 1 ) \begin{pmatrix}F[a_i] F[a_i 1]\end{pmatrix} \begin{pmatrix}0 1 \\ 1 1\end{pmatrix} (F[ai]F[ai1])(0111)
13. Hotel - POJ 3667 (值得再写)
给一个长度为 n ( n ≤ 5 ∗ 1 0 4 ) n(n \le 5 * 10^4) n(n≤5∗104) 的序列一开始都是 0 0 0有 q q q 种操作找到一段长度为 k k k 的全为 0 0 0 的子串使开始位置尽可能得小输出起始位置然后把这段全部变成1找不到的话输出 0 0 0使得一段区间全部变成 0 0 0.
每个点维护左起一段连续最长的空住房以及右起一段连续的最长的空住房在表示的区间内最长的连续空住房数。
如何合并信息
前两个很好维护但是要特判一边全部都是空住房的时候。
最后一个也好维护首先用两边原来的答案来更新。把两个区间拼接起来会导致中间的连续一段空住房变长所以还需要用它来更新答案。
对于lazy标记的下放因为是覆盖所以直接改就好了。
这道题的WA了很久才过 懒标记之间会有相互限制就比如这个题lazy0 和 lazy1 一定不会同时为1因此一旦修改其中一个是1另一个必须要修改为0.
当然这道题的懒标记开一个就行了因为他们是相互限制的嘛.
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 50010;
struct node
{int l, r;int lmax, rmax, mmax;int lazy;
}tr[N * 4];
int n, m;
void pushup(int u)
{if(tr[u 1].mmax tr[u 1].r - tr[u 1].l 1){tr[u].lmax tr[u 1].mmax tr[u 1 | 1].lmax;}else tr[u].lmax tr[u 1].lmax;if(tr[u 1 | 1].mmax tr[u 1 | 1].r - tr[u 1 | 1].l 1){tr[u].rmax tr[u 1].rmax tr[u 1 | 1].mmax;}else tr[u].rmax tr[u 1 | 1].rmax;tr[u].mmax max(max(tr[u 1].mmax, tr[u 1 | 1].mmax), tr[u 1].rmax tr[u 1 | 1].lmax);
}void pushdown(int u)
{if(tr[u].lazy ! -1){tr[u 1].lmax tr[u 1].rmax tr[u 1].mmax (tr[u 1].r - tr[u 1].l 1) * (tr[u].lazy ^ 1);tr[u 1 | 1].lmax tr[u 1 | 1].rmax tr[u 1 | 1].mmax (tr[u 1 | 1].r - tr[u 1 | 1].l 1) * (tr[u].lazy ^ 1);tr[u 1].lazy tr[u 1 | 1].lazy tr[u].lazy;}tr[u].lazy -1;
}void build(int u, int l, int r)
{tr[u].l l, tr[u].r r;if(l r){tr[u].lmax tr[u].rmax tr[u].mmax 1;tr[u].lazy -1;}else{int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pushup(u);}
}
void modify(int u, int l, int r, int x)
{if(l tr[u].l tr[u].r r){tr[u].lazy x;tr[u].lmax tr[u].rmax tr[u].mmax (tr[u].r - tr[u].l 1) * (x ^ 1);}else{pushdown(u);int mid tr[u].l tr[u].r 1;if(l mid) modify(u 1, l, r, x);if(r mid) modify(u 1 | 1, l, r, x);pushup(u);}
}
int query(int u, int k)
{if(tr[u].mmax k) return 0;if(tr[u].l tr[u].r) return tr[u].l;pushdown(u);if(tr[u 1].mmax k) return query(u 1, k);if(tr[u 1].rmax tr[u 1 | 1].lmax k) return tr[u 1].r - tr[u 1].rmax 1;else return query(u 1 | 1, k);
}int main()
{scanf(%d%d, n, m);build(1, 1, n);for(int i 1; i m; i){int op, l, k;scanf(%d, op);if(op 1){scanf(%d, k);int res query(1, k);printf(%d\n, res);if(res) modify(1, res, res k - 1, 1);}else{scanf(%d%d, l, k);modify(1, l, l k - 1, 0);}}return 0;
}14. 可持久化线段树 1可持久化数组
如题你需要维护这样的一个长度为 NN 的数组支持如下几种操作
在某个历史版本上修改某一个位置上的值访问某个历史版本上的某一位置的值
此外每进行一次操作对于操作2即为生成一个完全一样的版本不作任何改动就会生成一个新的版本。版本编号即为当前操作的编号从1开始编号版本0表示初始状态数组
简单的可持久化线段树不需要建立权值线段树
注意数组千万别开小因为询问是 1 0 6 10^6 106 次.
#includebits/stdc.h
using namespace std;
const int N 1000010;
struct node
{int l, r, value;
}tr[N * 4 N * 20];
//小心询问次数达到1e6数组千万别开小.
int n, m, a[N], root[N], idx;int build(int l, int r)
{int q idx;if(l r){tr[q].value a[l];return q;}int mid l r 1;tr[q].l build(l, mid), tr[q].r build(mid 1, r);return q;
}int modify(int p, int l, int r, int x, int v)
{int q idx;tr[q] tr[p];if(l r){tr[q].value v;return q;}int mid l r 1;if(x mid) tr[q].l modify(tr[p].l, l, mid, x, v);else tr[q].r modify(tr[p].r, mid 1, r, x, v);return q;
}int query(int p, int l, int r, int x, int res)
{int q idx;tr[q] tr[p];if(l r){res tr[q].value;return q;}int mid l r 1;if(x mid) tr[q].l query(tr[p].l, l, mid, x, res);else tr[q].r query(tr[p].r, mid 1, r, x, res);return q;
}int main()
{scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, a[i]);root[0] build(1, n);for(int i 1; i m; i){int v, op, loc, value;scanf(%d%d%d, v, op, loc);if(op 1){scanf(%d, value);root[i] modify(root[v], 1, n, loc, value);}else{int res;root[i] query(root[v], 1, n, loc, res);printf(%d\n, res);}}return 0;
}15. 可持久化并查集
给定 n 个集合第 i 个集合内初始状态下只有一个数为 i。
有 m 次操作。操作分为 3 种
1 a b 合并 a,b 所在集合2 k 回到第 k 次操作执行三种操作中的任意一种都记为一次操作之后的状态3 a b 询问 a,b 是否属于同一集合如果是则输出 1 否则输出 0。
按秩合并的并查集只要 f a fa fa 数组确定 d e p dep dep 状态确定这个并查集的就唯一确定。
有几个需要注意的地方
一定小心可持久化线段树的版本结点个数是 m ∗ log n m * \log n m∗logn 个版本个数是 m 1 m1 m1 个 r o o t root root 的数组要开到 M M M.版本信息啥的要弄好一定看清楚当前的 r o o t [ i ] root[i] root[i] 的信息有没有更新按秩合并有启发式合并的感觉就是把高度低的树的树根连到高度高的树根上面去这样子可以保证复杂度 r k rk rk 维护的是树的高度。需要注意的是不妨假设 r k [ a ] ≤ r k [ b ] rk[a] \le rk[b] rk[a]≤rk[b]当 r k [ a ] r k [ b ] rk[a] rk[b] rk[a]rk[b] 的时候 a a a 连到 b b b 不会使 b b b 的高度发生变化但是如果 r k [ a ] r k [ b ] rk[a] rk[b] rk[a]rk[b] r k [ b ] rk[b] rk[b] 的高度就会发生变化. 这个时候就要 r k [ b ] rk[b] rk[b]. 千万不要加错了不然复杂度会炸.
#includebits/stdc.h
using namespace std;
const int N 100010, M 200010;struct node
{int l, r, fa, rk;
}tr[N * 4 20 * M];
//想清楚内存是 M * log N.int n, m, idx, root[M];int build(int l, int r)
{int q idx;if(l r){tr[q].fa l;return q;}int mid l r 1;tr[q].l build(l, mid), tr[q].r build(mid 1, r);return q;
}int modify(int p, int l, int r, int x, int v)
{int q idx;tr[q] tr[p];if(l r){tr[q].fa v;return q;}int mid l r 1;if(x mid) tr[q].l modify(tr[p].l, l, mid, x, v);else tr[q].r modify(tr[p].r, mid 1, r, x, v);return q;
}void query(int q, int l, int r, int x, int fa, int rk)
{if(l r){fa tr[q].fa, rk tr[q].rk;return;}int mid l r 1;if(x mid) query(tr[q].l, l, mid, x, fa, rk);else query(tr[q].r, mid 1, r, x, fa, rk);
}int find(int q, int x, int rk)
{int fa;query(q, 1, n, x, fa, rk);if(fa x) return x;return find(q, fa, rk);
}void add(int q, int l, int r, int x)
{if(l r){tr[q].rk;return;}int mid l r 1;if(x mid) add(tr[q].l, l, mid, x);else add(tr[q].r, mid 1, r, x);
}int main()
{scanf(%d%d, n, m);root[0] build(1, n);for(int i 1; i m; i){int op, a, b, k;scanf(%d, op);if(op ! 2){scanf(%d%d, a, b);int pa, da, pb, db;pa find(root[i - 1], a, da), pb find(root[i - 1], b, db);//这个版本信息的更新千万别忘放在最前面!root[i] root[i - 1];if(op 1){if(pa pb) continue;//高度小的树连在高度大的树下方.if(da db) swap(a, b), swap(da, db), swap(pa, pb);root[i] modify(root[i - 1], 1, n, pa, pb);if(da db) add(root[i], 1, n, pb);}else{printf(%d\n, int(pa pb));}}else{scanf(%d, k);root[i] root[k];}}
}
平衡树
11. 无旋Treap
P3369 【模板】普通平衡树
无旋treap
#includebits/stdc.h
using namespace std;
const int N 100010, INF 0x3f3f3f3f;
mt19937 rnd(0);
struct node
{int key, l, r, sz, rnk;
}tr[N];
int tot, root;
void pushup(int u)
{tr[u].sz tr[tr[u].l].sz tr[tr[u].r].sz 1;
}
void split(int rt, int a, int b, int k)
{if(rt 0){a b 0;return;}if(tr[rt].key k){a rt;split(tr[a].r, tr[a].r, b, k);}else{b rt;split(tr[b].l, a, tr[b].l, k);}pushup(rt);
}
void merge(intrt, int a, int b)
{if(a 0 || b 0){rt a b;return;}if(tr[a].rnk tr[b].rnk){rt b;merge(tr[b].l, a, tr[b].l);}else{rt a;merge(tr[a].r, tr[a].r, b);}pushup(rt);
}
int add_node(int val)
{tr[tot] {val, 0, 0, 1, rnd()};return tot;
}
void insert(int rt, int val)
{int x 0, y 0, nnode add_node(val);split(rt, x, y, val);merge(x, x, nnode);merge(rt, x, y);
}
void remove(int rt, int val)
{int x 0, y 0, z 0;split(rt, x, y, val);split(x, x, z, val - 1);merge(z, tr[z].l, tr[z].r);merge(x, x, z);merge(rt, x, y);
}
int get_kth(int rt, int k)
{while(tr[tr[rt].l].sz 1 ! k){if(tr[tr[rt].l].sz k) rt tr[rt].l;else{k - tr[tr[rt].l].sz 1;rt tr[rt].r;}}return tr[rt].key;
}
int get_rank(int rt, int val)
{int x 0, y 0;split(rt, x, y, val - 1);int res tr[x].sz 1;merge(rt, x, y);return res;
}
int get_pre(intrt, int val)
{int x 0, y 0;split(rt, x, y, val - 1);int res get_kth(x, tr[x].sz);merge(rt, x, y);return res;
}
int get_scc(int rt, int val)
{int x 0, y 0;split(rt, x, y, val);int res get_kth(y, 1);merge(rt, x, y);return res;
}
void build()
{add_node(INF);root 1;tr[root].sz 0;
}
int main()
{int n;scanf(%d, n);build();for(int i 1; i n; i){int op, x;scanf(%d%d, op, x);if(op 1){insert(root, x);}else if(op 2){remove(root, x);}else if(op 3){printf(%d\n, get_rank(root, x));}else if(op 4){printf(%d\n, get_kth(root, x));}else if(op 5){printf(%d\n, get_pre(root, x));}else{printf(%d\n, get_scc(root, x));}}return 0;
}P3391 【模板】文艺平衡树
无旋treap
Treap - OI Wiki (oi-wiki.org)
12. P3380 【模板】二逼平衡树树套树 补
线段树套 无旋treap
树链剖分
13. Query on a tree
给一棵树有两个操作修改边权查询 从 u u u 到 v v v 的路径的边的最大值.
树链剖分裸题把边权下沉至点权.
#includebits/stdc.h
#pragma GCC optimize(2)
using namespace std;
const int N 10010, M N * 2, INF 0x3f3f3f3f;int h[N], e[M], ne[M], we[M], wv[N], idx;
int n;inline void add(int a, int b, int c)
{e[idx] b, ne[idx] h[a], we[idx] c, h[a] idx;
}int sz[N], fa[N], dep[N], son[N];
void dfs1(int u, int father, int depth)
{sz[u] 1, fa[u] father, dep[u] depth;son[u] 0;for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(v father) continue;wv[v] we[i];dfs1(v, u, depth 1);sz[u] sz[v];if(sz[son[u]] sz[v]) son[u] v;}
}
int id[N], top[N], nw[N], cnt;void dfs2(int u, int t)
{id[u] cnt, nw[cnt] wv[u], top[u] t;if(!son[u]) return;dfs2(son[u], t);for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(v fa[u] || v son[u]) continue;dfs2(v, v);}
}struct node
{int l, r, mmax;
}tr[N * 4];void pushup(int u)
{int t1 tr[u 1].mmax, t2 tr[u 1 | 1].mmax;tr[u].mmax t1 t2 ? t1 : t2;
}void build(int u, int l, int r)
{tr[u] {l, r};if(l r){tr[u].mmax nw[l];}else{int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pushup(u);}
}int query(int u, int l, int r)
{if(l tr[u].l tr[u].r r) return tr[u].mmax;int mid tr[u].l tr[u].r 1;int res 0;if(l mid){int t query(u 1, l, r);if(t res) res t;}if(r mid){int t query(u 1 | 1, l, r);if(t res) res t;}return res;
}void modify(int u, int x, int y)
{if(tr[u].l x tr[u].r x) tr[u].mmax y;else{int mid tr[u].l tr[u].r 1;if(x mid) modify(u 1, x, y);else if(x mid) modify(u 1 | 1, x, y);pushup(u);}
}int query_path(int a, int b)
{if(a b) return 0;int res 0;while(top[a] ! top[b]){if(dep[top[a]] dep[top[b]]) swap(a, b);int t query(1, id[top[a]], id[a]);if(t res) res t;a fa[top[a]];}if(dep[a] dep[b]) swap(a, b);int t query(1, id[b] 1, id[a]);if(t res) res t;return res;
}int main()
{int T;scanf(%d, T);while(T--){memset(h, -1, sizeof h);idx 0, cnt 0;scanf(%d, n);for(int i 1; i n; i){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c), add(b, a, c);}dfs1(1, -1, 1);dfs2(1, 1);build(1, 1, n);char op[10];while(scanf(%s, op) *op ! D){int a, b;scanf(%d%d, a, b);if(*op Q) printf(%d\n, query_path(a, b));else{int edge 2 * (a - 1);int u e[edge], v e[edge ^ 1];if(u fa[v]) modify(1, id[v], b);else modify(1, id[u], b);}}}return 0;
}15.Problem - 5405
题意给出一棵节点上有权的树两种操作
1.修改一个点的权 w i w_i wi
2.询问 u , v u,v u,v求 ∑ w i ∗ w j ∑w_i∗w_j ∑wi∗wj, 其中 i到j的路径 和 u到v的路径 有公共点
难不会
16. 染色
给定一棵有 n n n 个节点的无根树和 m m m 个操作操作有 2 2 2 类
1、将节点 a a a 到节点 b b b 路径上所有点都染成颜色 c c c
2、询问节点 a a a 到节点 b b b 路径上的颜色段数量连续相同颜色被认为是同一段如 “ 112221 112221 112221” 由 3 3 3 段组成“ 11 11 11”、“ 222 222 222” 和 “ 1 1 1”。
请你写一个程序依次完成这 m m m 个操作。
链剖裸题套个线段树。
这题唯一难的就在于查询颜色段的时候要考虑跨越查询区间时要记得去掉重复的部分。合并区间的时候看一下两边区间相接的部分是否是相同颜色相同的话减掉就可以了。
线段树维护这一段区间的左端点颜色右端点颜色区间不同颜色的和记得 l a z y lazy lazy 标记。
动态树
18. OTOCI补
一个只有点的图
三种操作link 操作, update 操作query 链上的点权和
动态树LCT
其他
5. Trains and Statistic
有 N N N 个车站 [ 1 , n ) [1,n) [1,n) 的车站可以买到编号为 i 1 i1 i1 到 a i a_i ai 的车站的票,设 p i j p_{ij} pij 为 i i i 车站到 j j j 车站的最少买票数求 ∑ i 1 n ∑ j i 1 n p i j \sum\limits_{i1}^{n}\sum\limits_{ji 1}^{n}p_{ij} i1∑nji1∑npij n ≤ 1 0 5 n \le 10^5 n≤105
设 d p i dp_i dpi 为从第 i i i 个车站出发到达 [ i 1 , n ] [i1,n] [i1,n] 车站需要的最小车票数量之和. 我们考虑 d p i dp_i dpi 从哪个 d p m dp_m dpm 转移过来答案是在 m ∈ [ i 1 , a i ] m \in [i 1,a_i] m∈[i1,ai] 找到 a m a_m am 最小的 m m m. 可以这么考虑从 i i i 开始走两步可以到达的点经过 m m m 可以到达最远的点其他点能到的 m m m 也可以到. 因此拿 m m m 当中转节点是最优的.
9. BZOJ4990 Why Did the Cow Cross the Road II
上下有两个长度为n、位置对应的序列A、B两个序列都是全排列
其中数的范围均为 1 ∼ n 1\sim n 1∼n。若 a b s ( A [ i ] − B [ j ] ) 4 abs(A[i]-B[j]) 4 abs(A[i]−B[j])4
则 A [ i ] A[i] A[i] 与 B [ j ] B[j] B[j] 间可以连一条边。现要求在边与边不相交的情况下的最大的连边数量。
找到 A [ i ] A[i] A[i] 对应的 B B B 数组中的 9 9 9 个数字然后把这 9 9 9 个数字按照降序排序推进同一个数组里面最后在此数组求最长上升子序列就是答案.
P1439 【模板】最长公共子序列
给出 1 , 2 , … , n 1,2,\ldots,n 1,2,…,n 的两个排列 P 1 P_1 P1 和 P 2 P_2 P2 求它们的最长公共子序列。
对于 P 1 P_1 P1 的每一个数 i i i记录 s e q [ i ] seq[i] seq[i] 为 i i i 在 P 2 P_2 P2 中的位置. 那么答案就是 s e q seq seq 的最长上升子序列。因为 P 1 P_1 P1 的下标上升的同时要保证 P 2 P_2 P2 的下标也是上升的的.
2. Problem - 961E. Tufurama
#includebits/stdc.h
#define x first
#define y secondusing namespace std;typedef long long ll;
const int N 200010;
ll ans;
int a[N], n, tr[N];
int lowbit(int x)
{return x -x;
}
int sum(int x)
{int res 0;for(int i x; i; i - lowbit(i)) res tr[i];return res;
}
void add(int x, int c)
{for(int i x; i n; i lowbit(i)) tr[i] c;
}
typedef pairint, int P;int main()
{scanf(%d, n);for(int i 1; i n; i) scanf(%d, a[i]);priority_queueP, vectorP, greaterP que;for(int i 1; i n; i){while(que.size() que.top().x i){add(que.top().y, -1);que.pop();}//printf(%d %d %d\n, i, a[i], sum(a[i]));ans sum(min(a[i], n));que.push({a[i], i});add(i, 1);}printf(%lld\n, ans);return 0;
}4. Problem - 980E - Codeforces
题意给定一个 n n n 个结点的树第 i i i 号点的权值是 2 i 2^i 2i现在删除 k k k 个点并且保证剩下的节点都是连通的而且要保证权值之和最大。问需要删除哪些结点
可以考虑贪心由于我们只要能选择较大的结点就一定要选因为此节点的权值大于比他编号小的所有节点权值之和。因为 n n n 号点是必须要选择的因此以 n n n 号点为根把 n n n 加入树 T ′ T T′ 中。现在开始从大到小把结点加入树中然后找到从 i i i 到 T ′ T T′ 的最短路径。
法一采用树上倍增的方法快速解决记录一下已经在 T ′ T T′ 中的结点然后倍增法计算出来它到最近的在 T ′ T T′ 中的祖先的距离。
法二采用树状数组。怎样优化一个新节点 (记为 u u u ) 到离 T ′ T T′ 中点 (记为 v v v) 的距离的最小值即 u u u 到根节点的距离减去 u u u 到根节点的路径中已标明的结点的数量。已标明的结点数量怎么算呢建立一个树的深搜序相当于单点修改树的结点权值把0改为1然后查询某一结点到根节点的结点权值之和. 那么修改某个结点 u u u 权值影响路径权值之和的结点是以 u u u 为子树的结点。那么在 [ i n [ u ] , o u t [ u ] ] [in[u], out[u]] [in[u],out[u]] 之间加1即可.
法二代码万分小心树状数组那俩函数千万别写错
#includebits/stdc.h
using namespace std;
const int N 1000010, M N * 2;
int h[N], e[M], ne[M], idx;
int n, m, tr[N];
vectorint ans;
bool st[N];
inline void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx;
}
int lowbit(int x)
{return x -x;
}
//别把两个函数搞反
void modify(int x, int c)
{//别写成 i lowbit(x)for(int i x; i n; i lowbit(i)){//别写成 tr[i] xtr[i] c;}
}
int sum(int x)
{int res 0;for(int i x; i; i - lowbit(i)){res tr[i];}return res;
}
int cnt, in[N], out[N], fa[N], dep[N];void dfs(int u, int father, int depth)
{in[u] cnt, fa[u] father, dep[u] depth;for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(v father) continue;dfs(v, u, depth 1);}out[u] cnt;
}int main()
{memset(h, -1, sizeof h);scanf(%d%d, n, m);m n - m;for(int i 1; i n; i){int a, b;scanf(%d%d, a, b);add(a, b), add(b, a);}dfs(n, 0, 1);for(int i n; i; i--){if(dep[i] - sum(in[i]) m){//printf(** %d %d\n, dep[i], sum(in[i]));for(int u i; u !st[u]; u fa[u]){st[u] true;modify(in[u], 1), modify(out[u] 1, -1);m--;//printf(%d %d %d\n, i, u, m);}}}for(int i 1; i n; i) if(!st[i]) ans.push_back(i);sort(ans.begin(), ans.end());for(int i 0, sz ans.size(); i sz; i){printf(%d%c, ans[i], i 1 sz ? \n : );}return 0;
}
