Link PowerⅡ题解报告

分块大法吼啊！(ಡωಡ)

虽然知道是线段树。
但是我觉得~~好久没搞线段树。我不会打惹~~过于无趣。
所以用了分块。
谁叫这题数据<= $10^5$ ，明摆着练分块的，分块的每次操作是 $O(\sqrt n)$
然后就是经常有的：码字15分钟，debug 2小时，搞得我连模拟题都没做完。
。。。难受qwq

分块思想

把一个整体分成一块块，遍历块比遍历点快很多很多很多。。
不知道数据是不是随机的，所以把整体分成 $\sqrt n$ 块，因为这样理论上是最快的，请自行了解~~

本题思路

首先是基本要有的
1. $block$ :代表一个块有 $block$ 个元素
2. $blnum$ :代表有 $blnum$ 个块
就是这个 $blnum$ 没处理好，害的我白提交6次，多耗费1h多时间
图片标题
3. $blv[i]$ :代表第i个块里有 $blv[i]$ 个元素
4. $seat[i]$ :代表第i个元素在第 $seat[i]$ 个块里
接下来是本题的操作
5.题目思想:先打一个最开始的 $sum$ ，照抄 $F$ 里面的就行，然后我们想，每把第 $x$ 个从 $0$ 变成 $1$ ，就会增加 $x$ 到其他点距离和的值( $sum+=dissum(x)$ )，反之，则减少 $x$ 点到其他点距离和的值( $sum-=dissum(x)$ )。
6. $bll[i]$ :代表第 $i$ 个块里所有点到该块左边界( $(i-1)*block+1$ )的距离
7. $blr[i]$ :代表第 $i$ 个块里所有点到该块右边界( $i*block$ )的距离

本题核心qwq

那么每次新来一个 $x$ ，不管是加还是减，都要先求出距离和，所以如何求距离和呢？
不妨画一个图，有点丑。。。。

红色的是修改的点
假设这个图就这么点东西:
1.两条 $rdis$ 就是 $blr[]$
2.对于该块外的点，增加的距离和是
一.左侧: $blr[i]+(mdis+红点ldis+1)*blv[i]$ ，加1是细节问题， $mdis$ 是中间完整块的长度
二.右侧: $bll[i]+(mdis+红点rdis+1)*blv[i]$
3.对于块内的点，直接枚举反正一个块也就 $\sqrt n$
4.注意，对于修改完的红点，需要在原来的地方进行，并且同时维护那几个数组
然后就没了~~
贴上蒟蒻代码:

#include<bits/stdc++.h>
#define maxn 100010
#define Mod 1000000007
using namespace std;

int n,m,last;
long long num,sum,now,block;
string str;
bool Map[maxn];

int bll[1010],blr[1010],blv[1010],seat[maxn],blnum; 

void Build()
{
    block=sqrt(n);
    if(n%block!=0) ++block;
    if(n%block==0) blnum=n/block;
    else blnum=n/block+1;  
    for(int i=1;i<=n;++i) 
        seat[i]=(i-1)/block+1;
    for(int i=1;i<=n;++i){
        int j=str[i-1];
        if(j=='0') continue;
        ++blv[seat[i]];
        bll[seat[i]]+=i-(block*(seat[i]-1)+1);
        blr[seat[i]]+=min(block*seat[i],1LL*n)-i;
    }
}

long long Dis_sum(int x){
    long long res=0;
    long long x_l=x-(1LL*(seat[x]-1)*block+1),x_r=min(1LL*seat[x]*block,1LL*n)-x;
    if(seat[x]>1)
        for(int i=seat[x]-1;i>=1;--i){
            long long m_dis=1LL*(seat[x]-i-1)*block;
            res=(res+(x_l+m_dis+1)*blv[i]%Mod+blr[i])%Mod;
        }
    if(seat[x]<blnum)
        for(int i=seat[x]+1;i<=blnum;++i){
            long long m_dis=1LL*(i-seat[x]-1)*block;
            res=(res+(x_r+m_dis+1)*blv[i]%Mod+bll[i])%Mod;
        }
    for(int i=(seat[x]-1)*block+1;i<=min(seat[x]*block,1LL*n);++i)
        if(Map[i]==1)
            res=(res+1LL*abs(i-x))%Mod;
    return res;
}

int main(){
    scanf("%d",&n);
    cin>>str;
    Build();
    for(int i=0;i<n;++i){
        if(str[i]=='1'){
            now=(now+(i-last)*num%Mod)%Mod;
            sum=(sum+now)%Mod;
            last=i;
            num++;
            Map[i+1]=1;
        }
        else Map[i+1]=0;
    }
    printf("%lld\n",sum);
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        int opt,x;
        scanf("%d%d",&opt,&x);
        long long dis_sum=Dis_sum(x);
        if(opt==1){
            Map[x]=1;
            blv[seat[x]]++;
            bll[seat[x]]+=x-((seat[x]-1)*block+1);
            blr[seat[x]]+=min(1LL*n,seat[x]*block)-x;
            sum=(sum+dis_sum)%Mod;
            printf("%lld\n",sum);
        }
        if(opt==2){
            Map[x]=0;
            blv[seat[x]]--;
            bll[seat[x]]-=x-((seat[x]-1)*block+1);
            blr[seat[x]]-=min(seat[x]*block,1LL*n)-x;
            sum=(sum-dis_sum+1LL*100000*Mod)%Mod;
            printf("%lld\n",sum);
        }
    }
    return 0;
}

分块永远是正宫...这种思想啥都能维护(ಡωಡ)