牛牛的Link Power II 思维线段树

题意大家都知道了..毕竟是为了看题解才来看题解..

这个题比赛过程中没有写是因为被I题规律卡了一个半小时，没有时间写了..其实后来想想发现也挺简单的。比赛过程中大体看了一眼感觉是线段树，只想着维护一棵线段树，但是其实需要维护两颗线段树。

具体思路：
首先我们根据 I 题里面求出序列初始的 CUT值：
假设我的序列为：1110001
那么如果我在5位置将0变为1，那么我会产生新的价值即为(1,5),(2,5),(3,5)，(5,7) 也就是 5-1+5-2+5-3+7-5，咱们不妨把这个式子化简一下那么就是 35-(1+2+3) 与 7-15，观察5之前的系数，即为该位置之前1的个数，括号里的内容是一个1的位置的前缀和，那么就好写多了。我们只需要维护 两颗线段树(为什么用线段树呢？因为我看到题解里面没有线段树的题解~hahaha)一棵维护区间内1的个数，另一颗维护区间内1的位置的求和
很容易得出 ：

0->1对应的修改为:

1->0对应的修改为：与0->1的操作相反 '+'->'-'

所以说具体的线段树修改操作我们只需要维护两种：

然后这个题目就基本解决了~

附一下AC代码：

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e13;
const ll maxn=1e6+5;
const int mod=1e9+7;
const double eps=1e-12;
ll n,m;
struct node{
    int l,r,flag=0;
    ll w;
}pre[maxn<<2],suff[maxn<<2];//区间内1的数量 ，区间内1的位置的总和
void build(node *p,int k,int l,int r){
    p[k].l=l;p[k].r=r;
    p[k].flag=0;
    p[k].w=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(p,k<<1,l,mid);
    build(p,k<<1|1,mid+1,r);
}
void update(node *p,int k,int pos,int w){//线段树单点修改
    if(p[k].l==p[k].r){
        p[k].w=(p[k].w+w)%mod;
        return;
    }
    int mid=(p[k].l+p[k].r)/2;
    if(pos<=mid) update(p,k<<1,pos,w);
    else update(p,k<<1|1,pos,w);
    p[k].w=(p[k<<1].w+p[k<<1|1].w)%mod;
}
ll query(node *p,int k,int x,int y){
    if(x<1||y>n) return 0;
    if(x<=p[k].l&&y>=p[k].r){
        return p[k].w;
    }
    ll sum=0;
    int mid=(p[k].l+p[k].r)/2;
    if(x<=mid) sum+=query(p,k<<1,x,y);
    if(y>mid) sum+=query(p,k<<1|1,x,y);
    return sum;
}
ll dp[maxn];//代表以当前节点结束的有能量值为多少
char str[maxn];
ll work()
{
    ll a=0,pos=-1;//前方1的数量,前放最后一个1出现的位置
    scanf("%lld%s",&n,str+1);
    for(int i=1;i<=n;i++){
        if(str[i]=='1'){
            if(pos!=-1)
            dp[i]=(dp[pos]+a%mod*(i-pos)%mod)%mod;
            a++;
            pos=i;
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++)
        if(str[i]=='1')
            res=(res+dp[i])%mod;
    return res;
}
int main()
{
    ll ans=work();
    build(pre,1,1,n);
    build(suff,1,1,n);//初始化两颗树
    for(int i=1;i<=n;i++){
        if(str[i]=='1'){
            update(pre,1,i,1);
            update(suff,1,i,i);
        }
    }
    printf("%lld\n",ans);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        if(x==1){
            ll cot_One=query(pre,1,1,y-1);//1~x-1有多少个1
            ll cot_sum=query(suff,1,1,y-1);
            ans=(ans+y*cot_One-cot_sum%mod+mod)%mod;
            cot_One=query(pre,1,y+1,n);//x+1~n有多少个1
            cot_sum=query(suff,1,y+1,n);//
            ans=(ans+cot_sum-(cot_One*y)%mod+mod)%mod;
            update(pre,1,y,1);
            update(suff,1,y,y);
        }
        else{
            ll cot_One=query(pre,1,1,y-1);//1~x-1有多少个1
            ll cot_sum=query(suff,1,1,y-1);
            ans=(ans-(y*cot_One-cot_sum%mod+mod)%mod+mod)%mod;
            cot_One=query(pre,1,y+1,n);//x+1~n有多少个1
            cot_sum=query(suff,1,y+1,n);//
            ans=(ans-(cot_sum-(cot_One*y)%mod+mod)%mod+mod)%mod;
            update(pre,1,y,-1);
            update(suff,1,y,-y);
        }
        printf("%lld\n",ans);
    }
    return 0;
}