牛客2020寒假训练营3-G

牛客2020寒假训练营3-G

七月 15, 2020

牛牛的Link Power II

题意
牛牛有一颗大小为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能量，为了避免这个数字过于庞大，你只用输出答案对1e9+7取余后的结果即可。

题解
就我们发现每个“1”对于它本身位置产生的影响贡献为0，而往后面依次产生了0,1,2,3,4,5…的贡献
比如10001 对于第一个1到第二个1共产生 4的贡献
那么可以在每个1的位置到最后一个位置全部+1
那么对于一个1 我们可以 求和区间 [1到它当前位置] 上的贡献来计算出这个1产生的值

开两颗线段树，一颗叫pre树，一颗叫suf树，然后对于每个位置为pos的”1”，都在pre树的[pos+1,n]这个区间加上1，在suf树中的[1,pos−1]这个区间加上1 然后对于每个1，他跟别人产生的贡献就是pre树的sum(1,pos)+suf树的sum(pos,n)sum

因为加入删除1 的操作 不但会对之后的1产生新的贡献(所以更新pre[pos+1,n])
自身也会对之前的1产生贡献(所以更新suf[1,pos-1])
比如100001在中间0->1 那么第1个1对中间的1产生贡献用pre[1,pos]统计 并更新pre[pos+1,n], 最后的1对中间的1产生贡献用suf[pos,n]统计 并更新suf[1,pos-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

const int maxn=(int)1e5+5;
const ll mod=(ll)1e9+7;
struct Tree{
    ll sum,lazy;
    int L,R;
};
struct Segment_Tree{
    Tree tree[4*maxn];
    void push_up(int root){tree[root].sum=(mod+tree[root<<1].sum+tree[root<<1|1].sum)%mod;}
    void push_down(int root){
        if(tree[root].lazy){
            tree[root<<1].lazy=(mod+tree[root<<1].lazy+tree[root].lazy)%mod;
            tree[root<<1|1].lazy=(mod+tree[root].lazy+tree[root<<1|1].lazy)%mod;
            tree[root<<1].sum=(mod+tree[root<<1].sum+tree[root].lazy*(tree[root<<1].R-tree[root<<1].L+1)%mod)%mod;
            tree[root<<1|1].sum=(mod+tree[root<<1|1].sum+tree[root].lazy*(tree[root<<1|1].R-tree[root<<1|1].L+1)%mod)%mod;
            tree[root].lazy=0;
        }
    }
    void build(int l,int r,int root=1){
        tree[root].L=l,tree[root].R=r;
        tree[root].sum=0,tree[root].lazy=0;
        if(l==r)return ;
        int mid=(l+r)>>1;
        build(l,mid,root<<1);
        build(mid+1,r,root<<1|1);
        push_up(root);
    }
    void updata(int qL,int qR,ll val,int now=1){
        if(tree[now].L>=qL&&tree[now].R<=qR){///注意取到的条件
            tree[now].sum=(mod+tree[now].sum+val*(tree[now].R-tree[now].L+1)%mod)%mod;
            tree[now].lazy=(mod+tree[now].lazy+val)%mod;
            return;
        }
        push_down(now);
        if(qL<=tree[now<<1].R)updata(qL,qR,val,now<<1);
        if(qR>=tree[now<<1|1].L)updata(qL,qR,val,now<<1|1);
        push_up(now);
        return;
    }
    ll query(int qL,int qR,int now=1){///注意if的条件
        if(tree[now].R<=qR&&tree[now].L>=qL) return tree[now].sum;
        push_down(now);
        ll sum=0;
        if(tree[now<<1].R>=qL)sum=(mod+sum+query(qL,qR,now<<1))%mod;
        if(tree[now<<1|1].L<=qR)sum=(mod+sum+query(qL,qR,now<<1|1))%mod;
        return sum;
    }
}pre,suf;
int main(){
    int n;cin>>n;ll ans=0;
    string s;cin>>s;
    pre.build(0,n-1);
    suf.build(0,n-1);
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            ans=(ans+pre.query(0,i))%mod;
            //cout<<pre.query(0,i)<<" ";
            if(i!=n-1)pre.updata(i+1,n-1,1);
            if(i!=0)suf.updata(0,i-1,1);
        }
    }
    //cout<<endl;
    cout<<ans<<endl;
    int t;cin>>t;
    while(t--){
        int ops,pos;
        cin>>ops>>pos;pos--;
        ll presum=pre.query(0,pos);///在它之前的1对它产生的贡献
        ll sufsum=suf.query(pos,n-1);///它之后的1对它产生的贡献
        if(ops==1){
            ans=(ans+presum+sufsum)%mod;
            if(pos!=n-1)pre.updata(pos+1,n-1,1);
            if(pos!=0)suf.updata(0,pos-1,1);
        }
        else{
            ans=(2*mod+ans-presum-sufsum)%mod;
            if(pos!=n-1)pre.updata(pos+1,n-1,-1);
            if(pos!=0)suf.updata(0,pos-1,-1);
        }
        cout<<ans<<endl;
    }
}