牛牛的Link Power II

题号：NC201819
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛有一颗大小为n的神奇Link-Cut 数组，数组上的每一个节点都有两种状态，一种为link状态，另一种为cut状态。数组上任意一对处于link状态的无序点对（即(u,v)和(v,u)被认为是同一对）会产生dis(u,v)的link能量，dis(u,v)为数组上u到v的距离。

我们定义整个数组的Link能量为所有处于link状态的节点产生的link能量之和。

一开始数组上每个节点的状态将由一个长度大小为n的01串给出，'1'表示Link状态，'0'表示Cut状态。

牛牛想要知道一开始，以及每次操作之后整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对 $10^9+7$ 取余后的结果即可。

第一行输入一个正整数n $(1 \leq n \leq 10^5)$

接下里一行输入一个长度大小为n的01串表示数组的初始状态，'1'表示Link状态，'0'表示Cut状态。

接下来一行输入一个正整数m $(1 \leq m \leq 10^5)$ 表示操作的数目

接下来m行，每行输入两个正整数q,pos $(q \in \{ 1,2 \},1 \leq pos \leq n)$

当q=1时表示牛牛对数组的第pos个元素进行操作，将其赋值为1，保证在这个操作之前，该元素的值为0。

当q=2时表示牛牛对数组的第pos个元素进行操作，将其赋值为0，保证在这个操作之前，该元素的值为1。

请输出m+1行表示一开始，以及每次操作之后整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对取余后的结果即可。

示例1

复制

复制