BZOJ

BZOJ 4105

不稳定的传送门

Description

现有一个长度为$N$的序列$ \lbrace X_1,X_2,…,X_N\rbrace $，要求支持两种操作：
$1.\ 0\ l\ r$ 表示将$\forall i\in [l,r],X_i = X_i^2\ {\rm mod}\ p$
$2.\ 1\ l\ r$ 询问$\sum_{l\leq i\leq r}X_i$

Input

第一行有三个整数$N，M，p$，分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。
接下来一行$N$个数代表一开始的序列$\lbrace X_1,X_2,…,X_N\rbrace $。
接下来$M$行，每行三个整数$op,l,r$。其中$op$代表本次操作的类型。若$op=0$，代表这是一次平方操作，平方的区间为$[l,r]$；如果$op=1$，代表这是一次询问操作，询问的区间为$[l,r]$。

Output

对于每次的询问操作，输出一行代表这段区间内数的总和。注意：答案没有对任何数取模。

Sample Input

1
2
3
4
5
3 3 11
1 2 3
1 1 3
0 1 3
1 1 3

Sample Output

1
2
6
14

Hint

对于$100\%$的数据，保证$\forall i, X_i\in[0, P)$, $l, r\in[1, n]$

测试点 N M P
1 $\leq 1000$ $\leq 1000$ $=233$
2 $\leq 1000$ $\leq 1000$ $=2332$
3 $\leq 100000$ $\leq 100000$ $=5$
4 $\leq 100000$ $\leq 100000$ $=8192$
5 $\leq 100000$ $\leq 100000$ $=23$
6 $\leq 100000$ $\leq 100000$ $=45$
7 $\leq 100000$ $\leq 100000$ $=37$
8 $\leq 55000$ $\leq 55000$ $=4185$
9 $\leq 55000$ $\leq 55000$ $=5850$
10 $\leq 55000$ $\leq 55000$ $=2975$
11 $\leq 55000$ $\leq 55000$ $=2542$
12 $\leq 55000$ $\leq 55000$ $=2015$
13 $\leq 60000$ $\leq 60000$ $=2003$
14 $\leq 65000$ $\leq 65000$ $=2010$
15 $\leq 70000$ $\leq 70000$ $=4593$
16 $\leq 75000$ $\leq 75000$ $=4562$
17 $\leq 80000$ $\leq 80000$ $=1034$
18 $\leq 85000$ $\leq 85000$ $=5831$
19 $\leq 90000$ $\leq 90000$ $=9905$
20 $\leq 100000$ $\leq 100000$ $=9977$

在模意义下，任何数字一直平方都会进入$\rho$或$O$型循环

打表可以发现这些模数的所有循环节长度的${\rm LCM}$都是$\leq 60$的（本来想贴上每个的长度的…发现打表的程序删了T T）

那么线段树中每个节点维护一个环，修改时转一下就行了

注意$\rho$型循环中还没真正进入循环（也就是还在柄上）的情况，还没进循环时先不存，等转进循环时再算

先处理出$[0,p-1]$中真正在循环中的数，然后建树，线段树合并时长度取左右儿子长度的${\rm LCM}$，环上每个点的数值取左右儿子这一位的和

别的操作自行YY即可

顺便贴一发题解…


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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
program bzoj_4105;
type circ=record nxt,k:longint; end;
var s:array[0..200000]of record l,r,len,sum,lc,rc,mk,cir:longint; end;
    n,m,mo,i,op,l,r,tot,rt,cir:longint;
    v:array[0..10000]of longint;
    incir:array[0..10000]of boolean;
    x:array[1..100000]of longint;
    c:array[1..12000000]of circ;

function gcd(a,b:longint):longint;
begin
  if b=0 then exit(a) else exit(gcd(b,a mod b));
end;

procedure find_cir(x:longint);
var t:longint;
begin
  if v[x]<>0 then
  begin
    if v[x]=tot then
    begin
      t:=x;
      repeat
        incir[t]:=true;
        t:=t*t mod mo;
      until t=x;
    end;
    exit;
  end;
  v[x]:=tot;
  find_cir(x*x mod mo);
end;

procedure get_cir(var p,len:longint;k:longint);
var st,t:longint;
begin
  len:=1;
  inc(cir);
  p:=cir;
  c[p].k:=k;
  st:=p;
  t:=k*k mod mo;
  while t<>k do
  begin
    inc(len);
    inc(cir);
    c[p].nxt:=cir;
    p:=c[p].nxt;
    c[p].k:=t;
    t:=t*t mod mo;
  end;
  c[p].nxt:=st;
  p:=st;
