fork download
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
  4. #define pii pair<int, int>
  5. #define f first
  6. #define s second
  7. #define ep emplace_back
  8. #define all(x) x.begin(), x.end()
  9. using namespace std;
  10.  
  11. const int maxn = 1e5 + 10;
  12. const int LOG = log2(maxn)+2;
  13. int a[maxn];
  14. struct PST_node{
  15. int l,r,sum;
  16. };
  17. PST_node T[maxn*LOG];
  18. int cnt = 0;
  19. int n,q;
  20.  
  21.  
  22. int ROOT[maxn];
  23.  
  24. void push_up(int nod){
  25. T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum;
  26. }
  27.  
  28. void update(int& nod, int prev_nod, int l, int r, int pos, int val){
  29. nod = ++cnt;
  30. T[nod] = T[prev_nod];
  31. if (l == r){
  32. T[nod].sum += val;
  33. return;
  34. }
  35. int mid = (l+r) >> 1;
  36. if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val);
  37. else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val);
  38. push_up(nod);
  39. }
  40.  
  41. int query(int nod, int l, int r, int u, int v){
  42. if (u > v) return 0;
  43. if (l > v || r < u) return 0;
  44. if (l >= u && r <= v) return T[nod].sum;
  45. int mid = (l+r) >> 1;
  46. int L = query(T[nod].l, l, mid, u, v);
  47. int R = query(T[nod].r, mid+1, r, u, v);
  48. return L+R;
  49. }
  50.  
  51. vector<int> V;
  52.  
  53. signed main(){
  54. ios_base::sync_with_stdio(false);
  55. cin.tie(0);
  56. #define Task "A"
  57. if (fopen(Task".inp", "r")){
  58. freopen(Task".inp", "r", stdin);
  59. freopen(Task".out", "w", stdout);
  60. }
  61.  
  62. cin >> n;
  63. up(i,1,n){
  64. cin >> a[i];
  65. V.push_back(a[i]);
  66. }
  67.  
  68. sort(all(V));
  69. V.resize(unique(all(V)) - V.begin());
  70. up(i,1,n) a[i] = lower_bound(all(V), a[i]) - V.begin() + 1;
  71.  
  72. up(i,1,n) update(ROOT[i], ROOT[i-1], 1, n, a[i], 1);
  73. V.insert(V.begin(), -1e9 - 7);
  74.  
  75. cin >> q;
  76. up(i,1,q){
  77. int l,r,x,y;
  78. cin >> l >> r >> x >> y;
  79.  
  80. x = lower_bound(all(V), x) - V.begin();
  81. y = upper_bound(all(V), y) - V.begin() - 1;
  82.  
  83. int R = query(ROOT[r], 1, n, x, y);
  84. int L = query(ROOT[l-1], 1, n, x, y);
  85. cout << R - L << "\n";
  86. }
  87. }
  88.  
Success #stdin #stdout 0.01s 5676KB
stdin
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
stdout
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