題面
現場題面
codeforces878E
codeforces878E
A sequence of n integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let x and y be two adjacent numbers ( x x x before y y y), then he can remove them and write x + 2 y x + 2y x + 2y instead of them. He will perform these operations until one number is left. Sasha likes big numbers and will get the biggest possible number.
Nikita wants to get to the blackboard before Sasha and erase some of the numbers. He has q q q options, in the option i i i he erases all numbers to the left of the l i l_i li-th number and all numbers to the right of r i r_i ri-th number, i. e. all numbers between the l i l_i li-th and the r i r_i ri-th, inclusive, remain on the blackboard. For each of the options he wants to know how big Sasha’s final number is going to be. This number can be very big, so output it modulo 1 0 9 + 7 10^9 + 7 109 + 7.
雙倍經驗傳送門：Luogu
題解
自己的唠叨
- 現場得分：NULL/50（他沒給我測）
- 題目已補
- 注意點：
- 會爆long long，是以對于一個塊，要記錄取模後的和以及大緻的和（就是不取模，與INF取min）
- 一定要注意不要輸出負數
- xjoi上面的資料是hapi，過了xjoi不一定能過codeforces。其中差别（就我的程式而言），在于為 0 0 0的元素的處理。值為 0 0 0的塊不要并到前面的塊上面。
現場題解
代碼
#include<bits/stdc++.h>
#define LL long long
#define MAXN 1000000
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
template<typename T>void Read(T &cn)
{
char c;int sig = 1;
while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
while(isdigit(c = getchar()))cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T>void Min(T &cn, T cm) {cn = cn > cm ? cm : cn; }
template<typename T>void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
struct xun{
int l,r,ci;
inline friend bool operator <(xun a,xun b) {return a.r < b.r; }
void getit(int cn) {Read(l); Read(r); ci = cn; }
};
struct qwe{
LL zhi,dax,chang;
void mk(int cn) {zhi = dax = cn; }
};
xun b[MAXN+1];
int ans[MAXN+1];
int n,m;
qwe a[MAXN+1];
int fa[MAXN+1];
LL qz[MAXN+1],mi[MAXN+1],nim[MAXN+1];
LL he[MAXN+1];
int get_fa(int cn) {return cn == fa[cn] ? cn : fa[cn] = get_fa(fa[cn]); }
LL ksm(LL cn,LL cm) {LL ans = 1; while(cm) ans = ans*(1+(cn-1)*(cm&1))%MOD, cn = cn*cn%MOD, cm>>=1; return ans; }
void yuchu(int cn)
{
mi[0] = 1; mi[1] = 2; nim[0] = 1; nim[1] = ksm(2,MOD-2);
for(int i = 2;i<=cn;i++) mi[i] = mi[i-1]*mi[1]%MOD, nim[i] = nim[i-1]*nim[1]%MOD;
}
void weihu_he(int cn)
{
int lin = get_fa(cn);
he[lin] = (he[get_fa(lin-1)]+a[lin].zhi*(1+(lin!=1)))%MOD;
}
LL jia(LL cn,LL cm,LL cx)
{
if(cx >= 62) return INF;
if(((INF-cn)>>cx) <= cm) return INF;
LL guo = cn + cm*(1ll<<cx);
return min(guo,INF);
}
void weihu_a(int cn)
{
a[cn].chang = 1;
if(cn == 1) return;
while(cn != 1 && a[cn].dax >= 0)
{
int lin = get_fa(cn-1);
fa[cn] = lin;
a[lin].zhi = (a[lin].zhi + a[cn].zhi * mi[a[lin].chang])%MOD;
a[lin].dax = jia(a[lin].dax,a[cn].dax,a[lin].chang);
a[lin].chang = a[lin].chang + a[cn].chang;
cn = lin;
}
}
LL suan(int cn,int cm)
{
int lin = get_fa(cn);
int lin2 = lin + a[lin].chang-1;
int lin1 = get_fa(cm);
// printf("lin = %d lin1 = %d lin2 = %d\n",lin,lin1,lin2);
return ((he[lin1] - he[lin] + (qz[lin2]-qz[cn-1]+MOD)%MOD*nim[cn-1]%MOD+MOD)%MOD+MOD)%MOD;
}
signed main()
{
// freopen("border2.in","r",stdin);
// freopen("T3.out","w",stdout);
Read(n); Read(m);
for(int i = 1;i<=n;i++) {int bx; Read(bx); a[i].mk(bx); fa[i] = i; }
for(int i = 1;i<=m;i++) b[i].getit(i);
yuchu(n); qz[0] = 0;
for(int i = 1;i<=n;i++) qz[i] = (qz[i-1] + a[i].zhi*mi[i-1])%MOD;
sort(b+1,b+m+1);
int xian = 0; he[0] = 0;
for(int i = 1;i<=n;i++)
{
weihu_a(i); weihu_he(i);
while(xian < m && b[xian+1].r == i) xian++, ans[b[xian].ci] = suan(b[xian].l,i);
}
for(int i = 1;i<=m;i++) Write(ans[i]), puts("");
return 0;
}