Դավիթը և եռահատվածները
Դավիթը շատ էր սիրում հատվածներ, և մի պայծառ օր նա մտածեց, թե ինչու չի կարելի ուղղակի 3 հատված իրար կպցնել։ Հենց այդպես էլ առաջացավ եռահատվածի գաղափարը։
Այլ կերպ ասած, եռահատվածը
([a,b], [b,c], [c,d]) հատվածների եռյակ է։Դավիթին շատ դուր եկավ եռահատվածների գաղափարը ու նա որոշեց տանը n եռահատված աճեցնել։ Ոստիկանությունը, իմանալով դրա մասին, հաջորդ օրը թակեց իրենց տան դուռը ու սկսեց հարցեր տալ Դավիթին: Ոստիկանության բոլոր հարցերը կարելի է նկարագրել երկու
l, r թվերով, որոնց համար Դավիթը պետք է ասի այն եռահատվածների քանակը, որոնց գոնե մի հատվածը ամբողջովին ընկած է [l,r] միջակայքում։Դավիթը ամբողջ օրը անցկացրել էր եռահատվածներ մշակելով ու փորձարկելով և, հոգնածության պատճառով, ձեզ է խնդրում պատասխանել տրված հարցերին։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված են
1 ≤ n,q ≤n տողերում տրված են, հերթական եռահատվածի համար q տողերերից iրդը պարունակում է ansը նախորդ հարցի պատասխանը (առաջին հարցի համար ans=0), դուք պետք է հերթական հարցի համար վերցնեք Ելքային տվյալներ
Պետք է արտածել
q թիվ՝ տրված հարցերի պատասխանները:Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (13 միավոր)
1 ≤ n,q ≤ 5000
- Ենթախնդիր 2 (11 միավոր)
- Ենթախնդիր 3 (14 միավոր)
և
- Ենթախնդիր 4 (21 միավոր)
- Ենթախնդիր 5 (41 միավոր) լրացուցիչ սահմանափակումներ չկան։
Օրինակ
Մուտք | Ելք |
3 5
1 3 5 10
6 8 13 15
1 10 12 14
5 10
3 10
7 10
0 13
5 4 | 2
2
1
3
0 |
Բացատրություն
Առաջին օրինակի բացատրությունը`
- Առաջին հարցում
l=5ևr=10։ Քանի որ առաջին եռահատվածի երրորդ և երկրորդ եռահատվածի առաջին հատվածները ամբողջովին ընկած են այդ հատվածի մեջ, հարցի պատասխանը 2 է։
- Երկրորդ հարցում
l=1ևr=8։ Քանի որ առաջին եռահատվածի առաջին հատվածը, և երկրորդ եռահատվածի առաջին հատվածը ամբողջովին ընկած են այդ հատվածի մեջ, հարցի պատասխանը նույնպես 2 է։
- Երրորդ հարցում
l=5ևr=8։ Քանի որ միայն երկրորդ եռահատվածը ունի հատված ամբողջովին ընկած այդ միջակայքում, պատասխանը 1 է։
- Չորորդ հարցում
l=1ևr=12։ Բոլոր երեք եռահատվածները ունեն գոնե մի հատված ընկած այդ հատվածում։
- Առաջին հարցումում
l=6ևr=7։ Ոչ մի եռահատված չունի հատված ամբողջովին ընկած այդ հատվածում։
*c++ լեզվում «բիթային բացառող կամ» գործողությունը կարող եք կատարել
^ օպերատորով։Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 5.2 seconds
Memory limit: 512 MB
Output limit: 1 MB