牛牛的Link Power II
- 2020 年 4 月 9 日
- 筆記
題目鏈接：牛牛的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; }
