五一普转提Day-2
五一普转提Day-2
上午
1.线段树(分治)
主要用来解决区间存储的问题
每一个节点都对应一个区间
1.有
层,最多
个区间
2.有
个节点
3.计算区间和,自下而上计算,上面一个等于下面的和
4.区间求和把几个区间找出来再加起来就可以了
5.空间要开为
倍
6.建树的代码
#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int maxn=1000010; int n,m,a[maxn]; struct node{ int sum;//区间和 int size;//区间长度 void init(int v){ sum=v; size=1; } }z[maxn<<2];//注意,大小要开4倍大小! node operator+(const node &l,const node &r){ node res; res.sum=l.sum+r.sum; res.size=l.size+r.size; } #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define root 1,n,1 void build(int l,int r,int rt)//建树 编号为rt的线段树节点所对应的区间是l~r { if(l==r){ z[rt].init(a[l]); return; } int m=(l+r)>>1; build(lson); build(rson); z[rt]=z[rt<<1]+z[rt<<1|1];//合并 } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(root); return 0; }
7.懒标记
被整体加了n但没有告诉它的儿子,直到询问它的儿子时才会告诉它们(标记下放)
8.完整代码:
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=100010; int n,m,a[maxn]; struct node{ //一个线段树节点 int sum; //代表区间和 int size; //代表区间长度 int add; //这段区间被整体加了多少 node(){sum = size = add = 0;} void init(int v){ //用一个数初始化 sum = v; size = 1; } }z[maxn<<2]; //z[i]就代表线段树的第i个节点 node operator+(const node &l,const node &r){ node res; res.sum = l.sum + r.sum; res.size = l.size + r.size; return res; } void color(int l,int r,int rt,int v){ //给l,r,rt这个节点打一个+v的懒标记 z[rt].add += v; z[rt].sum += z[rt].size * v; } void push_col(int l,int r,int rt){ //标记下放 把标记告诉儿子 if(z[rt].add == 0) return; //没标记 不需要下放 int m=(l+r)>>1; color(lson,z[rt].add); color(rson,z[rt].add); z[rt].add=0; } void build(int l,int r,int rt){ //建树 初始化l,r,rt这个节点 if(l==r){ z[rt].init(a[l]); return; } int m=(l+r)>>1; build(lson); build(rson); z[rt] = z[rt<<1] + z[rt<<1|1]; } node query(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr) return z[rt]; push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m){ if(m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr); else return query(lson,nowl,nowr); } else return query(rson,nowl,nowr); } void modify(int l,int r,int rt,int nowl,int nowr,int v){ //区间修改 if(nowl<=l && r<=nowr){ color(l,r,rt,v); return; } push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) modify(lson,nowl,nowr,v); if(m<nowr) modify(rson,nowl,nowr,v); z[rt] = z[rt<<1] + z[rt<<1|1]; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(root); cin>>m; for(int i=1;i<=m;i++){ int opt; cin>>opt; if(opt==1){ //询问 int l,r; cin>>l>>r; cout<<query(root,l,r).sum<<"\n"; } else{ //修改 int l,r,v; cin>>l>>r>>v; modify(root,l,r,v); } } return 0; }
9.T1 求区间内相邻两数之差的绝对值的和
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=100010; int n,m,a[maxn]; struct node//一个线段树节点 { int sum;//代表区间相邻两数差的绝对值的和 int lv;//最左边的数是多少 int rv;//最右边的数是多少 int add;//这段区间被整体加了多少 int size;//区间长度 node() { sum = add = 0; } void init(int v)//用一个数初始化 { sum = 0; lv = rv = v; size = 1; } }z[maxn<<2];//z[i]就代表线段树的第i个节点 node operator+(const node &l,const node &r) { node res; res.sum = l.sum + r.sum + abs(l.rv - r.lv); res.lv = l.lv; res.rv = r.rv; res.size = l.size + r.size; return res; } void color(int l,int r,int rt,int v)//给l,r,rt这个节点打一个+v的懒标记 { z[rt].add += v; z[rt].lv += v; z[rt].rv += v; } void push_col(int l,int r,int rt)//标记下放 把标记告诉儿子 { if(z[rt].add == 0) return; //没标记 不需要下放 可以不要这句话 但会慢些 int m=(l+r)>>1; color(lson,z[rt].add); color(rson,z[rt].add); z[rt].add=0; } void build(int l,int r,int rt)//建树 初始化l,r,rt这个节点 //编号为rt的线段树节点 所对应的区间是l~r { if(l==r) { z[rt].init(a[l]); return; } int m=(l+r)>>1; build(lson); build(rson); z[rt] = z[rt<<1] + z[rt<<1|1]; } node query(int l,int r,int rt,int nowl,int nowr) //l,r,rt描述了一个线段树节点 //nowl nowr代表了询问的区间的左端点和右端点 { if(nowl<=l && r<=nowr) return z[rt]; push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) { if(m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr); else return query(lson,nowl,nowr); } else return query(rson,nowl,nowr); } void modify(int l,int r,int rt,int nowl,int nowr,int v) //把nowl~nowr这段区间全部整体+v { if(nowl<=l && r<=nowr)//当前线段树节点被修改区间整体包含 { color(l,r,rt,v);//给l,r,rt这个节点打一个+v的懒标记 return; } push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) modify(lson,nowl,nowr,v); if(m<nowr) modify(rson,nowl,nowr,v); z[rt] = z[rt<<1] + z[rt<<1|1]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(root); cin>>m; for(int i=1;i<=m;i++) { int opt; cin>>opt; if(opt==1)//询问 { int l,r; cin>>l>>r; cout<<query(root,l,r).sum<<"\n"; } else { int l,r,v; cin>>l>>r>>v; modify(root,l,r,v); } } return 0; }
10.T2 求区间内各数的平方和
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=100010; int n,m,a[maxn]; struct node//一个线段树节点 { int sum;//代表区间和 int sum2;//代表区间平方和 int size;//代表区间长度 int add;//这段区间被整体加了多少 node() { sum = size = add = 0; } void init(int v)//用一个数初始化 { sum = v; sum2 = v*v; size = 1; } }z[maxn<<2];//z[i]就代表线段树的第i个节点 node operator+(const node &l,const node &r) { node res; res.sum2 = l.sum2 + r.sum2; res.sum = l.sum + r.sum; res.size = l.size + r.size; return res; } void color(int l,int r,int rt,int v)//给l,r,rt这个节点打一个+v的懒标记 { z[rt].add += v; z[rt].sum2 = z[rt].sum2 + 2*v*z[rt].sum + z[rt].size*v*v; z[rt].sum += z[rt].size*v; } void push_col(int l,int r,int rt)//标记下放 把标记告诉儿子 { if(z[rt].add == 0) return; //没标记 不需要下放 可以不要这句话 但会慢些 int m=(l+r)>>1; color(lson,z[rt].add); color(rson,z[rt].add); z[rt].add=0; } void build(int l,int r,int rt)//建树 初始化l,r,rt这个节点 { if(l==r) { z[rt].init(a[l]); return; } int m=(l+r)>>1; build(lson); build(rson); z[rt] = z[rt<<1] + z[rt<<1|1]; } node query(int l,int r,int rt,int nowl,int nowr) { if(nowl<=l && r<=nowr) return z[rt]; push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) { if(m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr); else return query(lson,nowl,nowr); } else return query(rson,nowl,nowr); } void modify(int l,int r,int rt,int nowl,int nowr,int v) { if(nowl<=l && r<=nowr) { color(l,r,rt,v); return; } push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) modify(lson,nowl,nowr,v); if(m<nowr) modify(rson,nowl,nowr,v); z[rt] = z[rt<<1] + z[rt<<1|1]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(root); cin>>m; for(int i=1;i<=m;i++) { int opt; cin>>opt; if(opt==1) { int l,r; cin>>l>>r; cout<<query(root,l,r).sum<<"\n"; } else { int l,r,v; cin>>l>>r>>v; modify(root,l,r,v); } } return 0; }
11.线段树2
种操作:
种标记,顺序用好用的那一种
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=100010; int n,m,a[maxn]; struct node//一个线段树节点 { int sum;//代表区间和 int size;//代表区间长度 int add; int mul; //x*mul+add node() { sum = size = add = 0; mul = 1; } void init(int v)//用一个数初始化 { sum = v; size = 1; } }z[maxn<<2];//z[i]就代表线段树的第i个节点 node operator+(const node &l,const node &r) { node res; res.sum = l.sum + r.sum; res.size = l.size + r.size; return res; } void color(int l,int r,int rt,int mul,int add)//给l,r,rt这个节点打一个*mul+add的懒标记 { z[rt].mul *= mul; z[rt].add = z[rt].add * mul + add; z[rt].sum = z[rt].sum * mul + add * z[rt].size; } void push_col(int l,int r,int rt)//标记下放 把标记告诉儿子 { if(z[rt].mul == 1 && z[rt].add == 0) return; //没标记 不需要下放 int m=(l+r)>>1; color(lson,z[rt].mul,z[rt].add); color(rson,z[rt].mul,z[rt].add); z[rt].mul=1;z[rt].add=0; } void build(int l,int r,int rt)//建树 初始化l,r,rt这个节点 { if(l==r) { z[rt].init(a[l]); return; } int m=(l+r)>>1; build(lson); build(rson); z[rt] = z[rt<<1] + z[rt<<1|1]; } node query(int l,int r,int rt,int nowl,int nowr) { if(nowl<=l && r<=nowr) return z[rt]; push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) { if(m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr); else return query(lson,nowl,nowr); } else return query(rson,nowl,nowr); } void modify(int l,int r,int rt,int nowl,int nowr,int mul,int add) { if(nowl<=l && r<=nowr) { color(l,r,rt,mul,add); return; } push_col(l,r,rt); int m=(l+r)>>1; if(nowl<=m) modify(lson,nowl,nowr,mul,add); if(m<nowr) modify(rson,nowl,nowr,mul,add); z[rt] = z[rt<<1] + z[rt<<1|1]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(root); cin>>m; for(int i=1;i<=m;i++) { int opt; cin>>opt; if(opt==1)//询问 { int l,r; cin>>l>>r; cout<<query(root,l,r).sum<<"\n"; } else//修改 { int l,r,mul,add; cin>>l>>r>>mul>>add; modify(root,l,r,mul,add); } } return 0; }
12.线段树2.5
种操作:
种标记,顺序用好用的那一种
13.更麻烦的东西
14.减小时间.
%
)%
%
%
%
%
%
%
%20a-%3Dc&preview=true)
%
%
%
15.求l~r之间和最大的一个子段
我就不写代码了(手有点懒了)
16.SP2916
17.SP2713
18.5824
19.3954
20.区间等差数列
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=100010; int n,m,a[maxn]; struct node//一个线段树节点 { int sum;//代表区间和 int size;//代表区间长度 int x,y;//给这段区间加上了一个首项为x 公差为y的等差数列 node() { sum = size = x = y = 0; } void init(int v)//用一个数初始化 { sum = v; size = 1; } }z[maxn<<2];//z[i]就代表线段树的第i个节点 node operator+(const node &l,const node &r) { node res; res.sum = l.sum + r.sum; res.size = l.size + r.size; return res; } void color(int l,int r,int rt,int x, int y)//给l,r,rt这个节点加上一个首项为x公差为y的等差数列 { z[rt].x+=x; z[rt].y+=y; z[rt].sum+=(x+x+(size-1)*y)*size/2; } void push_col(int l,int r,int rt)//标记下放 把标记告诉儿子 { if (z[rt].x == 0 && z[rt].y == 0) return; //没标记 不需要下放 可以不要这句话 但会慢些 int m=(l+r)>>1; color(lson,z[rt].x,z[rt].y); color(rson,z[rt].x + z[rt<<1].size * y,z[rt].y); z[rt].x=z[rt].y=0; } void build(int l,int r,int rt)//建树 初始化l,r,rt这个节点 //编号为rt的线段树节点 所对应的区间是l~r { if (l==r) { z[rt].init(a[l]); return; } int m=(l+r) >> 1; build(lson); build(rson); z[rt] = z[rt<<1] + z[rt<<1|1]; } node query(int l,int r,int rt,int nowl,int nowr) //l,r,rt描述了一个线段树节点 //nowl nowr代表了询问的区间的左端点和右端点 { if (nowl <= l && r <= nowr) return z[rt]; push_col(l,r,rt); int m=(l+r)>>1; if (nowl<=m) { if (m<nowr) return query(lson,nowl,nowr) + query(rson,nowl,nowr); else return query(lson,nowl,nowr); } else return query(rson,nowl,nowr); } void modify(int l,int r,int rt,int nowl,int nowr,int v) //把nowl~nowr这段区间全部整体+v { if (nowl<=l && r<=nowr)//当前线段树节点被修改区间整体包含 { color(l,r,rt,v);//给l,r,rt这个节点打一个+v的懒标记 return; } push_col(l,r,rt); int m=(l+r)>>1; if (nowl<=m) modify(lson,nowl,nowr,v); if (m<nowr) modify(rson,nowl,nowr,v); z[rt] = z[rt<<1] + z[rt<<1|1]; } int main() { cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; build(root); cin >> m; for (int i=1;i<=m;i++) { int opt; cin >> opt; if (opt==1)//询问 { int l,r; cin >> l >> r; cout << query(root,l,r).sum << "\n"; } else { int l,r,v; cin >> l >> r >> v; modify(root,l,r,v); } } return 0; }
下午
21.求区间最多逆序对P3333
2.可持久化线段树
1.可以通过连接与前一时刻相同的部分,更改不同的部分,形成一棵完整的线段树。(每一个线段树只需要
的时间新建一棵线段树) )
2.可持久化线段树模板代码
#include<bits/stdc++.h> using namespace std; int cnt;//总共有多少个节点 struct node { int l,r;//左儿子 右儿子编号 int sum;//区间和 node(){ l=r=sum=0; } }z[maxn*logn]; void update(int p) { z[p].sum = z[z[p].l].sum + z[z[p].r].sum; } int build(int l,int r)//当前的区间为l~r 是这段区间对应的节点编号 { cnt++; int p=cnt; if (l==r) { z[p].sum = a[l]; return p; } int m=(l+r)>>1; z[p].l = build(l,m); z[p].r = build(m+1,r); update(p); return p; } int query(int l,int r,int rt,int nowl,int nowr) //当前线段树节点编号为rt 对应的区间为l~r 要询问nowl~nowr这段区间的和 { if (nowl <= l && r <= nowr) return z[rt].sum; int m=(l+r)>>1; if (nowl<=m) { if (m<nowr) return query(l,m,z[rt].l,nowl,nowr) + query(m+1,r,z[rt].r,nowl,nowr); else return query(l,m,z[rt].l,nowl,nowr); } else return query(m+1,r,z[rt].r,nowl,nowr); } int modify(int l,int r,int rt,int p,int v)//返回修改后的新节点编号 //当前线段树节点编号为rt 对应的区间为l~r 要把a[p]+=v { cnt++;int q = cnt;//新的节点q用于修改 z[q] = z[rt]; if (l==r) { z[q].sum += v; return q; } int m=(l+r)>>1; if (p<=m)//在左儿子 z[q].l = modify(l,m,z[q].l,p,v); else z[q].r = modify(m+1,r,z[q].r,p,v); update(q); return q; } int main() { cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; cin >> m; root[0] = build(1,n);//root[i]代表第i次操作后的根节点是谁 for (int i=1;i<=m;i++) { int opt; cin >> opt; if (opt==1) { int p,v; cin >> p >> v; root[i] = modify(1,n,root[i-1],p,v); } else { int k,l,r; cin >> k >> l >> r; cout << query(1,n,root[k],l,r) << "\n"; root[i] = root[i-1]; } } return 0; }
3.5818
4.主席树
模板代码:
#include<bits/stdc++.h> using namespace std; int cnt;//总共有多少个节点 struct node { int l,r;//左儿子 右儿子编号 int sum;//区间和 node(){ l=r=sum=0; } }z[maxn*logn]; void update(int p) { z[p].sum = z[z[p].l].sum + z[z[p].r].sum; } int query(int l,int r,int rt,int nowl,int nowr) //当前线段树节点编号为rt 对应的区间为l~r 要询问nowl~nowr这段区间的和 { if (nowl <= l && r <= nowr) return z[rt].sum; int m=(l+r)>>1; if (nowl<=m) { if (m<nowr) return query(l,m,z[rt].l,nowl,nowr) + query(m+1,r,z[rt].r,nowl,nowr); else return query(l,m,z[rt].l,nowl,nowr); } else return query(m+1,r,z[rt].r,nowl,nowr); } int modify(int l,int r,int rt,int p,int v)//返回修改后的新节点编号 //当前线段树节点编号为rt 对应的区间为l~r 要把a[p]+=v { cnt++;int q = cnt;//新的节点q用于修改 z[q] = z[rt]; if (l==r) { z[q].sum += v; return q; } int m=(l+r)>>1; if (p<=m)//在左儿子 z[q].l = modify(l,m,z[q].l,p,v); else z[q].r = modify(m+1,r,z[q].r,p,v); update(q); return q; } int query(int p1,int p2,int l,int r,int k) //当前对应的值域范围为l~r //要询问第k小的数 //需要用p1和p2这两颗线段树来询问 { if (l==r) return l; int m=(l+r)>>1; if (z[z[p2].l].sum - z[z[p1].l].sum >= k) return query(z[p1].l,z[p2].l,l,m,k); //z[z[p2].l].sum - z[z[p1].l].sum代表aL~aR有多少个数在[l,m]之间 else return query(z[p1].r,z[p2].r,m+1,r,k-(z[z[p2].l].sum - z[z[p1].l].sum)); } int main() { cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; root[0] = 0; //root[i] 代表a1~ai这些数所对应的值域线段树的根 //值域范围是1~maxv for (int i=1;i<=n;i++) root[i] = modify(1,maxv,root[i-1],a[i],1); cin >> m; for (int i=1;i<=m;i++) { int l,r,k; cin >> l >> r >> k; cout << query(root[l-1],root[r],1,maxv,k) << "\n"; } return 0; }