#include <bits/stdc++.h> #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++) #define down(i,a,b) for (int i = (int)a; i >= (int)b; i--) #define pii pair<int, int> #define f first #define s second #define ep emplace_back #define all(x) x.begin(), x.end() using namespace std; const int maxn = 1e5 + 10; const int LOG = log2(maxn)+2; int a[maxn]; struct PST_node{ int l,r,sum; }; PST_node T[maxn*LOG]; int cnt = 0; int n,q; int ROOT[maxn]; void push_up(int nod){ T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum; } void update(int& nod, int prev_nod, int l, int r, int pos, int val){ nod = ++cnt; T[nod] = T[prev_nod]; if (l == r){ T[nod].sum += val; return; } int mid = (l+r) >> 1; if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val); else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val); push_up(nod); } int query(int nod, int l, int r, int u, int v){ if (u > v) return 0; if (l > v || r < u) return 0; if (l >= u && r <= v) return T[nod].sum; int mid = (l+r) >> 1; int L = query(T[nod].l, l, mid, u, v); int R = query(T[nod].r, mid+1, r, u, v); return L+R; } vector<int> V; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); #define Task "A" if (fopen(Task".inp", "r")){ freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n; up(i,1,n){ cin >> a[i]; V.push_back(a[i]); } sort(all(V)); V.resize(unique(all(V)) - V.begin()); up(i,1,n) a[i] = lower_bound(all(V), a[i]) - V.begin() + 1; up(i,1,n) update(ROOT[i], ROOT[i-1], 1, n, a[i], 1); V.insert(V.begin(), -1e9 - 7); cin >> q; up(i,1,q){ int l,r,x,y; cin >> l >> r >> x >> y; x = lower_bound(all(V), x) - V.begin(); y = upper_bound(all(V), y) - V.begin() - 1; int R = query(ROOT[r], 1, n, x, y); int L = query(ROOT[l-1], 1, n, x, y); cout << R - L << "\n"; } }
500 330815 377416 186066 81576 306424 356770 260844 424689 43781 287669 135595 95147 18987 141653 49134 417881 452472 106768 112126 288675 15433 181907 320278 179277 404297 184909 216520 337920 406427 228221 306218 257163 372062 312709 121612 234097 301577 179254 360027 141350 413331 266147 348899 310298 74905 168940 89244 229425 347159 216836 1024 224863 98327 232285 165961 206778 399398 361416 335257 233151 54508 105529 174426 385886 252629 13794 266351 352176 150907 190417 492298 77244 401766 183304 144706 200488 133159 497244 291285 394713 17706 186438 220557 171294 344276 403121 6092 350948 136877 53216 229647 339844 370837 38247 486596 253182 457058 47646 292381 231155 335258 289289 31181 59406 48895 256312 297179 104262 441359 168596 22377 134057 348777 396612 267181 133151 346413 234730 63371 457860 62488 142819 169123 233237 390490 16245 455858 485545 461177 275078 444455 451746 489147 27383 275825 64360 96926 26400 247426 134414 113188 442847 154763 460716 213246 465294 458000 450999 183005 116412 220164 233780 79041 422686 397610 148517 231581 405517 227078 385901 297486 297739 217569 14766 256018 340167 334980 113635 422743 431137 210295 326457 299869 382512 24171 313874 207180 199971 360777 234235 337173 359258 268629 249476 189130 274871 10637 303347 232832 228060 272818 438376 170192 164948 65002 336889 430093 352499 364536 291304 13934 385792 292536 441728 342853 34590 129237 111648 478632 173138 115648 9266 176406 305454 319906 351810 153538 327424 16221 16013 173296 167316 201982 246084 241434 117236 477075 152524 321649 118887 152129 64102 75357 393365 68637 161555 11333 431156 419390 342251 209209 142370 221870 323915 310231 244156 497673 184028 259672 341462 6379 88238 355049 440047 370682 307462 4031 418852 108977 44945 497826 499680 75235 494430 474485 323413 349641 296253 355076 355396 192221 386995 48627 75568 218969 496006 417639 393348 230096 428975 478622 199622 274857 212429 335024 303804 227505 326524 383628 439408 153859 196708 424173 465931 98498 267314 69713 439541 260697 60082 400108 182651 488070 1445 174532 394740 382329 169592 271539 385316 18166 383094 404459 106378 256205 328644 239110 389962 202766 494365 428776 62967 155937 111385 137822 331478 422311 164262 353861 50745 312401 193714 114630 307256 125052 400618 158741 126418 8345 334744 89870 96075 366200 239519 475740 43033 351392 478099 304917 483346 269093 67248 230234 331506 181000 147871 136366 435755 244136 5126 172819 239508 107047 178523 336620 163784 286212 17007 157397 357271 320396 64199 259627 330198 46790 130305 48183 225647 306533 71251 485589 471312 435886 269722 263311 133256 407420 109021 416701 488780 292891 479355 288874 157031 171142 440802 62456 481518 141163 86878 360521 170203 192916 412075 119335 286465 250631 152932 101113 122828 63249 444302 233115 212056 310826 63131 234908 284364 241441 35828 40592 494617 387127 170659 26925 368289 147059 271864 471039 354140 430734 316002 421088 386199 444188 177789 26918 243967 245590 485038 384837 465686 204141 313368 312779 367374 234422 391754 75563 320849 325274 480265 260968 346548 325358 287674 293772 495372 199776 20284 185865 158728 420311 186941 199949 49187 495962 378025 318947 404245 366104 6238 72003 214205 183506 102988 310238 367736 261036 212953 425742 189622 402705 308924 461947 385709 105765 191031 176631 23023 105254 454814 397395 67913 473989 474327 411614 303550 483565 163222 500 161 353 156 434 160 464 314 359 213 472 443 451 465 491 339 339 315 379 307 387 369 467 30632 112646 482 483 421 453 136 285 244 478 249 412 444 482 488 493 118 481 353 397 167 479 412 462 261 404 57 263 454 455 332 374 366 434 92 155 494 496 97 347 165 489 392 448 311518 411352 13 431 75627 255753 302 426 124 180 75 362 157 370 393 453 197527 213115 66 146 37488 247965 52 224 465 475 372 407 434498 459373 417 478 58 100 403 475 65 328 149 376 297 336 165 425 145 225 106 160 277013 390753 24 187 388782 427314 192 258 30747 89751 422 459 323 390 118 338 335 497 249 470 306 399 340 498 197786 315606 51 363 113 310 436 457 104512 359217 288 433 362263 439876 155 369 443 468 131 431 140410 336734 410 491 298 381 471 474 176 395 374 437 482 485 90 296 305778 416905 256 291 217 459 342 361 281556 370669 7 498 168529 349092 453 498 54367 354131 117 252 411 449 261 321 293 421 451 457 82 222 360 360 386 414 445 482 395 465 117 421 384291 384440 393 468 447701 476340 298 474 154890 436646 93 306 342490 393653 294 333 231772 447344 238 311 430001 441343 482 494 287859 411196 406 438 445 490 18 160 26 257 481 482 496805 499407 114 182 360 423 226 349 302 324 456 466 74051 239962 70 351 345 419 342 451 331971 375383 109 325 421 483 273 402 83 473 245 263 129443 386002 133 163 205 234 273 419 267 389 264 326 245 376 363 448 145038 248095 310 368 37 343 57 362 123307 340760 307 468 153 354 452 454 207 390 50 218 366 492 341 464 442 496 132 226 226000 482582 409 491 426683 466988 55 78 295 334 125 375 422 433 144 188 159968 410845 143 162 272754 288031 21 468 347 390 112 435 27094 448295 113 392 164818 251797 485 488 376 451 64 395 380 495 10 481 376 402 258 482 330 396 41 112 454 493 142 316 12 275 400 492 202 314 148 436 444 463 83 96 237408 381922 1 478 276714 486907 251 372 441492 456083 28 428 500 500 302 399 215 225 379 453 445295 463285 162 490 379 388 125 138 50216 317934 365 486 383930 486833 458 479 384 384 192 202 281 463 67 197 328265 493792 142 366 50870 233891 146 336 432 465 341 362 451007 457223 176 487 285209 387728 356 439 93350 276226 437 472 14 371 50 151 103 160 36 50 19004 282752 300 439 231 242 284 426 203 239 11 132 60 448 306 481 151 162 383 431 309 313 463 479 344314 425385 18 401 438 447 271 457 270 388 440 456 391894 396420 486 488 224 458 302 443 33767 386954 67 235 396737 425660 439 476 371681 438706 115 270 131301 166495 373 462 249991 261550 300 316 34158 281879 375 447 18 21 117 389 94 232 176 451 259 450 237 456 473 487 484 497 131874 494391 478 485 308558 474578 240 360 310 399 476 478 382873 445962 157 481 436953 482094 414 498 21 82 250 294 267351 327028 128 271 329 489 155 404 73 206 51 134 15 58 5 367 174284 444605 456 481 144 216 39 52 365 404 393 479 148715 335017 487 498 479 500 221 396 26 346 133 235 42 72 442 500 378 427 33 353 282064 481112 435 446 103921 135638 303 384 378436 467196 164 272 448 465 64 307 319 469 158 448 478072 484435 210 435 180035 463178 41 147 128622 390813 461 475 396 472 344 457 176 499 33 477 474092 478339 47 492 326145 359825 440 441 115991 186517 75 418 11280 348378 58 423 179804 222548 445 497 388 488 321 323 205 319 395 459 432 495 200 303 397 406 6 111 201284 439647 40 185 157 294 439 469 449 479 80 363 120 130 210 247 248784 375168 63 342 313 352 86 300 28 458 26 382 412 431 224 294 274432 340616 43 199 299 375 294 461 264750 350975 494 498 140515 262636 348 392 298887 378142 336 406 496751 497017 361 366 462847 487038 432 492 214084 247913 412 436 403 430 344 496 8689 54063 255 292 199203 462822 421 466 404 435 231 263 493228 494000 196 418 50 306 157 452 30967 396350 153 390 266235 321152 1 413 144507 233039 237 498 396 492 446 483 231056 259032 286 410 402 403 167 294 307707 470706 455 460 111757 406661 334 388 302304 409444 89 258 345 395 237 292 54052 329765 162 296 493 499 23 177 256389 390392 112 339 341 398 349 398 26149 147644 365 418 182448 203095 457 491 174796 239034 153 369 389870 455574 197 237 126 328 190 244 457276 460489 251 473 59159 115632 263 290 202 320 293 393 326478 346393 229 282 239396 410020 391 489 445625 474237 195 438 246 444 425 478 112910 405570 199 484 418435 472564 500 500 423 442 74 225 31770 496723 267 359 276 497 364 402 396 468 372 465 233 431 322 456 212620 421749 279 358 95247 468081 471 485 51 412 420 453 198 342 93 477 381409 476769 404 473 112 481 284 498 318 446 279 352 458 477 421 439 118993 322942 285 487 391656 428338 274 459 96 335 54 192 354296 448708 114 474 172 223 268 401 169993 394689 193 438 60308 391771 293 434 398329 464800 393 432 288 347 287 415 153785 325230 315 376 98 440 20 480 209320 374007 85 175 304421 361234 442 452 278522 298669 28 59 40 105 349 361 65973 397582 143 149 340005 476928 477 478 117 242 55 65 36184 87665 244 347 364979 379392 389 488 93 378 39 58 51884 353229 391 445 241 345 211 263 310 382 239 494 254 446 290 367 407 477 404 442 420558 471839 222 382 80816 472881 451 487 175449 186042 354 418 168 428 432 449 444 467 298 435 133417 370553 489 498 340261 455529 441 499 66 381 284 294 109 291 375 402 294533 406943 454 464 22082 436128 319 375 280512 307576 176 274 314243 394877 465 471 238180 486405 470 485 344406 356256 115 234 137112 194282 198 366 417 460 443 472 466441 499254 446 488 56 424 330 494 230878 303619 450 499 439223 440958 211 419 45 418 345 453 330 403 159 187 366 396 48 282 365844 429623 38 324 315 473 248 349 362913 398189 475 500 401 481 488 499 272394 272721 63 125 70 405 124 352 130 462 391 468 158963 225585 334 434 500 500 377 436 314863 404315 375 398 428 437 113 462 76 402 156 280 171 327 31 258 137 499 77 260 53653 99518 333 469 425644 464368 497 499 184 226 150 495 222740 363047 30 107 94315 427601 12 273 140 366 64 173 295 386 4 489 289503 362024 18 93 323 370 79 343 357 431 253 427 450 490 218 330 364194 402459 317 446 303 375 224 291 412 449 117 172 197 294 250 405 382 431 317 475 431 461 302 306 50231 258195 357 444 328 332 81 224 304758 438891 402 440 42 357 146 316 498 500 355 410 208 480 442 448 85 261 277 323 108256 222737 10 144 183 474 165 182 71 454 362 413 299977 318163 91 422 288056 407574 147 231 372949 437764 35 208 133 360 263 483 497593 497762 65 368 322 375 5 337 467 495 5 450 445 495 320 362 291826 428852 139 363 90012 370930 191 270 45 427 129 205 318 350 183 282 222362 458766 140 407 482392 494175 196 386 240 294 499 499 484 486 102 211 359965 485052 107 123 413029 439886 288 474 53183 229900 310 320 12852 29666 119 146 9925 57393 435 489 383040 471011 141 497 129 425 165 332 73471 443674 20 424 317 462 355 490 84 482 137 489 487 491 33 484 296877 443225 111 419 265 274 490 492 218 336 475 499 357 458 142 374 104 179 198 301 309845 324389 393 402 483 490 252 365 158 357 82 366 212062 424452 178 297 35 406 339 417 206539 400677 346 466 237880 323246 123 160 302 347 361 459 165488 339853 292 333 113 139 346 444 496043 499870 74 106 338 385 27 327 332207 447504 239 468 292478 308905 356 447 157 418 220 230 25649 142835 18 74 59 441 363 497 394 404 297 313 92 180 318 407 444019 497830 419 422 465 490 196 350 142279 435387 456 471 341171 351403 316 443 260804 373359 401 457 42 142 63 426 312 332 490 499 221 325 447 498 130 351 276 383 305 434 48 221 487 488 119 437 191 469 194 251 354 354 196 467 444100 485609 13 482 356 494 375 423 255 452 311 365 41599 228711 177 483 151 398 75 114 375 379 352 373 221312 430809 201 310 428 447 156 276 101642 103637 213 277 440 482 20 499 404399 437207 394 403 368233 458299 232 346 195286 369733 30 199 241 289 51 354 476048 484151 438 500 392589 451399 127 195 333 484 309 365 35321 71062 99 492 461602 479920 316 491 4 81 345 448 84 409 235 338 34 348 33 483 212217 425584 220 264 288847 306495 83 468 96 103 174 487 226052 392427 15 43 22631 349754 440 480 82 90 103 490 85 197 421 423 51035 199786 425 444 274 348 42 92 82 253 73 434 277 366 354 391 295 493 450 490 313565 427551 165 407 21 277 71 372 396998 457551 147 341 93121 487877 134 327 52 344 280 403 498 498 35 457 202337 456243 180 231 11 359 10 251 155049 182616 119 319 425064 444442 233 460 144 424 204 213 37921 307685 435 499 25 357 497 500 474699 498650 170 174 492551 498767 249 497 450 464 343 436 287 406 318 381 188754 472531 490 496 156 168 95 365 326674 460504 279 481 161 213 480 490 251 253 189 320 184 408 136 327 208 332 82 309 433 488 124 465 131026 313043 314 360 43 406 244 310 456 462 126 210 338140 421741 74 338 45310 237033 36 120 40268 294373 346 366 294 480 403 431 289 388 308 451 88646 341499 220 500 493559 496298 429 439 219 259 327 342 186247 312869 214 459 83 410 109 495 305418 316445 2 140 293105 366976 244 246 79 272 236 405 396528 464267 196 335 320 493 140 235 413206 482299 194 366 326 339 321 400 374 391 5 71 392325 459043 291 484 126712 290059 391 450 60 453 421 486 289493 431801 57 373 276021 402771 17 170 93724 492288 233 425 28887 486178 190 343 152280 273483 165 287 254 352 9 240 201808 452613 286 419 275 415 264 420 147872 478409 285 317 451777 483836 271 465 161 441 273 283 215384 338884 83 94 63 104 326 412 391985 480161 202 484 405 483 150 432 122 493 256 429 216 225 177 210 414 467 331 460 389 492 231 438 286245 349621 165 450 354 426 51 68 321 500 329 347 395370 442199 80 492 258 409
0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 11 155 0 0 2 35 0 2 0 0 0 0 5 13 6 0 0 0 40 0 14 24 0 131 0 0 0 44 0 4 203 26 0 0 0 0 0 0 2 109 22 19 4 4 0 0 0 0 0 5 0 8 0 0 8 0 0 0 20 0 143 0 0 0 0 54 5 0 0 31 0 0 274 53 0 0 0 0 0 0 0 0 5 199 0 0 0 0 0 4 27 0 0 44 83 0 0 80 36 0 0 9 0 0 0 0 0 5 0 0 0 0 104 6 5 11 3 7 0 0 0 0 10 5 0 0 21 0 6 0 0 0 213 0 0 40 0 0 0 0 128 0 11 0 0 6 121 59 0 0 4 38 0 237 28 0 0 0 0 54 0 0 0 8 0 0 0 10 0 31 0 7 0 0 4 0 11 23 0 0 0 224 27 84 0 1 0 46 4 13 0 26 0 40 0 11 1 10 27 0 0 25 0 6 18 3 0 36 24 0 137 0 0 0 59 64 0 0 70 0 0 0 7 15 0 22 0 62 171 16 0 47 0 175 9 0 0 10 4 0 1 2 0 15 0 0 0 0 6 122 2 0 0 68 3 0 0 2 9 3 23 4 0 15 0 3 0 24 0 0 0 0 23 0 10 0 0 0 0 11 0 6 0 0 0 0 11 6 0 111 60 0 0 87 0 0 0 11 0 0 0 0 0 2 0 35 0 0 0 0 9 0 0 1 84 9 0 0 0 0 0 12 138 0 0 48 4 0 0 27 0 63 1 3 10 0 135 0 0 0 145 0 0 0 0 5 0 0 130 0 29 27 0 42 0 0 0 78 8 0 2 0 0 0 9 0 97 0 29 0 0 0 0 0 0 0 0 18 0 0 23 0 0 9 0 0 0 26 1 39 0 5 6 0 4 13 0 0 0 210 0 0 121 21 0 0 0 0 0 0 0 13 0 32 159 0 0 226 0 16 10 0 5 0 1 0 0 0 29 0 76 0 0 0 0 0 134 0 0 11 103 49 0 0 81 6 0 3 0 13 21 0 20 0 13 0 0 7 69 0 28 86 128 175 40 0 123 0 106 1 0 3 0 13 0 0 0 0 0 26 0 0 1 0