codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

316E1.md (2570B)


      1 Source: https://codeforces.com/problemset/problem/316/E1
      2 
      3 E1. Summer Homework
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 By the age of three Smart Beaver mastered all arithmetic operations and got this summer homework from the amazed teacher:
     22 
     23 You are given a sequence of integers *a*1, *a*2, ..., *a**n*. Your task is to perform on it *m* consecutive operations of the following type:
     24 
     25 1. For given numbers *x**i* and *v**i* assign value *v**i* to element *a**x**i*.
     26 2. For given numbers *l**i* and *r**i* you've got to calculate sum ![](https://espresso.codeforces.com/1d7ff346cc22d72b468f0d5a8f2d7186003971d4.png), where *f*0 = *f*1 = 1 and at *i* ≥ 2: *f**i* = *f**i* - 1 + *f**i* - 2.
     27 3. For a group of three numbers *l**i* *r**i* *d**i* you should increase value *a**x* by *d**i* for all *x* (*l**i* ≤ *x* ≤ *r**i*).
     28 
     29 Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.
     30 
     31 Input
     32 
     33 The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 2·105) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains *n* integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 105). Then follow *m* lines, each describes an operation. Each line starts with an integer *t**i* (1 ≤ *t**i* ≤ 3) — the operation type:
     34 
     35 * if *t**i* = 1, then next follow two integers *x**i* *v**i* (1 ≤ *x**i* ≤ *n*, 0 ≤ *v**i* ≤ 105);
     36 * if *t**i* = 2, then next follow two integers *l**i* *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ *n*);
     37 * if *t**i* = 3, then next follow three integers *l**i* *r**i* *d**i* (1 ≤ *l**i* ≤ *r**i* ≤ *n*, 0 ≤ *d**i* ≤ 105).
     38 
     39 The input limits for scoring 30 points are (subproblem E1):
     40 
     41 * It is guaranteed that *n* does not exceed 100, *m* does not exceed 10000 and there will be no queries of the 3-rd type.
     42 
     43 The input limits for scoring 70 points are (subproblems E1+E2):
     44 
     45 * It is guaranteed that there will be queries of the 1-st and 2-nd type only.
     46 
     47 The input limits for scoring 100 points are (subproblems E1+E2+E3):
     48 
     49 * No extra limitations.
     50 
     51 Output
     52 
     53 For each query print the calculated sum modulo 1000000000 (109).
     54 
     55 Examples
     56 
     57 Input
     58 
     59 ```
     60 5 5  
     61 1 3 1 2 4  
     62 2 1 4  
     63 2 1 5  
     64 2 2 4  
     65 1 3 10  
     66 2 1 5
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 12  
     73 32  
     74 8  
     75 50
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 5 4  
     82 1 3 1 2 4  
     83 3 1 4 1  
     84 2 2 4  
     85 1 2 10  
     86 2 1 5
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 12  
     93 45
     94 ```