@[Ace_FutureDream](/user/684960) TLE了，但我觉得是线性的复杂度
by Ace_FutureDream @ 2024-04-20 21:49:57
@[Ace_FutureDream](/user/684960) 虽然我看不懂你的但是我的思路跟你说了你应该会大为震惊，线段树+平衡树，线段树用于记录大小写的改变次数，平衡树用于反转字符串
详见 [我的提交](https://atcoder.jp/contests/abc350/submissions/52615490)
by kevinZ99 @ 2024-04-20 21:55:45
@[kevinZ99](/user/1117080) 这两个只需要平衡树就够了，在翻转的同时大小写切换
by murder_drones @ 2024-04-20 21:57:57
@kevinZ99？？？有这么复杂吗？
by Ace_FutureDream @ 2024-04-20 21:58:36
@[kevinZ99](/user/1117080) 我的思路是递归找到每个区间再合并起来，正确性是对的，但时间复杂度为什么寄了我不理解
by Ace_FutureDream @ 2024-04-20 21:59:38
@[murder_drones](/user/610393) 啊，反正我赛时只想到了这个，没想太多 @[Ace_FutureDream](/user/684960)
by kevinZ99 @ 2024-04-20 21:59:48
哦，好像是O(n^2)，暴力翻转复杂度高
by Ace_FutureDream @ 2024-04-20 22:01:48
@[Ace_FutureDream](/user/684960) 能到n方吧？
(a(a(a...a)a)a)
by murder_drones @ 2024-04-20 22:02:15
@[murder_drones](/user/610393) $|S|\le 5\times10^5$
by Ace_FutureDream @ 2024-04-20 22:03:03
每一个括号区间都能在递归中产生一个string，这是括号长度的，那么上面的复杂度是n方。 @[Ace_FutureDream](/user/684960)
by murder_drones @ 2024-04-20 22:03:55