牛客练习赛46 E 华华和奕奕学物理 （树状数组）

https://ac.nowcoder.com/acm/contest/894/E

一开始写了一个简单的模拟 通过率只有5%......

看题解真的理解了好久！！肥宅大哭orz

题解如下

最后一句：“维护6个树状数组即可”.....喵喵喵？？

先学一下树状数组吧：

链接在这
https://blog.csdn.net/Small_Orange_glory/article/details/81290634

结合代码讲比较容易理解

#include<bits/stdc++.h>

using namespace std;

const int maxn=4e6+;

const int T=3e5+;

const int mod=1e9+;

const int g=;

#define ll long long

ll bit[][maxn];

void add(ll b[],int i,ll C)  //更新树状数组

{

    while(i<maxn)

    {

        b[i]=(b[i]+C)%mod;

        i+=i&-i;

    }

}

ll sum(ll b[],int i)   //求和 前i个元素的和

{

    ll  ans=;

    while(i>)

    {

        ans+=b[i];

        i-=i&-i;

    }

    return ans%mod;

}

int main()

{

    int Q;scanf("%d",&Q);

    while(Q--)

    {

        int op,v,t,m;scanf("%d%d%d",&op,&v,&t);

        if(op==)

        {

            int V=v+g*(T-t);

            scanf("%d",&m);

            add(bit[],V,1LL*m*v%mod*v%mod);

            add(bit[],V,1LL*m*g*g%mod);

            add(bit[],V,1LL*m*g*g%mod*t%mod*t%mod);

            add(bit[],V,1LL**m*g*g%mod*t%mod);

            add(bit[],V,1LL**m*v%mod*g%mod);

            add(bit[],V,1LL**m*v%mod*g*t%mod);

        }

        else

        {

            int V=min(v+g*(T-t),maxn-);

            ll ans=;

            ans+=sum(bit[],V);

            ans+=sum(bit[],V)*t%mod*t%mod;

            ans+=sum(bit[],V);

            ans-=sum(bit[],V)*t%mod;

            ans+=sum(bit[],V)*t%mod;

            ans-=sum(bit[],V);

            ans%=mod;

            if(ans<)

                ans+=mod;

            printf("%lld\n",ans);

        }

    }

    return ;

}

先讲为什么维护6个数组：

因为将公式

拆开就会变成含有6项的多项式：

我们将符合条件的小球的分别记录到6个数组中 这样方便求和

那么什么是符合条件的小球呢？

仔细看题解里说：

若某一时刻a球比b球速度快，则a球始终比b球速度快。

所以如果末尾时间a球比b球快 那么a球始终比b球快

所以判断某一时刻速度比v小的小球有哪些 假设在这一时刻扔下一个初速度为v的小球 只需要看哪些小球在最后的时刻速度比这个初速度为v的小球速度慢就好了

那么对于每一次op==1 我们就更新一次数组 把v+g*(T-t)之后的树状数组全部更新

对于每一次op==2 我们就把前v+g*(T-t)项求和

照着模拟几遍就理解了（而我想了一晚上）