隐藏
「bsoj3794」线段 - 线段树+双标记 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj3794」线段 - 线段树+双标记

题目大意

数轴上有很多单位线段,一开始时所有单位线段的权值都是1。有两种操作,第一种操作将某一区间内的单位线段权值乘以w,第二种操作将某一区间内的单位线段权值取w次幂。并且你还需要回答一些询问,每个询问需要求出某一区间的单位线段权值之积。由于答案可能很大,你只需要求出答案 mod (10^9+7)的值。


题目分析

显然我们可以用线段树维护信息。
线段树用双标记分别表示尚未下传的幂次与尚未下传的乘数。
然而区间范围极大,因此需要对区间离散化。
温馨提示:此题极为难调,本人调了一上午,建议冷静地分析


具体步骤

将区间端点提取出来进行离散化,排序后计算相邻两个点的距离(即为单位线段的个数)。
将原来的区间的点映射为离散化后的区间,因此每个询问的右区间需要-1。

维护属性

建立线段树,维护以下属性:

  • $left/right$
  • $mul$:当前区间的权值之积
  • $size$:当前区间包含的单位线段个数
  • $mullazy$:当前区间尚未下传的乘数
  • $powlazy$:当前区间尚未下传的幂次

以下markdown出了点问题,用图片代替。

修改处理

标记合并

标记下传

更新子区间的标记:

更新子区间权值:

清除标记:

取模运算

因为题目要求的模数为质数,故根据费马小定理,我们可以对$powlazy\bmod(mod-1)$

对于其余的$\bmod\,mod$即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005*2;
const LL mod=1000000007;
struct Tree {
int left,right;
LL mul,size;
LL mullazy,powlazy;
Tree(LL l=0,LL r=0,LL s=0):left(l),right(r),size(s),mul(1),mullazy(1),powlazy(1) {}
};
LL Quick_Pow(LL a,LL b) {
LL ans=1;
while(b>0) {
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,LL* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index]=Tree(Left,Right,a[Left]);
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
push_up(index);
}
void push_down(int index) {
tree[ls].powlazy=tree[ls].powlazy*tree[index].powlazy%(mod-1);
tree[rs].powlazy=tree[rs].powlazy*tree[index].powlazy%(mod-1);
tree[ls].mullazy=(Quick_Pow(tree[ls].mullazy,tree[index].powlazy)*tree[index].mullazy)%mod;
tree[rs].mullazy=(Quick_Pow(tree[rs].mullazy,tree[index].powlazy)*tree[index].mullazy)%mod;
tree[ls].mul=Quick_Pow(tree[ls].mul,tree[index].powlazy)*Quick_Pow(tree[index].mullazy,tree[ls].size)%mod;
tree[rs].mul=Quick_Pow(tree[rs].mul,tree[index].powlazy)*Quick_Pow(tree[index].mullazy,tree[rs].size)%mod;
tree[index].powlazy=tree[index].mullazy=1;
}
void push_up(int index) {
tree[index].mul=tree[ls].mul*tree[rs].mul%mod;
tree[index].size=tree[ls].size+tree[rs].size;
}
void modify(int index,int Left,int Right,LL v) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
tree[index].mul=tree[index].mul*Quick_Pow(v,tree[index].size)%mod;
tree[index].mullazy=tree[index].mullazy*v%mod;
return;
}
push_down(index);
modify(ls,Left,Right,v);
modify(rs,Left,Right,v);
push_up(index);
}
void modify2(int index,int Left,int Right,LL v) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
tree[index].mul=Quick_Pow(tree[index].mul,v);
tree[index].mullazy=Quick_Pow(tree[index].mullazy,v);
tree[index].powlazy=tree[index].powlazy*v%(mod-1);
return;
}
push_down(index);
modify2(ls,Left,Right,v);
modify2(rs,Left,Right,v);
push_up(index);
}
LL query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return 1;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].mul;
push_down(index);
return query(ls,Left,Right)*query(rs,Left,Right)%mod;
}
} st;
struct Query {
int opt,x,y,v;
} q[maxn];
LL n,a[maxn],v[maxn],cnt=0;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
q[i].opt=Get_Int();
if(q[i].opt!=2) {
a[++cnt]=q[i].x=Get_Int();
a[++cnt]=q[i].y=Get_Int();
q[i].v=Get_Int();
} else a[++cnt]=q[i].x=Get_Int(),a[++cnt]=q[i].y=Get_Int();
}
sort(a+1,a+cnt+1);
int tot=unique(a+1,a+cnt+1)-a-1;
for(int i=1; i<=n; i++) {
q[i].x=lower_bound(a+1,a+tot+1,q[i].x)-a;
q[i].y=lower_bound(a+1,a+tot+1,q[i].y)-a;
}
for(int i=1; i<tot; i++)v[i]=a[i+1]-a[i];
st.build(1,1,tot-1,v);
for(int i=1; i<=n; i++) {
if(q[i].opt==0)st.modify(1,q[i].x,q[i].y-1,q[i].v);
else if(q[i].opt==1)st.modify2(1,q[i].x,q[i].y-1,q[i].v);
else printf("%lld\n",st.query(1,q[i].x,q[i].y-1));
}
return 0;
}
姥爷们赏瓶冰阔落吧~