fork download
copy 
  1. from collections import deque
  2. class node:
  3.     def __init__(self):
  4.         self.arr = deque([0,0,0])
  5.  
  6. def buildTree(si,ss,se):
  7.     if ss == se:
  8.         segmentTree[si].arr[0]=1
  9.         segmentTree[si].arr[1]=0
  10.         segmentTree[si].arr[2]=0
  11.         return
  12.     mid = (ss+se)//2
  13.     buildTree(2*si,ss,mid)
  14.     buildTree(2*si+1,mid+1,se)
  15.  
  16.     segmentTree[si].arr[0] = segmentTree[2*si].arr[0] + segmentTree[2*si+1].arr[0]
  17.     segmentTree[si].arr[1] = segmentTree[2*si].arr[1] + segmentTree[2*si+1].arr[1]
  18.     segmentTree[si].arr[2] = segmentTree[2*si].arr[2] + segmentTree[2*si+1].arr[2]
  19.     return
  20.  
  21. def query(si,ss,se,qs,qe):
  22.     if lazy[si]!=0:
  23.         dx = lazy[si]
  24.         lazy[si]=0
  25.         segmentTree[si].arr.rotate(dx)
  26.         if ss!=se:
  27.             lazy[2*si]+=1
  28.             lazy[2*si+1]+=1
  29.  
  30.     if qe<ss or qs>se:
  31.         return 0
  32.     if ss>=qs and se<=qe:
  33.         return segmentTree[si].arr[0]
  34.     mid = (ss+se)//2
  35.     l = query(2*si,ss,mid,qs,qe)
  36.     r = query(2*si+1,mid+1,se,qs,qe)
  37.     return l+r
  38.  
  39. def update(si,ss,se,qs,qe):
  40.     if lazy[si]!=0:
  41.         dx = lazy[si]
  42.         lazy[si]=0
  43.         segmentTree[si].arr.rotate(dx)
  44.         if ss!=se:
  45.             lazy[2*si]+=dx
  46.             lazy[2*si+1]+=dx
  47.         return
  48.     if qe<ss or se<qs:
  49.         return
  50.     if ss>=qs and se<=qe:
  51.         segmentTree[si].arr.rotate()
  52.         if ss!=se:
  53.             lazy[2*si]+=1
  54.             lazy[2*si+1]+=1
  55.         return
  56.     mid = (ss+se)//2
  57.     update(2*si,ss,mid,qs,qe)
  58.     update(2*si+1,mid+1,se,qs,qe)
  59.  
  60.     segmentTree[si].arr[0] = segmentTree[2*si].arr[0]+segmentTree[2*si+1].arr[0]
  61.     segmentTree[si].arr[1] = segmentTree[2*si].arr[1]+segmentTree[2*si+1].arr[1]
  62.     segmentTree[si].arr[2] = segmentTree[2*si].arr[2]+segmentTree[2*si+1].arr[2]
  63.     return
  64.  
  65.  
  66. n,tc = map(int,input().split())
  67. segmentTree = [node() for _ in range(4*n)]
  68. lazy = [0]*(4*n)
  69. buildTree(1,0,n-1)
  70.  
  71. for _ in range(tc):
  72.     q,L,R = map(int,input().split())
  73.     if q==0:
  74.         update(1,0,n-1,L,R)
  75.     else:
  76.         print(query(1,0,n-1,L,R))
  77.  
Success #stdin #stdout 0.02s 9456KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/w7pck3
language:
Python 3 nbc (python 3.7.3)
created:
5 years ago
visibility:
secret

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!