end;

procedure add(var t:longint;c1,c2,len:longint);
var i,st,p:longint;
begin
  inc(cir);
  t:=cir;
  st:=cir;
  p:=st;
  c[cir].k:=c[c1].k+c[c2].k;
  for i:=1 to len-1 do
  begin
    inc(cir);
    c[p].nxt:=cir;
    p:=cir;
    c1:=c[c1].nxt;
    c2:=c[c2].nxt;
    c[p].k:=c[c1].k+c[c2].k;
  end;
  c[p].nxt:=st;
end;

procedure merge(t,c1,c2,len:longint);
var i:longint;
begin
  for i:=1 to len do
  begin
    c[t].k:=c[c1].k+c[c2].k;
    t:=c[t].nxt;
    c1:=c[c1].nxt;
    c2:=c[c2].nxt;
  end;
end;

procedure update(t:longint);
var ll,rl:longint;
begin
  s[t].sum:=s[s[t].lc].sum+s[s[t].rc].sum;
  ll:=s[s[t].lc].len;
  rl:=s[s[t].rc].len;
  if (s[t].len=0)and(ll<>0)and(rl<>0) then
  begin
    s[t].len:=ll*rl div gcd(ll,rl);
    add(s[t].cir,s[s[t].lc].cir,s[s[t].rc].cir,s[t].len);
  end else merge(s[t].cir,s[s[t].lc].cir,s[s[t].rc].cir,s[t].len);
end;

procedure build(var t:longint;l,r:longint);
var mid:longint;
begin
  inc(tot);
  t:=tot;
  s[t].lc:=0;
  s[t].rc:=0;
  s[t].sum:=0;
  s[t].len:=0;
  s[t].mk:=0;
  s[t].l:=l;
  s[t].r:=r;
  if l=r then
  begin
    if incir[x[l]] then get_cir(s[t].cir,s[t].len,x[l]);
    s[t].sum:=x[l];
    exit;
  end;
  mid:=(l+r)>>1;
  build(s[t].lc,l,mid);
  build(s[t].rc,mid+1,r);
  update(t);
end;

procedure rotate(t,d:longint);
var i:longint;
begin
  if t=0 then exit;
  d:=d mod s[t].len;
  inc(s[t].mk,d);
  for i:=1 to d do s[t].cir:=c[s[t].cir].nxt;
  s[t].sum:=c[s[t].cir].k;
end;

procedure pushdown(t:longint);
begin
  if s[t].mk=0 then exit;
  rotate(s[t].lc,s[t].mk);
  rotate(s[t].rc,s[t].mk);
  s[t].mk:=0;
end;

procedure modify(t,l,r:longint);
var mid:longint;
begin
  if s[t].mk<>0 then pushdown(t);
  if (l<=s[t].l)and(r>=s[t].r) then
  begin
    if s[t].len<>0 then rotate(t,1) else if s[t].l=s[t].r then
    begin
      s[t].sum:=sqr(s[t].sum)mod mo;
      if incir[s[t].sum] then get_cir(s[t].cir,s[t].len,s[t].sum);
    end else
    begin
      modify(s[t].lc,l,r);
      modify(s[t].rc,l,r);
      update(t);
    end;
    exit;
  end;
  mid:=(s[t].l+s[t].r)>>1;
  if l<=mid then modify(s[t].lc,l,r);
  if r>mid then modify(s[t].rc,l,r);
  update(t);
end;

function query(t,l,r:longint):longint;
var mid:longint;
begin
  if s[t].mk<>0 then pushdown(t);
  if (l<=s[t].l)and(r>=s[t].r) then exit(s[t].sum);
  mid:=(s[t].l+s[t].r)>>1;
  query:=0;
  if l<=mid then inc(query,query(s[t].lc,l,r));
  if r>mid then inc(query,query(s[t].rc,l,r));
end;

begin
  readln(n,m,mo);
  for i:=0 to mo-1 do incir[i]:=false;
  for i:=0 to mo-1 do v[i]:=0;
  tot:=0;
  for i:=0 to mo-1 do if v[i]=0 then
  begin
    inc(tot);
    find_cir(i);
  end;
  for i:=1 to n do read(x[i]);
  tot:=0;
  cir:=0;
  build(rt,1,n);
  for i:=1 to m do
  begin
    readln(op,l,r);
    if op=0 then modify(1,l,r) else writeln(query(1,l,r));
  end;
end.