「bzoj4105」「THUSC2015」平方运算 - 线段树+强行 | Bill Yang's Blog

「bzoj4105」「THUSC2015」平方运算 - 线段树+强行

题目大意



题目分析

这道题很无聊,出题人强行构造数据使得自己能过。

一眼就是有结论的线段树题,估计和区间取模类似。
首先我们发现只有操作$\bmod P$,并不要求对询问取模,这说明平方取模有一定性质。
再观察题目的数据范围,发现给定了每一个$P$,奥妙重重。

经过打表,发现在题目限制的模数中,对每个数平方取模最多经过$62$次就会产生循环。
因此我们想到,这道题是根据循环的方式来搞。
但是父节点如何合并子结点的循环呢?对子结点的循环长度取$lcm$即为父节点循环长度,暴力计算父节点循环。但$lcm$非常大啊,岂不是超时了。

每一个循环都长这个样子:

借用$rho$算法和带花树的名词,我们将循环称为$\rho$环,将圈称为花,将$\rho$环除去花部分称为花茎。

通过再一次打表发现:
对于$P=9977$时,花大小最大,$lcm$也最大,花大小与$lcm$均为$60$,花茎长度最大$=2$。
对于所有点,花茎最大长度不超过$5$。

这。。。也太巧了吧。
因此父节点就可以合并儿子结点的循环了。

每次修改定位到一个被完全包含且在花上的区间时,直接移动其在花上的指针,并打上懒标记,意味着儿子结点(必在花上)均需要移动指针。
若定位到一个区间不在花上,继续向下递归。

每次标记上传时需要重新计算父亲的$\rho$环,因为儿子中的一个改变了,而另外一个没变,会使得环发生变化。

时间复杂度$O((5n+q\log n)\cdot60)$。


代码

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
131
132
133
134
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
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=100005,maxp=10005;
int a[maxn],Next[maxp];
bool inCircle[maxn];
struct Segment_Tree {
struct Tree {
int left,right,sum,lazy;
bool inCircle;
int pos,len,circle[65];
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index].left=Left,tree[index].right=Right;
if(Left==Right) {
tree[index].sum=a[Left];
build_circle(index,a[Left]);
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void build_circle(int index,int val) {
tree[index].inCircle=inCircle[val];
if(tree[index].inCircle) {
tree[index].pos=0;for(int now=val; !tree[index].len||now!=val; now=Next[now])tree[index].circle[tree[index].len++]=now;
}
}
void push_up(int index) {
tree[index].sum=tree[ls].sum+tree[rs].sum;
tree[index].inCircle=tree[ls].inCircle&&tree[rs].inCircle;
if(tree[index].inCircle) {
tree[index].len=tree[ls].len/__gcd(tree[ls].len,tree[rs].len)*tree[rs].len;
tree[index].pos=0;
int lpos=tree[ls].pos,rpos=tree[rs].pos;
for(int i=0; i<tree[index].len; i++) {
tree[index].circle[i]=tree[ls].circle[lpos++]+tree[rs].circle[rpos++];
if(lpos==tree[ls].len)lpos=0;
if(rpos==tree[rs].len)rpos=0;
}
}
}
void push_down(int index) {
if(!tree[index].lazy)return;
tree[ls].lazy+=tree[index].lazy,tree[rs].lazy+=tree[index].lazy;
tree[ls].pos=(tree[ls].pos+tree[index].lazy)%tree[ls].len,tree[rs].pos=(tree[rs].pos+tree[index].lazy)%tree[rs].len;
tree[ls].sum=tree[ls].circle[tree[ls].pos],tree[rs].sum=tree[rs].circle[tree[rs].pos];
tree[index].lazy=0;
}
void modify(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right&&tree[index].inCircle) {
tree[index].lazy++;
tree[index].pos++;
if(tree[index].pos==tree[index].len)tree[index].pos=0;
tree[index].sum=tree[index].circle[tree[index].pos];
return;
}
if(tree[index].left==tree[index].right) { //叶子结点
tree[index].sum=Next[tree[index].sum];
build_circle(index,tree[index].sum);
return;
}
push_down(index);
modify(ls,Left,Right);
modify(rs,Left,Right);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].sum;
push_down(index);
return query(ls,Left,Right)+query(rs,Left,Right);
}
} st;
int n,m,p;
bool vst[maxp];
int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
for(int i=0; i<p; i++) {
Next[i]=i*i%p;
inCircle[i]=1;
}
for(int i=0; i<p; i++)
if(!vst[i]) {
int now=i;
while(!vst[now]) {
vst[now]=1;
now=Next[now];
}
for(int j=i; j!=now; j=Next[j])inCircle[j]=0;
}
for(int i=1; i<=n; i++)a[i]=Get_Int();
st.build(1,1,n);
for(int i=1; i<=m; i++) {
int opt=Get_Int(),l=Get_Int(),r=Get_Int();
if(opt==0)st.modify(1,l,r);
else printf("%d\n",st.query(1,l,r));
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%