K-th Set Bit (K-րդ հաստատված բիթ)
Ձեզ տրված է
n երկարությամբ երկուական համակարգի զանգված (0-ներ և 1-եր), որի էլեմենտները համարակալված են 1-ից մինչև n: Պետք է մշակել q հարցում, ընդ որում յուրաքանչյուր հարցում կարող է լինել երկու տեսակի.- Հարցման տեսակը 1: գտնել զանգվածում 1-ի
k-րդ հանդիպման ինդեքսը.
- Հարցման տեսակը 2: փոխել զանգվածի որևէ ինդեքսի արժեքը 0-ից 1-ի (կամ հակառակը).
Գրեք ծրագիր, որը կկարողանա արդյունավետորեն պատասխանել այս հարցումներին:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n և q (զատված բացատով), որոնք սահմանում են երկուական համակարգի զանգվածի չափը և հարցումների քանակը, համապատասխանաբար:Երկրորդ տողում ներկայացված են զանգվածի
n երկուական համակարգի էլեմենտները:Հաջորդ
q տողերը պարունակում են հարցումները. յուրաքանչյուր հարցում նկարագրվում է տեսակից (1 կամ 2) և անհրաժեշտ պարամետրերից.- Եթե , ապա տրվում է մեկ ամբողջ թիվ
k(1 ≤ k ≤ n):
- Եթե , ապա տրվում են ամբողջ թիվ
p(1 ≤ p ≤ n) և արժեք ($0$ կամ $1$), որը պետք է վերագրել տվյալ ինդեքսին:
Ելք
Յուրաքանչյուր 1-ին տեսակի հարցման համար պետք է արտածել զանգվածում 1-ի
k-րդ հանդիպման ինդեքսը: Եթե այդպիսի հանդիպում գոյություն չունի, պետք է տպել -1:Օրինակներ
Մուտք | Ելք |
6 4
1 0 1 1 0 1
1 2
2 1 0
1 4
1 3 | 3
-1
6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB