SPOJ GSS8 - Can you answer these queries VIII

题目链接

这一道题的修改操作用平衡树都很容易实现，难处理的是询问操作。

要想解决询问操作，只要知道如何在平衡树上快速合并左右两个区间的答案即可。

设$Ans_{[l,r]}^k=\sum\limits_{i=l}^rA(i)\cdot(i-l+1)^k$。

设现在要处理的区间为$[x,y]$，中间位置为$mid$，已知$Ans_{[x,mid-1]}^k$和$Ans_{[mid+1,y]}^k$,要求$Ans_{[x,y]}^k$。

显然，$Ans_{[x,y]}^k=Ans_{[x,mid-1]}^k+A(mid)\cdot(mid-l+1)^k+\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k$。

观察式子，发现最左边的部分已知，中间的部分容易求得，关键是要快速求出最右边的部分。

从充分利用已知信息的角度考虑，我们可以先试图让最右边的部分和$Ans_{[mid+1,y]}^k$扯上关系。

于是我们就这样变：

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{i=mid+1}^yA(i)\cdot(i-mid+mid-x+1)^k$。

那个$i-mid$可以看成是$i-(mid+1)+1$，是$Ans_{[mid+1,y]}^k$展开后里面的一部分，于是我们考虑令$s=mid-x+1$。

那么原式就可变成这样子：

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{i=mid+1}^yA(i)\cdot(i-mid+s)^k$。

更据二项式定理，可得：

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{i=mid+1}^yA(i)\cdot\sum\limits_{j=0}^kC_k^j(i-mid)^js^{k-j}$。

把$A(i)$扔进最里面的那个求和里，可得：

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{i=mid+1}^y\sum\limits_{j=0}^kA(i)\cdot(i-mid)^jC_k^js^{k-j}$。

交换一下里外的两层求和，再把$C_k^js^{k-j}$提出来，可得:

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{j=0}^kC_k^js^{k-j}\sum\limits_{i=mid+1}^yA(i)\cdot(i-mid)^j$。

然后我们可以发现里面的那层求和的形式和询问的式子的一模一样，于是我们就有：

$\sum\limits_{i=mid+1}^yA(i)\cdot(i-x+1)^k=\sum\limits_{j=0}^kC_k^js^{k-j}Ans_{[mid+1,y]}^j$。

那么，对于平衡树上每一个节点所代表的区间，我们可以把每一种$k$的答案都存起来，再预处理组合数，这样我们就可以用$O(k^2)$的时间完成对两个区间答案的合并，按照上面得到的结果计算即可。由于$k$很小，所以这个时间复杂度还是可以接受的。

至此，这道题的难点就解决了。

坑点：这道题是对$2^{32}$取模，计算过程中又有乘法，所以中间结果会爆long long，所以应该用unsigned long long存储和计算答案。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

    using namespace std;

    const int MxK=10;

    const unsigned long long INF=1e18;

    const unsigned long long mod=((long long)1<<32);

struct Data

{

    int Fa,Siz,Son[2];

    unsigned long long Val,Ans[11];

}S[200005];

    int tot=0,Root=0;

    unsigned long long ml[12],Num[100005],C[12][12];

inline long long rdin()

{

    char ch=getchar();

    register long long x=0;

    while(ch<'0'||ch>'9') ch=getchar();

    while(ch>='0'&&ch<='9')

        x=(x<<3)+(x<<1)+ch-48,ch=getchar();

    return x;

}

void Csh()

{

    S[0].Siz=0;

    for(int i=0;i<=MxK;i++)

        C[i][0]=1,S[0].Ans[i]=0;

    for(int i=1;i<=MxK;i++)

        for(int j=1;j<=i;j++)

            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

}

int NewNode(unsigned long long w)

{

    int x=++tot;

    S[x].Siz=1,S[x].Val=w;

    S[x].Son[0]=S[x].Son[1]=0;

    for(int i=0;i<=MxK;i++) S[x].Ans[i]=w;

    return x;

}

void PushUp(int p)

{

    int L=S[p].Son[0];

    int R=S[p].Son[1];

    int l=1,mid=S[L].Siz+1;

    int x=mid-l+1;

    unsigned long long s=1;

    ml[0]=1;

    for(int i=1;i<=MxK;i++)

        ml[i]=ml[i-1]*x%mod;

    for(register int k=0;k<=MxK;k++)

    {

        unsigned long long w=0;

        for(int i=0;i<=k;i++)

            w=(w+ml[k-i]*C[k][i]%mod*S[R].Ans[i]%mod)%mod;

        S[p].Ans[k]=(S[L].Ans[k]+S[p].Val*s%mod+w)%mod;

        s=s*x%mod;

    }

    S[p].Siz=S[L].Siz+S[R].Siz+1;

}

