M_sea

洛谷3924 康娜的线段树
Luogu算法看到样例的第一个操作的解释:(橙色表示该层每一个节点被进入的概率。可以发现与深度有关)(画的丑不要在...
扫描右侧二维码阅读全文
22
2018/08

洛谷3924 康娜的线段树

Luogu

算法

看到样例的第一个操作的解释:

img

(橙色表示该层每一个节点被进入的概率。可以发现与深度有关)
(画的丑不要在意)

可以发现,叶节点增加相当于把整个从根节点到叶节点的路径全部增加。

那么对每个叶节点维护一下根节点到叶节点的深度(黄字)的和,再求一遍前缀和,记为$s[]$。

现在看蓝字,发现将1~3全部加4,等于把那一片蓝色全部增加。

一般的,对于每一个修改操作$(x,y,z)$,和增加了$(s[y]-s[x-1])\times z$。

那么再求出期望即可。

注意开long long,还要约分。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m,qwq;
int ans=0,maxdep;
int s[1000010];

inline void build(int l,int r,int dep) { //并不用建树,只是求出s和初始化ans
    if (l==r) {
        s[l]=maxdep/dep*((dep<<1)-1);
        ans+=read()*s[l];
        s[l]+=s[l-1];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,dep<<1); build(mid+1,r,dep<<1);
}

mainint main() {
    n=read(),m=read(),qwq=read();
    for (maxdep=1;maxdep<n;maxdep<<=1); //找到最大的深度
    build(1,n,1);
    int d=__gcd(maxdep,qwq); qwq/=d,maxdep/=d; //约个分
    while (m--) {
        int x=read(),y=read(),z=read();
        ans+=(s[y]-s[x-1])*z;
        printf("%lld\n",ans*qwq/maxdep);
    }    
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 52 PM

发表评论