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

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

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

题解如下

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

先学一下树状数组吧：

链接在这

https://blog.csdn.net/Small_Orange_glory/article/details/81290634

结合代码讲比较容易理解

#include
     
      using namespace std;const int maxn=4e6+100;const int T=3e5+10;const int mod=1e9+7;const int g=10;#define ll long longll bit[8][maxn];void add(ll b[],int i,ll C)  //更新树状数组{    while(i
      
       0)    {        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==1)        {            int V=v+g*(T-t);            scanf("%d",&m);            add(bit[1],V,1LL*m*v%mod*v%mod);            add(bit[2],V,1LL*m*g*g%mod);            add(bit[3],V,1LL*m*g*g%mod*t%mod*t%mod);            add(bit[4],V,1LL*2*m*g*g%mod*t%mod);            add(bit[5],V,1LL*2*m*v%mod*g%mod);            add(bit[6],V,1LL*2*m*v%mod*g*t%mod);        }        else        {            int V=min(v+g*(T-t),maxn-1);            ll ans=0;            ans+=sum(bit[1],V);            ans+=sum(bit[2],V)*t%mod*t%mod;            ans+=sum(bit[3],V);            ans-=sum(bit[4],V)*t%mod;            ans+=sum(bit[5],V)*t%mod;            ans-=sum(bit[6],V);            ans%=mod;            if(ans<0)                ans+=mod;            printf("%lld\n",ans);        }    }    return 0;}
      
     

先讲为什么维护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)项求和

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