Query On Arrays
All submissions for this problem are available.
Harsh loves numbers and has a huge ordered collection of numbers of size n . One day Aniket saw his collection and came up with a challenge. Aniket does 2 kinds of operations on Harsh's collection.
- Update: He changes the value of xth number to y .
- Query: He asks if there exist any suffix in his ordered collection such that its sum is exactly z .
Can you help Harsh to do these operations and answer the queries.
First line contains an integer n denoting the size of Harsh's collection.
Next line contains n integers denoting a1, a2 ... an the numbers in Harsh's collection.
Next line contains an integer q denoting the number of operations Aniket does.
Next q lines follow in following format:
- 1 x y: Change the value of xth number to y.
- 2 z: Find out if there exist any suffix with sum exactly equal to z.
- 1 ≤ n ≤ 105
- 1 ≤ ai ,y≤ 109
- 1 ≤ q ≤ 105
- 1 ≤ x ≤ n
- 1≤ z ≤ 1014
For every query operation(i.e. of kind 2), print the answer of the query. Print "YES" (without quotes) if there exists a suffix having sum equal to z, otherwise print "NO".
Input 1: 5 10 1 9 8 11 6 2 19 1 3 13 2 28 2 32 1 1 100 2 133 Output 1: YES NO YES YES
|Tags||binary-search, fenwick-tree, npl_nitw, nplq1602, segment-tree, suffix|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions