NFLSHC集训Day5
Joyce_Official
·
·
算法·理论
安排
早八上课下午答疑，中午睡一觉结束，但是我今天忘记戴手表了
今日大纲
线段树进阶
知识点
从点修到区间修改就是质的飞跃，如果要求修改区间
懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。
看完懒惰标记的解释，我们来背背模板：
区间修改（加上一个值）：
```cpp
void upd(int l, int r, int c, int s, int t, int p)
{
// 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
if (l <= s && t <= r)
{
d[p] += (t - s + 1) * c, b[p] += c;
return;
}
int m = s + ((t - s) >> 1);
if (b[p] && s != t)
{
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
```
区间查询（区间和）：
```cpp
int getans(int l, int r, int s, int t, int p)
{
// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
if (l <= s && t <= r) return d[p];
// 当前区间为询问区间的子集时直接返回当前区间的和
int m = s + ((t - s) >> 1);
if (b[p])
{
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
int sum = 0;
if (l <= m) sum = getans(l, r, s, m, p * 2);
if (r > m) sum += getans(l, r, m + 1, t, p * 2 + 1);
return sum;
}
```
**线段树区间修改的应用**
[P1](https://www.luogu.com.cn/problem/P3372)
区间加数和区间和的板子全放在上面了，看看我写的：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
int sum[N * 4], delta[N * 4], a[N];
void pushup(int p)
{
sum[p] = sum[p * 2] + sum[p * 2 + 1];
}
void pushdown(int p , int l, int r)
{
if(l == r || !delta[p]) return ;
int mid = (l + r) / 2;
sum[p * 2] += delta[p] * (mid - l + 1);
sum[p * 2 + 1] += delta[p] * (r - mid);
delta[p * 2] += delta[p];
delta[p * 2 + 1] += delta[p];
delta[p] = 0;
}
void build(int p, int l, int r)
{
delta[p] = 0;
if(l == r)
{
sum[p] = a[l];
return ;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
pushup(p);
}
void upd(int p, int l, int r, int x, int y, int val)
{
pushdown(p, l , r);
if(x == l && r == y)
{
sum[p] += val * (r - l + 1);
delta[p] += val;
return ;
}
int mid = (l + r) / 2;
if(y <= mid) upd(p * 2, l, mid, x, y, val);
else if(x > mid) upd(p * 2 + 1, mid + 1, r, x, y, val);
else
{
upd(p * 2, l, mid, x, mid, val);
upd(p * 2 + 1, mid + 1, r, mid + 1, y, val);
}
pushup(p);
}
int qry(int p, int l, int r, int x, int y)
{
pushdown(p, l, r);
if(l == x && y == r) return sum[p];
int mid = (l + r) / 2;
if(y <= mid) return qry(p * 2, l, mid, x, y);
if(x > mid) return qry(p * 2 + 1, mid + 1, r, x, y);
return qry(p * 2, l, mid, x, mid) + qry(p * 2 + 1, mid + 1, r, mid + 1, y);
}
signed main()
{
int n, m, op, x, y, k;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
build(1, 1, n);
while(m--)
{
cin >> op;
if(op == 1)
{
cin >> x >> y >> k;
upd(1, 1, n, x, y, k);
}
else
{
cin >> x >> y;
cout << qry(1, 1, n, x, y) <<endl;
}
}
return 0;
}
```
[P2](https://www.luogu.com.cn/problem/P3373)
多了一个乘的应用，改一下就行，没啥含金量，看看我写的：
```cpp
#include<bits/stdc++.h>
#define N 101000
#define ll long long
using namespace std;
ll sum[N<<2],delt1[N<<2],delt2[N<<2],a[N],mod;
void pushdown(int p,int l,int r)
{
if (l==r || (delt1[p]==1 && delt2[p]==0)) return;
int mid=l+r>>1;
ll d1=delt1[p],d2=delt2[p];
sum[p<<1]=(sum[p<<1]*d1%mod+d2*(mid-l+1)%mod)%mod;
sum[p<<1|1]=(sum[p<<1|1]*d1%mod+d2*(r-mid)%mod)%mod;
delt1[p<<1]=delt1[p<<1]*d1%mod;
delt1[p<<1|1]=delt1[p<<1|1]*d1%mod;
delt2[p<<1]=(delt2[p<<1]*d1+d2)%mod;
delt2[p<<1|1]=(delt2[p<<1|1]*d1+d2)%mod;
delt1[p]=1;
delt2[p]=0;
}
void pushup(int p)
{
sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;
}
void build(int p,int l,int r)
{
delt1[p]=1;delt2[p]=0;
if (l==r)
{
sum[p]=a[l]%mod;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,int x,int y,ll x1,ll x2)
{
pushdown(p,l,r);
if (l==x && y==r)
{
//区间内的每个数*x1+x2
sum[p]=(sum[p]*x1%mod+x2*(r-l+1)%mod)%mod;
delt1[p]=x1%mod;delt2[p]=x2%mod;
return;
}
int mid=l+r>>1;
if (y<=mid) update(p<<1,l,mid,x,y,x1,x2);
else if (x>mid) update(p<<1|1,mid+1,r,x,y,x1,x2);
else
{
update(p<<1,l,mid,x,mid,x1,x2);
update(p<<1|1,mid+1,r,mid+1,y,x1,x2);
}
pushup(p);
}
int query(int p,int l,int r,int x,int y)
{
pushdown(p,l,r);
if (l==x && y==r) return sum[p];
int mid=l+r>>1;
if (y<=mid) return query(p<<1,l,mid,x,y);
if (x>mid) return query(p<<1|1,mid+1,r,x,y);
return (query(p<<1,l,mid,x,mid) + query(p<<1|1,mid+1,r,mid+1,y))%mod;
}
int main()
{
int n,m,op,x,y;
ll k;
cin>>n>>m>>mod;
for (int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while (m--)
{
cin>>op>>x>>y;
if (op==1)
{
cin>>k;
update(1,1,n,x,y,k,0);
}
else if (op==2)
{
cin>>k;
update(1,1,n,x,y,1,k);
}
else cout<<query(1,1,n,x,y)<<endl;
}
return 0;
}
```
[P3](https://www.luogu.com.cn/problem/P3870)
然鹅也没啥区别，开的灯关了，关的灯开了，灯的总数不变，只是把这两者数量交换下
例如： 1 0 1 0 1 1
开着的灯的数量：4
关着的灯的数量：2
（不太华丽的分割线）
操作一次后： 0 1 0 1 0 0
开着的灯的数量：2
关着的灯的数量：4
就这我为了一个 $pushdown$ 就调了40分钟，无语死，看看我写的：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1000030;
struct node
{
int l, r;
int l0, l1, add;
} t[N * 4];
int n, m, op, a, b;
void build(int p, int l, int r)
{
t[p].l = l;
t[p].r = r;
if (l == r)
{
t[p].l0++;
return ;
}
int mid = (l + r) / 2;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
t[p].l0 = t[p << 1].l0 + t[p << 1 | 1].l0;
}
void sp(int p)
{
if(t[p].add == 0) return ;
swap(t[p << 1].l0, t[p << 1].l1);
swap(t[p << 1 | 1].l0, t[p << 1 | 1].l1);
t[p << 1].add ^= 1;
t[p << 1 | 1].add ^= 1;
t[p].add = 0;
}
void ch(int p, int l, int r)
{
if(t[p].l >= l && t[p].r <= r)
{
t[p].add ^= 1;
swap(t[p].l0, t[p].l1);
return ;
}
sp(p);
int mid = (t[p].l + t[p].r) / 2;
if (l <= mid) ch(p * 2, l, r);
if (mid < r) ch(p * 2 + 1, l, r);
t[p].l0 = t[p * 2].l0 + t[p * 2 + 1].l0;
t[p].l1 = t[p * 2].l1 + t[p * 2 + 1].l1;
}
int getans(int p, int l, int r)
{
if (t[p].l >= l && t[p].r <= r) return t[p].l1;
sp(p);
int mid = (t[p].l + t[p].r) / 2, sum = 0;
if (l <= mid) sum += getans(p * 2, l, r);
if (mid < r) sum += getans(p * 2 + 1, l, r);
return sum;
}
int main()
{
cin >> n >> m;
build(1, 1, n);
while(m--)
{
cin >> op >> a >> b;
if(op == 0)
{
ch(1, a, b);
}
else
{
cout << getans(1, a, b) <<endl;
}
}
return 0;
}
```