Codeforces878E. Numbers on the blackboard

$n \leq 100000$的数列，数字范围$-1e9,1e9$，现$q \leq 1e5$个每次问在一个区间玩游戏，能得到的最大的数。“游戏”：选相邻两个数$a_x,a_y$，然后把他们删掉，变成$a_x+2a_y$，直到序列中只剩一个数。答案$\mod \ \ 1e9+7$。

单次询问可用贪心解决：首先第一个数系数一定是1，后面的数的系数是$2^k,k\geq 1$且$k$不会比上一个数的$k$多2以上。用一块表示给某个区间分配了系数2，4，8，16，。。。，也就是这个区间从左到右一个个合并，那么在数列右边加入一个新的数时，如果这个数是负数，那给他新开一块，否则合并到上一块中，若上一块的答案因此变成了正的，那就继续往前合并。

多次询问只需离线一下，记一下每个块的位置，然后按上面的方法模拟，询问时二分一下就好了。不过要注意，询问时可能左端点处不是一个完整块，这时需要把那个块的后缀单独拿出来算答案。

有个大问题：数字很大，如何判断大小以决定某个块是否要往前并？可以发现负权值最小只到2e9，因此超过2e9的正权值记成2e9+1就行了。

 //#include<iostream>

 #include<cstring>

 #include<cstdio>

 //#include<math.h>

 //#include<set>

 //#include<queue>

 //#include<vector>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define LL long long

 int qread()

 {

     char c; int s=,f=; while ((c=getchar())<'' || c>'') (c=='-') && (f=-);

     do s=s*+c-''; while ((c=getchar())>='' && c<=''); return s*f;

 }

 //Pay attention to '-' , LL and double of qread!!!!

 int n,m;

 #define maxn 100011

 const int mod=1e9+;

 int a[maxn],pos[maxn],bin[maxn],inv[maxn],sum[maxn],lp=,val[maxn],vv[maxn],svv[maxn];

 struct Ques{int l,r,id; bool operator < (const Ques &b) const {return r<b.r;} }q[maxn];

 int ans[maxn];

 int WWW(LL v) {return v>?:v;}

 int main()

 {

     n=qread(); m=qread();

     bin[]=inv[]=; for (int i=;i<=n;i++)

         a[i]=qread(),bin[i]=(bin[i-]<<)%mod,inv[i]=1ll*inv[i-]*((mod+)>>)%mod,

         sum[i]=((sum[i-]+1ll*a[i]*bin[i])%mod+mod)%mod;

     for (int i=;i<=m;i++) {q[i].l=qread(); q[q[i].id=i].r=qread();}

     sort(q+,q++m);

     pos[lp=]=; int j=; val[]=a[]*; vv[]=svv[]=((a[]*)%mod+mod)%mod;

     while (j<=m && q[j].r==) ans[q[j].id]=(a[]+mod)%mod,j++;

     for (int i=;i<=n;i++)

     {

         if (a[i]<=) pos[++lp]=i,val[lp]=*a[i],vv[lp]=(a[i]*2ll%mod+mod)%mod,svv[lp]=(svv[lp-]+vv[lp])%mod;

         else

         {

             int cur=WWW(0ll+val[lp]+bin[pos[lp]-pos[lp-]+]*1ll*a[i]);

             int cvv=(vv[lp]+bin[pos[lp]-pos[lp-]+]*1ll*a[i])%mod; lp--;

             while (lp && cur>)

             {

                 cur=WWW(0ll+val[lp]+(pos[lp]-pos[lp-]>?:bin[pos[lp]-pos[lp-]])*1ll*cur);

                 cvv=(vv[lp]+bin[pos[lp]-pos[lp-]]*1ll*cvv)%mod; lp--;

             }

             val[++lp]=cur; pos[lp]=i; vv[lp]=cvv; svv[lp]=(svv[lp-]+vv[lp])%mod;

         }

         while (j<=m && q[j].r==i)

         {

             if (q[j].l==q[j].r) {ans[q[j].id]=(a[i]+mod)%mod; j++; continue;}

             int l=q[j].l+,Ans=(a[q[j].l]+mod)%mod;

             int L=,R=lp;

             while (L<R)

             {

                 int mid=(L+R)>>;

                 if (pos[mid]>=l) R=mid; else L=mid+;

             }

             Ans=(Ans+svv[lp]-svv[L])%mod; Ans=(Ans+mod)%mod;

             Ans=(Ans+(sum[pos[L]]-sum[l-]+mod)*1ll*inv[l-])%mod;

             ans[q[j].id]=Ans;

             j++;

         }

     }

     for (int i=;i<=m;i++) printf("%d\n",ans[i]);

     return ;

 }

巴特西

Codeforces878E. Numbers on the blackboard

最新文章

热门文章