fork download
copy 
  1. def solve():
  2.     import sys
  3.     sys.setrecursionlimit(10**6)
  4.     I=sys.stdin.readline
  5.     MOD=10**9+7
  6.     n=int(I())
  7.     arr=list(map(int,I().split()))
  8.     q=int(I())
  9.     size=1
  10.     while size<n: size*=2
  11.     t=[0]*(size*2)
  12.     p=[1]*(size*2)
  13.     d=[0]*(size*2)
  14.     a=[-1]*(size*2)
  15.     for i in range(n):
  16.         t[size+i]=arr[i] % MOD
  17.     for i in range(size-1,0,-1):
  18.         t[i]=(t[i*2]+t[i*2+1]) % MOD
  19.     def ps(i, s, e):
  20.         if i>=size: return
  21.         m=(s+e)//2
  22.         L=i*2; R=i*2+1
  23.         if a[i]!=-1:
  24.             a[L]=a[i]
  25.             a[R]=a[i]
  26.             p[L]=1; p[R]=1
  27.             d[L]=0; d[R]=0
  28.             t[L]=a[i]* (m-s+1) % MOD
  29.             t[R]=a[i]* (e-m) % MOD
  30.             a[i]=-1
  31.         if p[i]!=1:
  32.             if a[L]!=-1:
  33.                 a[L]= a[L]*p[i] % MOD
  34.             else:
  35.                 p[L]= p[L]*p[i] % MOD
  36.                 d[L]= d[L]*p[i] % MOD
  37.             t[L]= t[L]*p[i] % MOD
  38.             if a[R]!=-1:
  39.                 a[R]= a[R]*p[i] % MOD
  40.             else:
  41.                 p[R]= p[R]*p[i] % MOD
  42.                 d[R]= d[R]*p[i] % MOD
  43.             t[R]= t[R]*p[i] % MOD
  44.             p[i]=1
  45.         if d[i]!=0:
  46.             if a[L]!=-1:
  47.                 a[L]=(a[L]+d[i]) % MOD
  48.             else:
  49.                 d[L]=(d[L]+d[i]) % MOD
  50.             t[L]=(t[L]+ d[i]*(m-s+1)) % MOD
  51.             if a[R]!=-1:
  52.                 a[R]=(a[R]+d[i]) % MOD
  53.             else:
  54.                 d[R]=(d[R]+d[i]) % MOD
  55.             t[R]=(t[R]+ d[i]*(e-m)) % MOD
  56.             d[i]=0
  57.     def upd1(i, s, e, l, r, v):
  58.         if l<=s and e<=r:
  59.             t[i]=(t[i]+ v*(e-s+1)) % MOD
  60.             if a[i]!=-1:
  61.                 a[i]=(a[i]+ v) % MOD
  62.             else:
  63.                 d[i]=(d[i]+ v) % MOD
  64.             return
  65.         ps(i,s,e)
  66.         m=(s+e)//2
  67.         if l<=m: upd1(i*2, s, m, l, r, v)
  68.         if r>m: upd1(i*2+1, m+1, e, l, r, v)
  69.         t[i]=(t[i*2]+t[i*2+1]) % MOD
  70.     def upd2(i, s, e, l, r, v):
  71.         if l<=s and e<=r:
  72.             t[i]= t[i]*v % MOD
  73.             if a[i]!=-1:
  74.                 a[i]= a[i]*v % MOD
  75.             else:
  76.                 p[i]= p[i]*v % MOD
  77.                 d[i]= d[i]*v % MOD
  78.             return
  79.         ps(i,s,e)
  80.         m=(s+e)//2
  81.         if l<=m: upd2(i*2, s, m, l, r, v)
  82.         if r>m: upd2(i*2+1, m+1, e, l, r, v)
  83.         t[i]=(t[i*2]+t[i*2+1]) % MOD
  84.     def upd3(i, s, e, l, r, v):
  85.         if l<=s and e<=r:
  86.             t[i]= v*(e-s+1) % MOD
  87.             a[i]= v
  88.             p[i]=1
  89.             d[i]=0
  90.             return
  91.         ps(i,s,e)
  92.         m=(s+e)//2
  93.         if l<=m: upd3(i*2, s, m, l, r, v)
  94.         if r>m: upd3(i*2+1, m+1, e, l, r, v)
  95.         t[i]=(t[i*2]+t[i*2+1]) % MOD
  96.     def qry(i, s, e, l, r):
  97.         if l<=s and e<=r:
  98.             return t[i]
  99.         ps(i,s,e)
  100.         m=(s+e)//2
  101.         res=0
  102.         if l<=m: res=(res+qry(i*2, s, m, l, r)) % MOD
  103.         if r>m: res=(res+qry(i*2+1, m+1, e, l, r)) % MOD
  104.         return res
  105.     out=[]
  106.     for _ in range(q):
  107.         tmp=list(map(int,I().split()))
  108.         if tmp[0]==1:
  109.             _,x,y,v=tmp
  110.             upd1(1,1,size,x,y,v)
  111.         elif tmp[0]==2:
  112.             _,x,y,v=tmp
  113.             upd2(1,1,size,x,y,v)
  114.         elif tmp[0]==3:
  115.             _,x,y,v=tmp
  116.             upd3(1,1,size,x,y,v)
  117.         else:
  118.             _,x,y=tmp
  119.             out.append(str(qry(1,1,size,x,y)))
  120.     sys.stdout.write("\n".join(out))
  121. if __name__=="__main__":
  122.     solve()
  123.  
Success #stdin #stdout 0.07s 14036KB
comments (?)
stdin
copy 
4
1 2 3 4
4
4 1 4
1 1 3 10
2 2 4 2
4 1 4
stdout
copy 
10
69
https://ideone.com/9Tg1MW
language:
Python 3 (python  3.12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!