Պրեֆիքս (Prefix) գումարների հարցում
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n դրական թվերից կազմված զանգված, պետք է մշակեք q հարցում: Յուրաքանչյուր հարցում կարող է պատկանել հետևյալ երկու տեսակներից որևէ մեկին.- Ստուգել, արդյոք զանգվածի որևէ նախաբաժնի գումարը հավասար է տրված
sարժեքին:
- Թարմացնել զանգվածի որևէ ինդեքսում գտնվող արժեքը:
Հարկավոր է ծրագիրը գրել այնպես, որ հարցումներին պատասխանի möglichst արդյունավետ կերպով:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n և q (1 ≤ n, q ≤ 100 000), բաժանված բացատով, որոնք ներկայացնում են զանգվածի չափը և հարցումների քանակը, համապատասխանաբար:Երկրորդ տողում տրված են
n դրական ամբողջ թվեր, որոնք հանդիսանում են զանգվածի էլեմենտները. յուրաքանչյուր էլեմենտ դրական է և չի գերազանցում -ը:Հաջորդ
q տողերում տրվում են հարցումները: Հարցման տիպը նշվում է (1 կամ 2) արժեքով, որին հաջորդում են անհրաժեշտ պարամետրերը.- Հարցման տիպ 1-ի դեպքում՝ մեկ ամբողջ թիվ
s:
- Հարցման տիպ 2-ի դեպքում՝ մեկ դիրք
pև արժեքx, որը պետք է դրվի զանգվածիp-րդ ինդեքսում:
Ելք
Յուրաքանչյուր տիպ 1 հարցման դեպքում պետք է տպել
YES, եթե գոյություն ունի prefix (նախաբաժին) զանգված, որի գումարը հավասար է s-ին, հակառակ դեպքում պետք է տպել NO:Օրինակներ
Մուտք | Ելք |
5 3
1 2 3 4 5
1 10
2 2 3
1 15 | YES
NO |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB