专栏首页一Wa哇一天牛牛的Link Power II

牛牛的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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • D. Same GCDs

    time limit per test:2 seconds memory limit per test:256 megabytes inputstandard...

    某些人
  • 并查集

    POJ 的题真的是对小白选手的一个大的磨炼了,看了好久才明白题意,然后发现还是不会写题意就是给你一个数n,然后又n次操作,每次操作有两种情况如果第一个字符是 M...

    某些人
  • D. Minimax Problem

    time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • Codeforces Round #633 (Div. 2) A ~~C

    用户7727433
  • 51Nod 1004 n^n的末位数字(日常复习快速幂,莫名的有毒,卡mod值)

    1004 n^n的末位数字 题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5...

    Angel_Kitty
  • Winter Camp 1

    AngelNH
  • 独家|V神最新论文足足有41页?这24个要点,让你快速了解社区中立社会的正式规则

    由于V神这篇论文超级超级长,因此,小编主要针对论文中 abstract、introduction 和 background 三部分进行了初步的解读(V神的思维跳...

    区块链大本营
  • 洛谷 P1019 单词接龙

    单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两...

    glm233
  • 【程序源代码】开源学校教务管理系统

    后台:权限控制,支持多个管理员,学生管理,学生成绩,教师管理,文章管理,站点管理,网站布局自动化,多导航模式,友情链接,站点工具。

    程序源代码
  • Python + Flask程序调试技巧(2):导入自定义模块失败

    当导入字定义模块文件:model/rtindex中自定义的函数:pay_sum_query()时,提示:"unresolved reference"。具体现象如...

    数据饕餮

扫码关注云+社区

领取腾讯云代金券