AT4163 [ARC099D] Eating Symbols Hard
不难发现，这些操作类似于子串哈希的过程。
同样的区间操作序列判断加强了我们的想法，哈希解决了问题。
考虑维护前缀哈希，一个区间 [ l , r ] [l,r] [l,r] 哈希值，应该是 [ 1 , r ] [1,r] [1,r] 哈希值，减去 [ 1 , l ? 1 ] [1,l-1] [1,l?1] 移位后的哈希值，顺便维护一下。
最后，判断双或三哈希，打开桶记录数量，时间复杂 O ( n ) \mathcal O(n) O(n)。
#include<bits/stdc .h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ha putchar(' ') #define he putchar('\n') inline int read() {
int x = 0, f = 1; char c =
getchar
(
)
;
while
(c
<
'0'
|| c
>
'9'
)
{
if
(c
==
'-'
) f
=
-
1
; c
=
getchar
(
)
;
}
while
(c
>=
'0'
&& c
<=
'9'
) x
= x
*
10
+ c
-
'0'
, c
=
getchar
(
)
;
return x
* f
;
}
inline
void
write
(ll x
)
{
if
(x
<
0
)
{
putchar
(
'-'
)
; x
=
-x
;
}
if
(x
>
9
)
write
(x
/
10
)
;
putchar
(x
%
10
+
'0'
)
;
}
const
int _
=
250010
*
2
;
const ll bs1
=
819
, Bs1
=
783725420
, md1
=
998244353
, bs2
=
1989
, Bs2
=
227249785
, md2
=
999999607
, bs3
=
1998
, Bs3
=
582062931
, md3
=
999967099
; ll n
, As
, pos
[_
]
; ull r1
, r2
, r3
, p1
[_
]
, P1
[_
]
, p2
[_
]
, P2
[_
]
, p3
[_
]
, P3
[_
]
, hs1
[_
]
, hs2
[_
]
, hs3
[_
]
;
char s
[_
]
; map
<tuple
<
int
,
int
,
int
>
,
int
> mp
;
signed
main
(
)
{
n
=
read
(
)
;
scanf
(
"%s"
, s
+
1
)
; p1
[
0
]
= P1
[
0
]
= p2
[
0
]
= P2
[
0
]
= p3
[
0
]
= P3
[
0
]
=
1
;
for
(
int i
=
1
; i
<= n
*
2
;
++i
)
{
p1
[i
]
= p1
[i
-
1
]
* bs1
% md1
; P1
[i
]
= P1
[i
-
1
]
* Bs1
% md1
; p2
[i
]
= p2
[i
-
1
]
* bs2
% md2
; P2
[i
]
= P2
[i
-
1
]
* Bs2
% md2
; p3
[i
]
= p3
[i
-
1
]
* bs3
% md3
; P3
[i
]
= P3
[i
-
1
]
* Bs3
% md3
;
} pos
[
0
]
= n
;
for
(
int i
=
1
; i
<= n
;
++i
)
{
pos
[i
]
= pos
[i
-
1
]
;
if
(s
[i
]
==
'>'
) pos
[i
]
= pos
[i
-
1
]
+
1
;
if
(s
[i
]
==
'<'
) pos
[i
]
= pos
[i
-
1
]
-
1
;
if
(s
[i
]
==
'+'
)
{
r1
=
(r1
+ p1
[pos
[i
]
]
)
% md1
; r2
=
(r2
+ p2
[pos
[i
]
]
)
% md2
; r3
=
(r3
+ p3
[pos
[i
]
]
)
% md3
;
}
if
(s
[i
]
==
'-'
)
{
r1
=
(r1
+ md1
- p1
[pos
[i
]
]
)
% md1
; r2
=
(r2
+ md2
- p2
[pos
[i
]
]
)
% md2
; r3
=
(r3
+ md3
- p3
[pos
[i
]
]
)
% md3
;
} hs1
[i
]
= r1
, hs2
[i
]
= r2
, hs3
[i
]
= r3
;
}
for
(
int i
= n
-
1
; i
>=
0
;
--i
)
{
mp
[
{
hs1
[i
+
1
]
, hs2
[i
+
1
]
, hs3
[i
+
1
]
}
]
++
; ull k1
=
(hs1
[i
]
+
(r1
*
(
(pos
[i
]
<= n
)
? P1
[n
- pos
[i
]
]
: p1
[pos
[i
]
- n
]
)
% md1
)
)
% md1
; ull k2
=
(hs2
[i
]
+
(r2
*
(
(pos
[i
]
<= n
)
? P2
[n
- pos
[i
]
]
: p2
[pos
[i
]
- n
]
)
% md2
)
)
% md2
; ull k3
=
(hs3
[i
]
+
(r3
*
(
(pos
[i
]
<= n
)
? P3
[n
- pos
[i
]
]
: p3
[pos
[i
]
- n
]
)
% md3
)
)
% md3
;
// cout << k1 << " " << k2 << "\n"; As
+= mp
[
{
k1
, k2
, k3
}
]
;
}
write
(As
)
;
return
0
;
}