@[TOC]

题目链接：牛牛的Link Power II

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
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≤n≤10^5^)
接下里一行输入一个长度大小为n的01串表示数组的初始状态，'1'表示Link状态，'0'表示Cut状态。
接下来一行输入一个正整数m(1≤m≤10^5^) 表示操作的数目
接下来m行，每行输入两个正整数q,pos(q∈{1,2},1≤pos≤n)
当q=1时表示牛牛对数组的第pos个元素进行操作，将其赋值为1，保证在这个操作之前，该元素的值为0。
当q=2时表示牛牛对数组的第pos个元素进行操作，将其赋值为0，保证在这个操作之前，该元素的值为1。
输出描述:
请输出m+1行表示一开始，以及每次操作之后整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对10^9^+7取余后的结果即可。
示例1
输入

输出

题目大意

给你一个n，然后有一个长度为 n 的01字符串，问你任意两个1之间的距离之和；比如说111这三个 1 吧，输出结果就是 4，然后给你一个数 m 有m次操作每次操作有两个数 x，y。
x=1 就把位置为y的值变成1，然后输出所有的1的距离之和
x=2 就把位置为y的值变成0，然后输出所有的1的距离之和

解题思路

这个很明显的需要用线段树或树状数组去求解，这里我就用树状数组来讲解。我们很容易发如果给你一个序列，比如是 100101；这个01串，如果把第3个位置变成1，那么更变后多产生了多少值呢？产生了（1,3），（3,4），（3,6）；这三段；如果把第5个位置变成1呢？那么多产生的就是（1,5），（4,5），（5,6）；我们发现当我们插入值得时候，只会产生新的对数，对于之前的距离和不会改变，我们只需要吧之前的加上现在新增的就可以了。
如何求新增的呢？这里设插入位置为 y ，通过上面俩次模拟我么发现一个公式新增加的数量就是y前面1的数量乘以y减去y前面的前缀和再加上 y以后的后缀和减去 y乘以y后面1的数量；这里的后缀和就是位置唯一的值之和，比如说11011，前缀和sum5=1+2+4+5；这时候我们只需要维护一个前缀和就可以了。
！！！！！更重要的是记得最后加mod再次进行取模！！！！！不要问我为啥这么激动。。。。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const ll mod=1e9+7;
char b[100100];
ll sc[100100];// 存1的数量的前缀和 
ll sm[100100];// 存 值为1的坐标的前缀和 

void add(ll x,ll k)
{
    ll f=1;
    if(k<0) f=-1;//如果 k 小于 0的时候表示把1变成0需要减  
    for(ll i=x;i<=n;i+=(i&-i))
    {
        sc[i]+=f;
        sm[i]=(sm[i]+k)%mod;
    }
    return;
}
ll sum_c(ll x)//求前面 1 数量的前缀和 
{
    ll ans=0;
    for(ll i=x;i;i-=(i&-i))
    {
        ans=ans+sc[i];
    }
    return ans%mod;
}
ll sum_s(ll x)//求 值为1的坐标的前缀和
{
    ll ans=0;
    for(ll i=x;i;i-=(i&-i))
    {
        ans=(ans+sm[i])%mod;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",b+1);
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        if(b[i]=='1')
        {
            add(i,i);//更新两个前缀和 
            //根据公式设刚开始是一个空的子串开始加 
            ans=(ans+sum_c(i-1)*i-sum_s(i-1))%mod;
            //因为刚开始是从前到后的所以不用管 i 后面的位置 
        }
    }
    cout<<ans<<"\n";
    ll m;
    cin>>m;
    ll x,y;
    while(m--)
    {
        cin>>x>>y;
        if(x==1)
        {
            ll sum_p=sum_s(y);//求出前面值为1的坐标的前缀合 
            ll sum_n=sum_s(n)-sum_p;//求后面值为1的坐标的前缀和 

            ll suc_p=sum_c(y);// 求前面 1 一共有多少个1 
            ll suc_n=sum_c(n)-suc_p;// 求后面一共有多少个1 
            //根据推出来的公式操作 
            ans=(ans+y*suc_p%mod-sum_p+sum_n-suc_n*y%mod)%mod;
            ans=(ans+mod)%mod;//这里一定记得再次取模！！！！！！ 
            add(y,y);//更新 
            cout<<ans<<"\n";
        }
        else{
            add(y,-y);//这里先更新是为了更新后这个位置刚好是0；
                      //对求后面的值不影响     
            ll sum_p=sum_s(y);
            ll sum_n=sum_s(n)-sum_p;

            ll suc_p=sum_c(y);
            ll suc_n=sum_c(n)-suc_p;//这是把1变成0所以要减 
            ans=(ans-(y*suc_p-sum_p+sum_n-suc_n*y)%mod+mod)%mod;
            ans=(ans+mod)%mod;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

牛牛的Link Power II（数组数组）

题目链接：牛牛的Link Power II

题目大意

解题思路

代码