int BuildTree(int l,int r)

{

    if(l>r) return 0;

    int mid=(l+r)>>1;

    int u=NewNode((Num[mid]==-INF)?0:Num[mid]);

    S[u].Son[0]=BuildTree(l,mid-1);

    S[u].Son[1]=BuildTree(mid+1,r);

    if(S[u].Son[0]) S[S[u].Son[0]].Fa=u;

    if(S[u].Son[1]) S[S[u].Son[1]].Fa=u;

    PushUp(u); return u;

}

int GetP(int x) {return S[S[x].Fa].Son[1]==x;}

void Rotate(int x)

{

    int p=GetP(x),f=S[x].Fa;

    if(S[f].Fa) S[S[f].Fa].Son[GetP(f)]=x;

    S[x].Fa=S[f].Fa;

    if(S[x].Son[p^1]) S[S[x].Son[p^1]].Fa=f;

    S[f].Son[p]=S[x].Son[p^1];

    S[x].Son[p^1]=f,S[f].Fa=x;

    PushUp(f);

}

void Splay(int x)

{

    while(S[x].Fa)

    {

        if(S[S[x].Fa].Fa&&GetP(x)==GetP(S[x].Fa)) Rotate(S[x].Fa);

        Rotate(x);

    }

    PushUp(x),Root=x;

}

int FindKth(int p,int k)

{

    int c=S[S[p].Son[0]].Siz+1;

    if(c==k) return p;

    if(c<k) return FindKth(S[p].Son[1],k-c);

    return FindKth(S[p].Son[0],k);

}

void SplitTree(int p,int k,int &x,int &y)

{

    x=FindKth(p,k),Splay(x);

    y=S[x].Son[1],S[y].Fa=0,S[x].Son[1]=0;

    PushUp(x);

}

int MergeTrees(int x,int y)

{

    Splay(x),Splay(y);

    while(S[x].Son[1]) x=S[x].Son[1];

    Splay(x),S[x].Son[1]=y,S[y].Fa=x;

    PushUp(x); return x;

}

void ChangeNode(int x,int w)

{

    S[x].Val=w;

    for(int i=0;i<=MxK;i++)

        S[x].Ans[i]=w;

}

void InsertVal(int x,int w)

{

    int u=NewNode(w);

    x=FindKth(Root,x-1),Splay(x);

    x=S[x].Son[1];

    while(S[x].Son[0]) x=S[x].Son[0];

    S[x].Son[0]=u,S[u].Fa=x,Splay(u);

}

void DeleteVal(int x)

{

    x=FindKth(Root,x),Splay(x);

    int l=S[x].Son[0];

    int r=S[x].Son[1];

    S[x].Son[0]=S[x].Son[1]=0;

    S[l].Fa=S[r].Fa=0;

    Root=MergeTrees(l,r);

}

void ChangeVal(int x,int w)

{

    x=FindKth(Root,x);

    ChangeNode(x,w),Splay(x);

}

unsigned long long Ask(int x,int y,int k)

{

    int a=0,b=0,c=0,d=0;

    unsigned long long res=0;

    SplitTree(Root,x-1,a,b);

    SplitTree(b,y-x+1,c,d);

    res=S[c].Ans[k];

    b=MergeTrees(c,d);

    Root=MergeTrees(a,b);

    return res;

}

int main()

{

    int n=0,m=0;

    n=rdin(),Csh();

    for(int i=1;i<=n;i++) Num[i]=rdin();

    Num[0]=-INF,Num[n+1]=-INF;

    Root=BuildTree(0,n+1);

    m=rdin();

    for(int i=1;i<=m;i++)

    {

        char opt=getchar();

        while(opt!='I'&&opt!='D'&&opt!='R'&&opt!='Q')

            opt=getchar();

        if(opt=='I')

        {

            int x=rdin(),y=rdin();

            InsertVal(x+2,y);

        }

        if(opt=='D')

        {

            int x=rdin();

            DeleteVal(x+2);

        }

        if(opt=='R')

        {

            int x=rdin(),y=rdin();

            ChangeVal(x+2,y);

        }

        if(opt=='Q')

        {

            int l=rdin(),r=rdin(),k=rdin();

            printf("%llu\n",Ask(l+2,r+2,k));

        }

    }

    return 0;

}

SPOJ GSS8

巴特西

SPOJ GSS8 - Can you answer these queries VIII | 平衡树

最新文章

热门文章