牛牛的Link Power II

题目链接:牛牛的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
输入

5
00001
7
1 1
2 5
2 1
1 2
1 4
1 3
1 1

输出

0
4
0
0
0
2
4
10

题目大意

给你一个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;
}

 上一篇
E. Permutation Separation E. Permutation Separation
E. Permutation SeparationE. Permutation Separation time limit per test:2 seconds memory limit per test:256 megabytes inp
2020-04-01
下一篇 
D. Shortest and Longest LIS D. Shortest and Longest LIS
题目链接:D. Shortest and Longest LIStime limit per test3 seconds memory limit per test256 megabytes inputstandard input outp
2020-04-01
  目录