习题1最大连续区间维护，例题3的简化版：
题链：
Hotel
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 5e4 + 10; struct node{ int l, r; int fmax,lmax,rmax; int lazy; }tr[N<<2]; void pushdown(node &tr,int lazy){ tr.fmax = lazy * (tr.r - tr.l + 1); tr.lmax = tr.rmax = tr.fmax; tr.lazy = lazy; } void pushdown(int u){ if(tr[u].lazy != -1){ pushdown(tr[u<<1],tr[u].lazy) ,pushdown(tr[u<<1|1],tr[u].lazy); tr[u].lazy = -1; } } void pushup(node &tr,node &l,node &r){ tr.fmax = max(max(l.fmax,r.fmax),l.rmax + r.lmax); tr.lmax = l.lmax + (l.lmax == l.r - l.l + 1 ? r.lmax : 0); tr.rmax = r.rmax + (r.rmax == r.r - r.l + 1 ? l.rmax : 0); } void pushup(int u){ pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r){ tr[u].l = l,tr[u].r = r,tr[u].fmax = tr[u].lmax = tr[u].rmax = 1,tr[u].lazy = -1; if(l == r) return; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } int findleft(int u,int v){ if(tr[u].l == tr[u].r) return tr[u].l; pushdown(u); if(tr[u<<1].fmax >= v) return findleft(u<<1,v); if(tr[u<<1].rmax + tr[u<<1|1].lmax >= v) return tr[u<<1].r - tr[u<<1].rmax + 1; return findleft(u<<1|1,v); } void modify(int u,int l,int r,int v){ if(tr[u].l >= l && tr[u].r <= r){ pushdown(tr[u],v); return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r,v); if(r > mid) modify(u<<1|1,l,r,v); pushup(u); } int main(){ int n,m; cin >> n >> m; build(1,1,n); while(m--){ int op; scanf("%d",&op); if(op == 1){ int x; scanf("%d",&x); if(tr[1].fmax >= x) { int l = findleft(1,x); printf("%d\n",l); modify(1,l,l+x-1,0); } else { printf("0\n"); } } else{ int l,r; scanf("%d%d",&l,&r); modify(1,l,l+r-1,1); } } return 0; }
习题2批量替换，例题1的变式
就只是根据操作变了个pushdown。
根节点tr[1].sum,查询树的总和
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 10; struct node{ int l,r; int sum; int lazy; }tr[N<<2]; void pushdown(node &tr,int lazy){ tr.sum = lazy * (tr.r - tr.l + 1); tr.lazy = lazy; } void pushdown(int u){ if(tr[u].lazy != -1){ pushdown(tr[u<<1],tr[u].lazy),pushdown(tr[u<<1|1],tr[u].lazy); tr[u].lazy = -1; } } void pushup(int u){ tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum; } void build(int u,int l,int r){ tr[u] = {l,r,1,-1}; if(l == r) return; 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 v){ if(tr[u].l >= l && tr[u].r <= r){ pushdown(tr[u],v); return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r,v); if(r > mid) modify(u<<1|1,l,r,v); pushup(u); } int main(){ int t; cin >> t; for(int Case = 1;Case <= t;Case++){ int n,m; scanf("%d%d",&n,&m); build(1,1,n); while(m--){ int l,r,v; scanf("%d%d%d",&l,&r,&v); modify(1,l,r,v); } printf("Case %d: The total value of the hook is %d.\n",Case,tr[1].sum); } return 0; }
2.批量自适应修改
题链
Q - Hotel
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
卡壳点:
忘记build，递归的 tr[u].l == tr[u].r == 写成 =
区间修改，题目给的时l和len，以为是l和r导致错误
用l和len表示r错误，写成了l + len，应该是l + len -1 ；
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 5e4 + 10; struct node{ int l, r; int fmax,lmax,rmax; int lazy; }tr[N<<2]; void pushdown(node &tr,int lazy){ tr.fmax = lazy * (tr.r - tr.l + 1); tr.lmax = tr.rmax = tr.fmax; tr.lazy = lazy; } void pushdown(int u){ if(tr[u].lazy != -1){ pushdown(tr[u<<1],tr[u].lazy) ,pushdown(tr[u<<1|1],tr[u].lazy); tr[u].lazy = -1; } } void pushup(node &tr,node &l,node &r){ tr.fmax = max(max(l.fmax,r.fmax),l.rmax + r.lmax); tr.lmax = l.lmax + (l.lmax == l.r - l.l + 1 ? r.lmax : 0); tr.rmax = r.rmax + (r.rmax == r.r - r.l + 1 ? l.rmax : 0); } void pushup(int u){ pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r){ tr[u].l = l,tr[u].r = r,tr[u].fmax = tr[u].lmax = tr[u].rmax = 1,tr[u].lazy = -1; if(l == r) return; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } int findleft(int u,int v){ if(tr[u].l == tr[u].r) return tr[u].l; pushdown(u); if(tr[u<<1].fmax >= v) return findleft(u<<1,v); if(tr[u<<1].rmax + tr[u<<1|1].lmax >= v) return tr[u<<1].r - tr[u<<1].rmax + 1; return findleft(u<<1|1,v); } void modify(int u,int l,int r,int v){ if(tr[u].l >= l && tr[u].r <= r){ pushdown(tr[u],v); return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r,v); if(r > mid) modify(u<<1|1,l,r,v); pushup(u); } int main(){ int n,m; cin >> n >> m; build(1,1,n); while(m--){ int op; scanf("%d",&op); if(op == 1){ int x; scanf("%d",&x); if(tr[1].fmax >= x) { int l = findleft(1,x); printf("%d\n",l); modify(1,l,l+x-1,0); } else { printf("0\n"); } } else{ int l,r; scanf("%d%d",&l,&r); modify(1,l,l+r-1,1); } } return 0; }
前提条件
是区间修改，区间查询，且修改操作的修改的值是根据具体节点储存的值而变化的，比如开根，幂，替换，乘除；
新做的题里发现替换可以直接批量赋值来实现，属于等值修改。
情景
对一个序列里的元素执行k次自适应操作，每次操作一个区间，然后询问区间内所有元素的值。
也有询问某个区间内所有值经过某种处理后的值。（此种问法是询问时用一个变量储存找到的值，经过处理后返回
例题1单种操作
Can you answer these queries?
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
主要就是把modify的递归条件改成了和传统query操作相同的有交集
复杂度比较高，需要一些剪枝
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N = 1e5 + 10; struct node{ int l,r; ll sum; }tr[N<<2]; ll w[N]; void pushup(int u){ tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum; } void build(int u,int l,int r){ tr[u] = {l,r,w[r]}; // cout << w[r] << endl; if(l == r) return; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } ll query(int u,int l,int r){ if(tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } // cout << tr[u].sum; ll res =0 ; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) res += query(u<<1,l,r); if(r > mid) res += query(u<<1|1,l,r); return res; } void modify(int u,int l,int r){ if(tr[u].l == tr[u].r) tr[u].sum = sqrt(tr[u].sum); else{ if(tr[u].sum == tr[u].r - tr[u].l + 1) return; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r); if(r > mid) modify(u<<1|1,l,r); pushup(u); } } int main() { int T = 1; int n, m; while (cin >> n) { for(int i = 1;i <= n;i++) scanf("%lld", &w[i]); build(1,1, n); printf("Case #%d:\n", T++); scanf("%d", &m); while (m--) { int op, l, r; scanf("%d %d %d", &op, &l, &r); if (l > r) swap(l, r); // cout << l << " " << r << endl; if (op) printf("%lld\n", query(1,l, r)); else modify(1,l, r); } printf("\n"); } return 0; }
例题2多种操作
Transformation HDU - 4578
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
题解代码
Transformation HDU - 4578 （线段树，审题很重要）_Soar-的博客-CSDN博客
#include<bits/stdc++.h> using namespace std; #define lson i<<1,l,m #define rson i<<1|1, m+1,r const int mod = 10007; const int maxn=1e5+10; int x[maxn<<2],flag[maxn<<2]; x是tr，flag是lazy void pushup(int i,int l,int r) { if(!flag[i<<1] || !flag[i<<1|1])左右子节点无值 flag[i] = 0; else if(x[i<<1] != x[i<<1|1])左右子节点有值且不等 flag[i] = 0; else flag[i]=1,x[i]=x[i<<1];左右子节点值相等 所以这是一个记录懒标记的函数，如果左右子节点的值相同，就上传。 通过用父节点的节点的值来代表子节点的值接受处理，降低复杂度 } void pushdown(int i,int l,int r) { if(flag[i]) { flag[i<<1] = flag[i<<1|1] =1; x[i<<1] = x[i<<1|1] = x[i]; flag[i]=0; } 这是一个下传懒标记并处理懒标记的函数，如果有懒标记，说明这个节点是代表子节点接受处理的，所以直接将值下传到子节点，然后清除懒标记 } void update(int ql,int qr,int p,int v,int i,int l,int r) { 妙：直接传入op，也就是p，根据p的值进行不同操作，减少了很多赘余的代码。 我写时想的是写3个modify，也就是update，根据op不同，调用不同的modify，麻烦得很。 if(ql<=l && qr>=r && flag[i]) 这里是有懒标记，且节点区间全都在需要处理的区间内，直接处理当前节点，然后pushdown，就可以实现区间处理 { if(p==1) x[i] = (x[i]+v)%mod; else if(p==2) x[i] = (x[i]*v)%mod; else x[i] = v; 修改当前节点值的话是不需要pushup的，因为pushup的操作是根据子节点的值来决定是否赋予当前节点一个懒标记，只修改当前节点值，代表当前节点已经是叶子节点，或者左右节点值相同，所以就算pushup了，懒标记还是会保持原有状态 return; } pushdown(i,l,r); 可能没有懒标记，会需要逐个单点修改，所以用两个if的原始query递归形式 int m = (l+r)>>1; if(ql<=m) update(ql,qr,p,v,lson); if(qr>m) update(ql,qr,p,v,rson); 进行子节点单点值修改操作后都需要pushup，来更新懒标记状态 pushup(i,l,r); } int query(int ql,int qr,int num,int i,int l,int r) l,r是当前节点的l，r { if(flag[i] && ql<=l && qr>=r) { int ans=1; for(int j=0;j<num;j++)ans=(ans*x[i])%mod;//pow操作，每次pow取余，如果是10007的三次方就有可能爆int了，所以用循环来每次操作后取余 ans=(ans*(r-l+1))%mod; return ans; } pushdown(i,l,r); int m = (l+r)>>1; int ans=0; if(ql<=m)ans+=query(ql,qr,num,lson); if(qr>m)ans+=query(ql,qr,num,rson); return ans%mod; } int main() { int n,m; while(cin>>n>>m,n||m) { memset(flag,1,sizeof flag); memset(x,0,sizeof x); int p,x,y,v; while(m--) { scanf("%d%d%d%d",&p,&x,&y,&v); if(p>=1 && p<=3)update(x,y,p,v,1,1,n); else printf("%d\n",query(x,y,v,1,1,n)); } } }
经过模仿后得到的acwing版代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 10,mod = 10007; struct node{ int l,r; int sum; int lazy; }tr[N<<2]; void pushup(int u){ if(!tr[u<<1].lazy || !tr[u<<1|1].lazy) tr[u].lazy = 0; 有一个子节点懒标记是0（当前节点的子节点的两个子节点的值不相等）则当前节点懒标记就变成0，由此可以推断出，懒标记的含义是表示当前节点的子树里所有节点的值 ，都相等，可以直接用当前节点的值来进行操作。 else if(tr[u<<1].sum != tr[u<<1|1].sum) tr[u].lazy = 0; else tr[u].lazy = 1,tr[u].sum = tr[u<<1].sum; } void pushdown(int u){ if(tr[u].lazy){ tr[u<<1].lazy = tr[u<<1|1].lazy = 1; tr[u<<1].sum = tr[u<<1|1].sum = tr[u].sum; tr[u].lazy = 0; } } void build(int u,int l,int r){ 只有叶子节点才能初始化成lazy1 if(l == r){ tr[u] = {l,r,0,1}; return; } tr[u] = {l,r}; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void modify(int u,int l,int r,int op,int v){ if(tr[u].l >= l && tr[u].r <= r && tr[u].lazy){ if(op == 1) tr[u].sum = (tr[u].sum + v) % mod; else if(op == 2) tr[u].sum = (tr[u].sum * v)%mod; else { tr[u].sum = v; } return; } pushdown(u); 有懒标记要先处理，然后再运算。 int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r,op,v); if(r > mid) modify(u<<1|1,l,r,op,v); pushup(u); } int query(int u,int l,int r,int v){ if(tr[u].l >= l && tr[u].r <= r && tr[u].lazy){ int res = 1; for(int i = 0;i < v;i++) res = (res * tr[u].sum) % mod; res = res * (tr[u].r - tr[u].l + 1) % mod; return res; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; int res = 0; if(l <= mid) res = (res + query(u<<1,l,r,v) ) %mod; if(r > mid) res = (res + query(u<<1|1,l,r,v)) % mod; return res % mod; } int main(){ int n,m; while(cin >> n >> m,n||m){ // for(int i=0;i <= N << 2;i++) tr[i]= {0,0,0,0}; build(1,1,n); int op,l,r,v; while(m--){ scanf("%d%d%d%d",&op,&l,&r,&v); // cout << op << " " << l << " " << r << " " << v << endl; if(op >=1 && op <= 3){ modify(1,l,r,op,v); } else { printf("%d\n",query(1,l,r,v)); } } } return 0; }
注意
注意点就是非数组模拟节点的代码要用build初始化，然后叶子节点懒标记初始化为1，因为代表的含义是两个子节点值是否相等 懒标记区间自适应修改至少耗时2s，如果能操作简单，能用简单的语句来确定是否可以省略操作（如例题1tr[u].r - tr[u].l + 1) == tr[u].sum)判断区间内是否全为1而可以省略掉区间开方操作。
其他套路：
涉及到一个多组输入的套路
前提条件是没有明确组数，结束关键词的多组数据集输入
取反while（~scanf(“%d”,&n)
和while(scanf(“%d”,&n) != EOF)
还有while（cin >> n)三种形式
习题1开方单点剪枝1e5 + 2e5，常数n为6以内：
题链
花神游历各国
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
比较
与例题1是同一题型，但例题1的题解里没有用到fmax来维护区间最大值，而是直接用
tr[u].sum 与 tr[u].r - tr[u].l +1 是否相等来判断是否return。
例题1的做法仅限于元素最小是1的情况下，
习题1的元素最小为0，所以不能用这种做法。
于是归结出第一个剪枝套路
卡壳点：
没注意node内的maxn也要在modify内开方。
注意操作时除了l，r之外的属性基本都要处理
build初始化，注意叶子节点和根节点的初始化可能会不同。
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N = 1e5 + 10; struct node{ int l,r; ll sum; int maxn; }tr[N<<2]; ll w[N]; void pushup(int u){ tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum; tr[u].maxn = max(tr[u<<1].maxn,tr[u<<1|1].maxn); } void build(int u,int l,int r){ if(l == r){ tr[u] = {l,r,w[r],w[r]}; return; }tr[u] = {l,r,0,0 }; // cout << w[r] << endl; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } ll query(int u,int l,int r){ if(tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } // cout << tr[u].sum; ll res =0 ; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) res += query(u<<1,l,r); if(r > mid) res += query(u<<1|1,l,r); return res; } void modify(int u,int l,int r){ if(tr[u].maxn <= 1) return; if(tr[u].l == tr[u].r) { tr[u].sum = sqrt(tr[u].sum); tr[u].maxn = sqrt(tr[u].maxn);return;} int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r); if(r > mid) modify(u<<1|1,l,r); pushup(u); } int main() { int T = 1; int n, m; while (cin >> n) { for(int i = 1;i <= n;i++) scanf("%lld", &w[i]); build(1,1, n); // printf("Case #%d:\n", T++); scanf("%d", &m); while (m--) { int op, l, r; scanf("%d %d %d", &op, &l, &r); // cout << l << " " << r << endl; if (op==1) printf("%lld\n", query(1,l, r)); else modify(1,l, r); } printf("\n"); } return 0; }
套路：
区间单点修改开平方剪枝：
前提条件，
对区间进行开平方，并需要动态维护区间和：
应对
节点中用fmax维护区间最值，modify时区间最值<=1就直接return。
如果节点值最小是1的话，直接通过判断tr[u].sum 与 tr[u].r - tr[u].l +1 是否相等可以确定是否需要剪枝。（区间值全为1）
3.区间染色
普通例题
题链
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
疑问
染过色后lazy被pushdown下移会不会有影响？
：modify经过lazy所在节点时，也就是lazy底下有节点被另外染色了此时lazy下移，这个节点没资格再代表其下的所有节点了。
判断是否颜色相同可以用个pushup，见批量自适应修改里的例题2多种操作里的pushup，但没什么必要。
代码
统计颜色种类及段数。
卡壳点：segment fault
用N作为下标访问元素时要养成写N-1的习惯，防止出现数组越界
#include <bits/stdc++.h> #define rep(i, n) for (int i = 1; i <= (n); ++i) using namespace std; typedef long long ll; const int N = 1E4 + 10; cou要开8011 int cou[N]; struct node { int l, r; int lazy; }t[N << 2]; void pushdown(node& op, int lazy) { op.lazy = lazy; } void pushdown(int x) { if (!t[x].lazy) return; pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy); t[x].lazy = 0; } void build(int l, int r, int x = 1) { t[x] = { l, r, 0 }; if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); } void modify(int l, int r, int c, int x = 1) { if (l <= t[x].l && r >= t[x].r) { pushdown(t[x], c); return; } 写错条件成叶子节点。 pushdown(x); int mid = t[x].l + t[x].r >> 1; 忘记/2 if (l <= mid) modify(l, r, c, x << 1); if (r > mid) modify(l, r, c, x << 1 | 1); 忘记变成x<<1|1 } int last = 0; //表示上一次碰到的颜色, 记得当遍历叶子结点时没有颜色的时候也要记录. void ask(int x = 1) { if (last != t[x].lazy) cou[t[x].lazy]++; 判断是否间隔开 if (t[x].lazy || t[x].l == t[x].r) { last = t[x].lazy; return; } 当前节点lazy不为0，表示当前节点下的所有节点都经过区间修改，变成一样的颜色，不用再继续深入。 // 有标记直接进上面的语句了，不需要pushdown 遍历整棵树 ask(x << 1), ask(x << 1 | 1); 先左后右保证last一定在t[x]的左边 } int main() { int n; while (~scanf("%d", &n)) { build(1, 8010); last = 0; memset(cou, 0, sizeof cou); o1查询的优化。 rep(i, n) { int l, r, c; scanf("%d %d %d", &l, &r, &c); modify(l + 1, r, c + 1); //这里是为了让建树区间下标从1开始, 涂色记录也从1开始 } ask(); rep(i, 8010) if (cou[i]) printf("%d %d\n", i - 1, cou[i]); printf("\n"); } return 0; }
离散化例题
套路：
lazy代替sum：
区间染色
前提条件：
题目不需要求区间长度，操作时各种值无优先级，在区间上互相进行区间覆盖操作，求最后的状态。
情景
操作之间存在覆盖，遮挡的影响
之前画的一些线段可能会被后面的一些线段所覆盖 给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。
