題目鏈接：點擊查看

題目大意：給出一個01字符串 s ，現在規定每兩個?1 的貢獻為其在字符串中的距離，現在有 m 次操作，每次操作會把一個位置將?0 變成 1 或者將 1 變成 0 ，問每次操作后字符串的總貢獻之和

題目分析：其實想清楚了就可以直接用線段樹來維護狀態，用區間合并處理一下細節就好了，假設每個節點代表著當前節點的貢獻，如果相鄰兩個節點想要合并的話，只需要再加上相鄰兩個節點互相的貢獻就好了，這個具體可以用平均值來解決，也就是每個節點所有 1 的下下標的平均值，因為線段樹在合并時，右節點的下標一定比左節點的下標要大，所以平均下標固然也大，所以顯然兩個節點之間的貢獻為( average_pos[ r?] - average_pos[ r ] ) * cnt[ r ] * cnt[ l ]，但是下標的平均值如果直接帶入會出現小數，不過我們只需要化簡一步就可以避免：

( average_pos[ r?] - average_pos[ r ] ) * cnt[ r ] * cnt[ l ]

=( sum_pos[ r?] / cnt[ r ] - sum_pos[ r ] / cnt[ l ]?) * cnt[ r ] * cnt[ l ]

= sum_pos[ r?] * cnt[ l ] - sum_pos[ r ] *?cnt[ r?]

其中cnt_pos是所有 1 的下標之和，這樣直接轉移就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=1e9+7;char s[N];struct Node {int l,r;LL pos_sum,cnt,ans;//pos_sum:所有位置之和 cnt:有多少個1 ans:答案 }tree[N<<2];void pushup(int k) {tree[k].cnt=tree[k<<1].cnt+tree[k<<1|1].cnt;tree[k].pos_sum=tree[k<<1].pos_sum+tree[k<<1|1].pos_sum;tree[k].ans=(tree[k<<1].ans+tree[k<<1|1].ans+(tree[k<<1|1].pos_sum%mod*tree[k<<1].cnt%mod+mod-tree[k<<1].pos_sum%mod*tree[k<<1|1].cnt%mod)%mod)%mod; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){if(s[l]=='1'){tree[k].pos_sum=l;tree[k].cnt=1;tree[k].ans=0;}else{tree[k].pos_sum=tree[k].cnt=tree[k].ans=0;}return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int pos,int val) {if(tree[k].l==tree[k].r){if(val){tree[k].pos_sum=pos;tree[k].cnt=1;tree[k].ans=0;}else{tree[k].pos_sum=tree[k].cnt=tree[k].ans=0;}return;}int mid=tree[k].l+tree[k].r>>1;if(mid>=pos)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);pushup(k); }int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);int n;scanf("%d%s",&n,s+1);build(1,1,n);printf("%lld\n",tree[1].ans);int m;scanf("%d",&m);while(m--){int op,pos;scanf("%d%d",&op,&pos);if(op==1)update(1,pos,1);elseupdate(1,pos,0);printf("%lld\n",tree[1].ans);}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的牛客 - 牛牛的Link Power II(线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。