区间修改部分

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的数量设置为11代表花瓶是空的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){
没什么区别，传统批量等值修改的modifyif(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){
没什么区别，传统批量等值修改的queryif(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递归做法，还不太懂。

还涉及到一个染色优先度的问题，

前提条件

分色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或0op.lmax = op.fmax, op.rmax = op.fmax;经过fmax被赋值后，fmax变成了区间长度乘lazy状态，可以直接赋给lmax和fmaxop.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;符合条件就returnpushdown(t, x);if (t[x << 1].fmax >= c) return findleft(t, c, x << 1);dfs，把1的深度搜完，转战2if (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);
}
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);
}
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;
}

基本形式：

加法操作：
void pushdown(int u,int lazy){
tr[u].sum += lazy * (tr[u].r - tr[u].l + 1);
tr[u].lazy += lazy;
}
减法操作：
void pushdown(int u,int lazy){
tr[u].sum -= lazy * (tr[u].r - tr[u].l + 1);
tr[u].lazy -= lazy;
}
替换操作：
void pushdown(int u,int lazy){
tr[u].sum = lazy * (tr[u].r - tr[u].l + 1);
tr[u].lazy = lazy;
}
通过在modify中调用pushdown来进行值的修改。
在替换操作里，lazy作为一个储存状态的标记储存0，1，-1的话，可以实现动态区间修改01串，区间查询01串中的0，1个数
01串情景一般是：有真或假两种状态，有花与没花，开灯与关灯，还有单纯的两种字符，a与b

2.批量自适应修改

前提条件

是区间修改，区间查询，且修改操作的修改的值是根据具体节点储存的值而变化的，比如开根，幂，替换，乘除；
新做的题里发现替换可以直接批量赋值来实现，属于等值修改。

情景

对一个序列里的元素执行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].l >= l && tr[u].r <= r && 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){
只有叶子节点才能初始化成lazy1if(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)三种形式

区别

区间等值修改里，
lazy存的是子树中所有节点要修改的值或要修改成的值，根据题意决定初始化的值，如例题1中批量+v操作，初始化为0，例题2批量替换，初始化为v的定义域之外的值。
sum存的是子树所有节点sum的总和 ，一般初始化为0.
是一个修改时给节点打上lazy，遇到lazy时解开lazy的过程。

区间自适应修改里，
lazy作为一个bool变量，存的是当前节点是否能代表子树接受修改，根据题意决定初始化的值
sum只有在lazy为1时有实际意义，
存的是这颗所有节点的值都相同的子树里的这个相同的值
修改值时，直接修改节点的值