题解 P3924 【康娜的线段树】

· · 题解

by zcysky

出题人是个智障，这个题可能是洛谷2017年以来月赛最简单的题。

原本出题人这段时间在沉迷Angel Beats，结果他正打算写题面的时候发现了一个了不得的事实：

曾经有一位叫做jxxx_2的dalao用过Tachibana Kanade作为某种线段树的代言人……

于是题面就变成了现在泥萌看到的样子。（还挺萌的不是吗~）

30分：

您会写线段树吗？

直接模拟即可。

什么？不会写？那就把题面上的拖下来即可。

70分：

考虑期望的性质。我们发现期望具有线性性。那么每一棵子树全部被区间加之后对答案的贡献可以单独计算。于是就可以用正常的线段树打标记的做法进行维护。

复杂度： O(nlogn)

100分：

回顾计算答案的过程，我们发现对答案产生实际贡献的点只跟叶子节点和他的深度有关。深度可以维护叶子节点的深度前缀和，这样可以 O(1) 的回答询问。

具体贡献的计算方法非常简单，如果还不清楚的可以看标程。

复杂度：O(n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+5;
ll sumv[maxn<<1],a[maxn],s[maxn];
int p[maxn];
namespace io
{
    const int MAXBUF = 1 << 22;
    char B[MAXBUF], *S = B, *T = B;
    #define getc() (S == T && (T = (S = B) + fread(B, 1, MAXBUF, stdin), S == T) ? 0 : *S++)
    template<class Type> inline Type read()
    {
        register Type aa = 0;
        register bool bb = 0;
        register char ch, *S = io::S, *T = io::T;
        for(ch = getc(); (ch < '0' || ch > '9') && ch != '-'; ch = getc())
            ;
        for(ch == '-' ? bb = 1 : aa = ch - '0', ch = getc(); '0' <= ch && ch <= '9'; ch = getc())
            aa = aa * 10 + ch - '0';
        io::S = S, io::T = T;
        return bb ? -aa : aa; 
    }
    int (*F)() = read<int>;

    template<> inline double read()
    {
        register double aa, bb;
        register char ch;
        register char *S = io::S, *T = io::T;
        while(ch=getc(),(ch<'0'||ch>'9'))
            ;aa=ch-'0';
        while(ch=getc(),(ch>='0'&&ch<='9'))aa=aa*10+ch-'0';
        if(ch=='.'){bb=1;while(ch=getc(),ch>='0'&&ch<='9')bb*=0.1,aa+=bb*(ch-'0');}
        io::S = S, io::T = T;
        return aa;
    }

    char buff[MAXBUF], *iter = buff;
    template<class T>inline void P(register T x, register char ch = '\n')
    {
        static int stack[110];
        register int O = 0;
        register char *iter = io::iter;
        if(!x)*iter++ = '0';
        else
        {
            (x < 0) ? x = -x, *iter++ = '-' : 1;
            for(; x; x /= 10)
                stack[++O] = x % 10;
            for(; O; *iter++ = '0' + stack[O--])
                ;
        }
        *iter++ = ch, io::iter = iter;
    }

    inline void putc(register char ch) {*iter++ = ch;}

    inline void ouput() {fwrite(buff, 1, iter - buff, stdout), iter = buff;}
}
#define lson o<<1
#define rson o<<1|1
int d=0;
inline void build(int l,int r,int o,int t){
    if(l==r){sumv[o]=a[l];p[l]=t;d=max(d,t);return;}
    int mid=l+r>>1;
    build(l,mid,lson,t+1);
    build(mid+1,r,rson,t+1);
    sumv[o]=sumv[lson]+sumv[rson];
}
inline ll query(int l,int r,int o,int t,ll tt){
    if(l==r){return 1LL*(1LL<<t)*(tt+sumv[o]);}
    int mid=l+r>>1;
    return query(l,mid,lson,t-1,tt+sumv[o])+query(mid+1,r,rson,t-1,tt+sumv[o]);
}
ll gcd(ll a,ll b){
    while(b){
        ll r=a%b;a=b;b=r;
    }
    return a;
} 
int main(){
    using io::P;
    int (*F)()=io::read<int>;
    int n=F(),m=F(),yyy=F();
    for(register int i=1;i<=n;++i)a[i]=F();
    build(1,n,1,1);
    ll ans=query(1,n,1,d-1,0),y=1LL<<(d-1);
    ll yy=gcd(y,yyy);yyy/=yy;y/=yy;
    for(register int i=1;i<=n;++i)s[i]=s[i-1]+1LL*(((1LL<<p[i])-1)<<(d-p[i]));
    while(m--){
        int l=F(),r=F(),x=F();
        ans+=(s[r]-s[l-1])*x;
        P(ans/y*yyy);
        io::ouput();
    }
}