Միջակայքի XOR հարցումներ
Ձեզ տրված է
n էլեմենտից բաղկացած զանգված և q հարցում: Հարցումները երկու տեսակ են.- Միջակայքի բացառող կամ (XOR) արժեքի հաշվում
- Զանգվածի արժեքի փոփոխում որոշակի դիրքում
Ձեր խնդիրը հարցումները արդյունավետ կերպով մշակելն է:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n և q (1 ≤ n, q ≤ 100000), որոնք ներկայացնում են զանգվածի էլեմենտների քանակը և հարցումների քանակը:Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր (), որոնք հանդիսանում են զանգվածի նախնական արժեքները:Հաջորդ
q տողերից յուրաքանչյուրն ներկայացնում է մեկ հարցում.- Միջակայքի XOR հարցման համար: Տողը սկսվում է
1թվով, որին հաջորդում են և (1 ≤ li ≤ ri ≤ n) թվերը, որոնք սահմանում են այն ինդեքսների միջակայքը[], որի համար անհրաժեշտ է հաշվել XOR արժեքը:
- Զանգվածի նորացման հարցման համար: Տողը սկսվում է
2թվով, որին հաջորդում են և (1 ≤ pi ≤ n, 0 ≤ xi < 2^{30}), որոնք սահմանում են դիրքում գտնվող էլեմենտը և նրա նոր արժեքը:
Ելք
Վերոհիշյալ XOR հարցումներից յուրաքանչյուրի համար անհրաժեշտ է տպել համապատասխան միջակայքի էլեմենտների XOR արժեքը առանձին տողում:
Օրինակներ
Մուտք | Ելք |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 7
9
3 |
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 1 MB