总算是把线段树和树状数组的例题给干完了，晚上思考下该继续做练习还是干别的专题，目前想法是干别的专题，只要每天重新做几道例题，反复做到滚瓜烂熟，遇到时能举一反一就好了。
线段树
1.批量等值修改
前提条件
是要区间修改，区间查询，且修改操作修改的值是相同的，比如批量+1，批量-1.
有一种特例是批量替换，
情景
一般是要对一个数组执行k次操作，每次改变其中一个区间内所有元素的值，然后询问一个区间内所有元素的最值或总和，
例题1区间等值操作
题解代码
void Pushdown(int k){ //更新子树的lazy值，这里是RMQ的函数，要实现区间和等则需要修改函数内容 if(lazy[k]){ //如果有lazy标记 lazy[k<<1] += lazy[k]; //更新左子树的lazy值 lazy[k<<1|1] += lazy[k]; //更新右子树的lazy值 t[k<<1] += lazy[k]; //左子树的最值加上lazy值 t[k<<1|1] += lazy[k]; //右子树的最值加上lazy值 lazy[k] = 0; //lazy值归0 } }
注意懒标记中储存区间修改的值与长度的乘积，大概率开long long
struct node { int l, r; ll val; ll lazy; }t[N << 2]; void pushdown(node& op, ll lazy) { op.val += lazy * (op.r - op.l + 1); 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\没有值传入时，默认初始化为1) { t[x] = { l, r, w[l], 0 }; if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); pushup(x); } void modify(int l, int r, int c, int x = 1) { if (l <= tr[x].l && r >= tr[x].r) { pushdown(tr[x], c); return; }\通过打标记的方法来赋值 pushdown(x); 操作时遇到了懒标记就处理下（懒的思想，顺路就搞下，不顺路就拖着不干） int mid = tr[x].l + tr[x].r >> 1; if (l <= mid) modify(l, r, c, x << 1);\modify的递归也变成了和线段树单点修改query里的递归形式，有交集就递归。 if (r > mid) modify(l, r, c, x << 1 | 1); pushup(x); } ll ask(int l, int r, int x = 1) { if (l <= t[x].l && r >= tr[x].r) return tr[x].val; pushdown(x); //query的唯一变化就是加上了一个pushdown(); int mid = tr[x].l + tr[x].r >> 1; ll res = 0; if (l <= mid) res += ask(l, r, x << 1); if (r > mid) res += ask(l, r, x << 1 | 1); return res; } int main() { int n, m; cin >> n >> m; rep(i, n) scanf("%d", &w[i]); build(1, n); while (m--) { char op[2]; int l, r; scanf("%s %d %d", op, &l, &r); if (*op == 'Q') printf("%lld\n", ask(l, r)); else { int c; scanf("%d", &c); modify(l, r, c); } } return 0; }
自己写的acwing式代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5 + 10; typedef long long ll; struct node{ int l,r; ll sum; ll lazy; }tr[N<<2]; int w[N]; 传入的lazy写成int类型，导致卡壳非常久。 晚上再写一遍。 注意不要混淆long long和int void pushdown(node &x,ll lazy){ x.sum += lazy*(x.r - x.l + 1); x.lazy += lazy; } //一次调用需要从外界赋值，打上lazy，还有一次调用不需要从外界赋值解放lazy，所以分开写。 void pushdown(int u){ if(!tr[u].lazy) return; pushdown(tr[u<<1],tr[u].lazy),pushdown(tr[u<<1|1],tr[u].lazy); tr[u].lazy = 0; } 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 = l,tr[u].r = r,tr[u].sum =w[r]; 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; ll res = 0; int mid = tr[u].l + tr[u].r >> 1; pushdown(u); 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,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; for(int i =1;i <= n;i++) scanf("%d",&w[i]); build(1,1,n); while(m--){ char op[2]; int l,r; scanf("%s%d%d",op,&l,&r); if(*op == 'Q') printf("%lld\n",query(1,l,r)); else{ int c; scanf("%d",&c); modify(1,l,r,c); } } return 0; }
注意：
线段树的初始化在build里完成，多组数据集时不需要再额外初始化。
例题2线段树区间覆盖，二分查找
区别似乎可以用储存的是什么，还有操作是什么来区分
题解代码
#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 = 5E4 + 10; struct node { int l, r; int val; int lazy; lazy不能初始化为0或1的原因，要区分lazy的是否存在，存在时状态为非空还是空 一般直觉是可以把有花设置为1，无花设置为0，可以用区间长度-查到的数量进行有花和无花数量的查询，所以这个应该不是什么问题，写出来之后再替换下。 }t[N << 2]; void pushdown(node& op, int lazy) { op.val = lazy * (op.r - op.l + 1); op.lazy = lazy; 解除储存的懒标记 理解这个代码的关键点在于这里的符号是等于，而不是+= } void pushdown(int x) { if (t[x].lazy == -1) return; pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1],t[x].lazy); t[x].lazy = -1; 向根部递归，解除所有子树里的节点的懒标记 } void pushup(int x) { t[x].val = t[x << 1].val + t[x << 1 | 1].val; } void build(int l, int r, int x = 1) { t[x] = { l, r, 1, -1 }; if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); pushup(x); } 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; if (l <= mid) modify(l, r, c, x << 1); if (r > mid) modify(l, r, c, x << 1 | 1); pushup(x); } int ask(int l, int r, int x = 1) { //查询[l, r]区间的空花瓶数目 if (l <= t[x].l && r >= t[x].r) return t[x].val; pushdown(x); int mid = t[x].l + t[x].r >> 1; int res = 0; if (l <= mid) res += ask(l, r, x << 1); if (r > mid) res += ask(l, r, x << 1 | 1); return res; 1代表花瓶是空的 } int n, m; int getindex(int a, int c) { //找到[a, n]区间, 第c个可以放花瓶的位置 int l = a, r = n; while (l < r) { int mid = l + r >> 1; if (ask(a, mid) >= c) r = mid; else l = mid + 1; } return l; } int main() { int T; cin >> T; while (T--) { scanf("%d %d", &n, &m); build(1, n); while (m--) { int k, x, y; scanf("%d %d %d", &k, &x, &y); if (k == 1) { int cou = ask(x + 1, n); 找到总共能插的花瓶数量 if (!cou) printf("Can not put any one.\n"); else { int L = getindex(x + 1, 1); 找到第一个能插花瓶的下标 int R = getindex(x + 1, min(y, cou)); //注意要和cou取一个min 找到最后一个插花瓶的地方，或者是最后一个能插花瓶的地方 modify(L, R, 0); l到r的数量设置为0，插花。 printf("%d %d\n", L - 1, R - 1); } } else { int res = y - x + 1 - ask(x + 1, y + 1); x到y的花瓶数量 - x到y的空花瓶数量 res就是非空（被清空）的花瓶数量 modify(x + 1, y + 1, 1); x到y的数量设置为1 1代表花瓶是空的 printf("%d\n", res); } } puts(""); } return 0; }
经过模仿得到的acwing代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 5e4 + 10; 统计的是花瓶数量，不需要开long long， struct node{ int l,r; int sum; int lazy; }tr[N<<2]; void pushdown(int u,int lazy){ 批量修改后，子树内所有的节点状态都相等，所以直接用lazy存状态，然后乘区间长度就可以表示出当前节点下的1状态节点个数，直接赋给sum。 lazy存一个当前节点下的所有节点的状态。 tr[u].sum = lazy * (tr[u].r - tr[u].l + 1); tr[u].lazy = lazy; } void pushdown(int u){ if(tr[u].lazy == -1) return ; pushdown(u<<1,tr[u].lazy),pushdown(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){ build需要和之前的题对比一下 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){ 没什么区别，传统批量等值修改的modify if(l <= tr[u].l && tr[u].r <= r){ pushdown(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 query(int u,int l,int r){ 没什么区别，传统批量等值修改的query if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; int res = 0; if(l <= mid) res += query(u<<1,l,r); if(r > mid) res += query(u<<1|1,l,r); return res; } int n,m; int find(int x,int v){ 找a到n的第v个空花瓶。没有第v个会返回n 二分是要看mid和返回值的关系 int l = x,r = n; while(l < r){ int mid = l + r >> 1; if(query(1,x,mid) >= v) r = mid; else l = mid + 1; } return l; } int main(){ int t; cin >> t; while(t--){ scanf("%d%d",&n,&m); build(1,1,n); while(m--){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op == 1){ l++; int cnt = query(1,l,n); // cout << cnt << endl; if(!cnt) printf("Can not put any one.\n"); else{ int L = find(l,1); int R = find(l,min(r,cnt)); 因为是找最后一个能插花的位置，所以要先用花的数量和空花瓶数量比较下，选出最小的一个，保证find查到的返回值位置是空花瓶。 // cout << L << " " << R << endl; modify(1,L,R,0); printf("%d %d\n",L-1,R-1); } } else{ l++,r++; int res = r - l + 1 - query(1,l,r); modify(1,l,r,1); printf("%d\n",res); } } puts(""); } return 0; }
例题3最大连续区间的维护，给连续区间长度，找端点
与例题2的区别，
此题要求在一个连续的区间上操作，所以是要知道一段区间是否连续，是否足够长，
用节点信息fmax，lmax，rmax来维护区间最大连续，左到右的最大连续，右到左的最大连续
情景：
如果这段时间空闲就安排活动。
因为要找到最左的区间，用深度优先搜索来找。
递归方面倒是和例题2很像，都是有一个左侧空瓶优先。但不会例题2递归做法，还不太懂。
套路
区间合并
前提条件：找连续区间
情景
区间合并，最大连续的情景
每组i向柜台的麋鹿Canmuu申请一组Di连续的房间。
任意两个相邻村庄之间可以通过地道保持连通。八路军司令询问从第 x 个村庄可以到达多少个地道完好的村庄（包括第 x 个村庄本身）。
就是找一段最靠前的符合要求的连续空间分配给每个请求，
应对：
用fmax，lmax，和rmax来维护最大连续。
查询区间，端点如果有优先级
递归优先的情景Canmuu总是选择尽可能小的r值。
就是找一段最靠前的符合要求的连续空间分配给每个请求，
dfs深搜递归查询，有先的放在前面。
一个染色优先度的套路，
前提条件
分色1，和色2，两种颜色
色1优先级高，可以无视色2进行区间染色，优先染无色区间，次优先染色2区间，不能染色1区间
色2不能在色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 = 1E5 + 10; struct node { int l, r; int fmax, lmax, rmax; int lazy; 0代表没时间，1代表有时间。 }t1[N << 2], t2[N << 2]; // 基友, 女神 void pushdown(node& op, int lazy) { 需要标记时使用 op.fmax = lazy * (op.r - op.l + 1); 直接把这个节点标注成了完全连续，进行区间覆盖成1或0 op.lmax = op.fmax, op.rmax = op.fmax; 经过fmax被赋值后，fmax变成了区间长度乘lazy状态，可以直接赋给lmax和fmax op.lazy = lazy; } void pushdown(node t[], int x) { 需要访问子节点时使用。 if (t[x].lazy == -1) return; pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy); t[x].lazy = -1; } 一个输入tr[x],一个输入tr,用地址和引用来区分两个pushdown void pushup(node& p, node& l, node& r) { p.fmax = max(max(l.fmax, r.fmax), l.rmax + r.lmax); p.lmax = l.lmax + (l.lmax == l.r - l.l + 1 ? r.lmax : 0); 如果完全左子节点完全连续，就加上右子节点的从左往右最大连续，是一段连续的区间 p.rmax = r.rmax + (r.rmax == r.r - r.l + 1 ? l.rmax : 0); 如果右子节点完全连续，就加上左子节点的从左往右最大连续。 } void pushup(node t[], int x) { pushup(t[x], t[x << 1], t[x << 1 | 1]); } 节点维护多个信息时写个pushup重载简化代码. 一个简化代码的操作，输入u变换成u<<1,u<<1|1的节点，传入函数引用里。 void build(int l, int r, int x = 1) { t1[x] = t2[x] = { l, r, 1, 1, 1, -1 };lazy初始化为-1其他为1. if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); pushup(t1, x), pushup(t2, x); } int findleft(node t[], int c, int x = 1) { //找到当前树中最左侧有连续c空闲时间的左端点(起始点) 不用担心搜不到结果，因为是用tr[1] 最上层节点的fmax确定过有这样一段连续时间才搜的 if (t[x].l == t[x].r) return t[x].l; 符合条件就return pushdown(t, x); if (t[x << 1].fmax >= c) return findleft(t, c, x << 1); dfs，把1的深度搜完，转战2 if (t[x << 1].rmax + t[x << 1 | 1].lmax >= c) return t[x << 1].r - t[x << 1].rmax + 1; 把2的深度搜完，转战3 搜到了立刻返回， return findleft(t, c, x << 1 | 1); 把3的深度搜完 } 维护最大连续，不需要query， 如果要求某个区间的最大连续的话要l==tr[u].l ,r == tr[u].r然后返回fmax 此题要找最左的符合要求的连续长度，如果有就在里面搜。要判断有没有，只需要看根节点的fmax是否符合要求即可， void modify(node t[], int l, int r, int x = 1) { //修改某一课树的 if (l <= t[x].l && r >= t[x].r) { pushdown(t[x], 0); return; } pushdown(t, x); int mid = t[x].l + t[x].r >> 1; if (l <= mid) modify(t, l, r, x << 1); if (r > mid) modify(t, l, r, x << 1 | 1); pushup(t, x); } void modify(int l, int r, int c, int x = 1) { //两棵树一起修改的 鸡血状态下会推掉所有邀约，所以要两棵树一起修改成1. 女神邀请时两颗树要一起修改成0，所以要从外部引入值。 if (l <= t1[x].l && r >= t1[x].r) { 两棵树的l，r是一样的，判一棵就行 pushdown(t1[x], c), pushdown(t2[x], c); return; } pushdown(t1, x), pushdown(t2, x); int mid = t1[x].l + t1[x].r >> 1; if (l <= mid) modify(l, r, c, x << 1); if (r > mid) modify(l, r, c, x << 1 | 1); pushup(t1, x), pushup(t2, x); } int main() { int T; cin >> T; rep(Case, T) { printf("Case %d:\n", Case); int n, m; scanf("%d %d", &n, &m); build(1, n); while (m--) { char s[10]; scanf("%s", s); if (*s == 'S') { int l, r; scanf("%d %d", &l, &r); modify(l, r, 1); 赋值1，相当于一个清空的状态。 printf("I am the hope of chinese chengxuyuan!!\n"); } else { int x; scanf("%d", &x); if (*s == 'N') { if (t1[1].fmax >= x) { //基友树有足够的时间 int l = findleft(t1, x); modify(l, l + x - 1, 0); 赋值0，有约状态， printf("%d,don't put my gezi\n", l); } else if (t2[1].fmax >= x){ //女神树有足够的时间 int l = findleft(t2, x); modify(l, l + x - 1, 0); printf("%d,don't put my gezi\n", l); } else printf("wait for me\n"); } else if (*s == 'D') { if (t1[1].fmax >= x) { int l = findleft(t1, x); modify(t1, l, l + x - 1); printf("%d,let's fly\n", l); } else printf("fly with yourself\n"); } } } } return 0; }
经过模仿得到的acwing代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 10; struct node{ int l,r; int fmax,lmax,rmax; int lazy; }t1[N<<2],t2[N<<2]; void pushdown(node &t,int lazy){ t.fmax = lazy * (t.r - t.l + 1); t.lmax = t.rmax = t.fmax; t.lazy = lazy; } void pushdown(node t[],int u){ if(t[u].lazy != -1){ pushdown(t[u<<1],t[u].lazy),pushdown(t[u<<1|1],t[u].lazy); t[u].lazy = -1; } } void pushup(node&p,node&l,node&r){ p.fmax = max(max(l.fmax,r.fmax),l.rmax + r.lmax); p.lmax = l.lmax + (l.lmax == l.r - l.l + 1 ? r.lmax : 0); p.rmax = r.rmax + (r.rmax == r.r - r.l + 1 ? l.rmax : 0); } void pushup(node t[],int u){ pushup(t[u],t[u<<1],t[u<<1|1]); } void build(int u,int l,int r){ t1[u] = t2[u] = {l,r,1,1,1,-1}; if(l == r) return; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(t1,u),pushup(t2,u); } void modify(node tr[],int u,int l,int r){ if(tr[u].l >= l && tr[u].r <= r){ pushdown(tr[u],0); return; } pushdown(tr,u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(tr,u<<1,l,r); if(r > mid) modify(tr,u<<1|1,l,r); pushup(tr,u); } void modify(int u,int l,int r,int v){ if(t1[u].l >= l && t1[u].r <=r ){ pushdown(t1[u],v),pushdown(t2[u],v); return; } pushdown(t1,u),pushdown(t2,u); int mid = t1[u].l + t1[u].r >> 1; if(l <= mid) modify(u<<1,l,r,v); if(r > mid) modify(u<<1|1,l,r,v); pushup(t1,u),pushup(t2,u); } int main(){ int t; cin >> t; for(int Case = 1;Case <= t;Case++){ printf("Case %d:\n",Case); int n,m; scanf("%d%d",&n,&m); build(1,1,n); while(m--){ char s[10]; scanf("%s",s); if(*s == 'S'){ int l,r; scanf("%d%d",&l,&r); modify(1,l,r,1); printf("I am the hope of chinese chengxuyuan!!\n"); } else{ int x; scanf("%d",&x); if(*s == 'N'){ if(t1[1].fmax >= x){ int l = findleft(t1,1,x); modify(1,l,l+x-1,0); printf("%d,don't put my gezi\n", l); } else if(t2[1].fmax >= x){ int l = findleft(t2,1,x); modify(1,l,l+x-1,0); printf("%d,don't put my gezi\n", l); } else printf("wait for me\n"); } else if(*s == 'D'){ if(t1[1].fmax >= x){ int l = findleft(t1,1,x); modify(t1,1,l,l+x-1); printf("%d,let's fly\n", l); } else printf("fly with yourself\n"); } } } } return 0; }
套路
前提条件
给连续区间长度，求满足长度要求的连续区间端点。
######应对：
dfs，fmax，lmax，rmax，搜fmax，rmax+lmax，
int findleft(node tr[],int u,int v){ if(tr[u].l == tr[u].r ) return tr[u].l; pushdown(tr,u); if(tr[u<<1].fmax >= v)return findleft(tr,u<<1,v); 会递到第一个左子节点<v的位置，然后回归到最后一个左子节点<= v的位置，然后往下面的语句走。 if(tr[u<<1].rmax +tr[u<<1|1].lmax >= v) return tr[u<<1].r - tr[u<<1].rmax + 1; 中间的区间不符合要求，说明答案不在左子节点，就往右子节点递归。 return findleft(tr,u<<1|1,v); }
例题4最大连通区间维护，给点找连续区间长度
找连续区间，用递归找，x点在的连续区间，长度大于n的连续区间。 没有优先级，可以先找左子节点，也可以先找右子节点。 和例题3的递归一样，x在左右子节点的合并区间或在叶子节点才返回具体的值。 fmax不能用来确定x的位置，所以没有任何用，此题就没有使用fmax，只使用了 lmax和rmax
套路：
前提条件：给点，找连续区间长度
应对，根据点与mid的值来确定在左右子节点，然后找
左rmax的左端点，
右lmax的右端点
看x在不在。在则返回左rmax+右lmax，
不在则继续搜左子节点（右子节点）
搜到叶子返回节点的lmax或rmax
int query(int u,int x){ if(tr[u].l == tr[u].r) return tr[u].lmax; int mid = tr[u].l + tr[u].r >> 1; if(x <= mid){ if(x>= tr[u<<1].r - tr[u<<1].rmax + 1) return tr[u<<1].rmax + tr[u<<1|1].lmax; return query(u<<1,x); } else{ if(x<= tr[u<<1|1].l + tr[u<<1|1].lmax - 1) return tr[u<<1].rmax + tr[u<<1|1].lmax; return query(u<<1|1,x); } }
题解代码
#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 = 5E4 + 10; struct node { int l, r; int lmax, rmax; //左右最大连续长度 }t[N << 2]; void pushup(node& p, node& l, node& r) { //区间合并 p.lmax = l.lmax + (l.lmax == l.r - l.l + 1 ? r.lmax : 0); p.rmax = r.rmax + (r.rmax == r.r - r.l + 1 ? l.rmax : 0); } void pushup(int x) { pushup(t[x], t[x << 1], t[x << 1 | 1]); } void build(int l, int r, int x = 1) { t[x] = { l, r, 1, 1 }; if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); pushup(x); } void modify(int a, int c, int x = 1) { if (t[x].l == t[x].r) { t[x].lmax = t[x].rmax = c; return; } int mid = t[x].l + t[x].r >> 1; modify(a, c, x << 1 | (a > mid)); pushup(x); } int ask(int a, int x = 1) { if (t[x].l == t[x].r) return t[x].lmax; int mid = t[x].l + t[x].r >> 1; if (a <= mid) { //表明a在左子树, 看看左子树右连续区间是否包含a点 node& op = t[x << 1]; if (a >= op.r - op.rmax + 1) return op.rmax + t[x << 1 | 1].lmax; 询问a是否在从右往左最大连续的区间内， return ask(a, x << 1); //不包含a } else { //表明a在右子树, 看看右子树左连续区间是否包含a点 node& op = t[x << 1 | 1]; if (a <= op.l + op.lmax - 1) return op.lmax + t[x << 1].rmax; 询问a是否在从左往右最大连续内，在则返回左右子节点的合并区间 return ask(a, x << 1 | 1); //不包含a 不在则继续搜 } } int main() { int n, m; while (~scanf("%d %d", &n, &m)) { stack<int> st; //记录最后被删除的点 build(1, n); rep(i, m) { char s[2]; scanf("%s", s); if (s[0] == 'D') { int a; scanf("%d", &a); modify(a, 0); st.push(a); } else if (s[0] == 'Q') { int a; scanf("%d", &a); printf("%d\n", ask(a)); } else modify(st.top(), 1), st.pop(); } } return 0; }
模仿后得到的acwing代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <stack> using namespace std; const int N = 5e4 + 10; struct node{ int l,r; int lmax,rmax; }tr[N<<2]; void pushup(node &tr,node &l,node &r){ 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,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); } int query(int u,int x){ if(tr[u].l == tr[u].r) return tr[u].lmax; int mid = tr[u].l + tr[u].r >> 1; if(x <= mid){ if(x>= tr[u<<1].r - tr[u<<1].rmax + 1) return tr[u<<1].rmax + tr[u<<1|1].lmax; 找到了直接返回值，因为第一次找到肯定是最接近根节点，最大的。 return query(u<<1,x ); 找连续区间，用递归找，x点在的连续区间，长度大于n的连续区间。 没有优先级，可以先找左子节点，也可以先找右子节点。 和例题3的递归一样，x在左右子节点的合并区间或在叶子节点才返回具体的值。 fmax不能用来确定x的位置，所以没有任何用，此题就没有使用fmax，只使用了 lmax和rmax } else{ if(x<= tr[u<<1|1].l + tr[u<<1|1].lmax - 1) return tr[u<<1].rmax + tr[u<<1|1].lmax; return query(u<<1|1,x); } } void modify(int u,int x,int v){ if(tr[u].l == tr[u].r){ tr[u].lmax = tr[u].rmax = v; return; } int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u<<1,x,v); else modify(u<<1|1,x,v); pushup(u); } int main() { int n, m; while (~scanf("%d %d", &n, &m)) { stack<int> st; //记录最后被删除的点 可以连续修复，所以用stack存摧毁的位置，先进后出，栈顶就是最新的一个元素。 build(1,1, n); for(int i= 1;i <= m;i++) { char s[2]; scanf("%s", s); if (s[0] == 'D') { int a; scanf("%d", &a); modify(1,a, 0); st.push(a); } else if (s[0] == 'Q') { int a; scanf("%d", &a); printf("%d\n", query(1,a)); } else modify(1,st.top(), 1), st.pop(); } } return 0; }
