fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 5e4+5;
  7.  
  8. int n, q, a[N];
  9.  
  10. namespace Subtask1 {
  11.     int f1[1005], f2[1005];
  12.     bool check() {
  13.         return n <= 1000 && q <= 1000;
  14.     }
  15.     void solve() {
  16.         while (q--) {
  17.             int x, y, u, v; cin >> x >> y >> u >> v;
  18.             memset(f1, 0, sizeof f1); 
  19.             memset(f2, 0, sizeof f2);
  20.             for (int i = x; i <= y; i++) f1[a[i]]++;
  21.             for (int i = u; i <= v; i++) f2[a[i]]++;
  22.             ll ans = 0;
  23.             for (int i = 1; i <= n; i++) ans += 1LL * f1[i] * f2[i];
  24.             cout << ans << '\n';
  25.         }
  26.     }
  27. }
  28.  
  29. namespace Subtask2 {
  30.     int P[55][N];
  31.     bool check() {
  32.         return *max_element(a + 1, a + n + 1) <= 50;
  33.     }
  34.     int query(int x, int l, int r) {
  35.         return P[x][r] - P[x][l - 1];
  36.     }
  37.     void solve() {
  38.         for (int x = 1; x <= 50; x++)
  39.             for (int i = 1; i <= n; i++) 
  40.                 P[x][i] = P[x][i - 1] + (a[i] == x);
  41.         while (q--) {
  42.             int x, y, u, v; cin >> x >> y >> u >> v;
  43.             ll ans = 0;
  44.             for (int val = 1; val <= 50; val++) 
  45.                 ans += 1LL * query(val, x, y) * query(val, u, v);
  46.             cout << ans << '\n';
  47.         }
  48.     }
  49. }
  50.  
  51. namespace Fulltask {
  52.     int B;
  53.     struct Query {
  54.         int r1, r2, id, sign;
  55.         bool operator<(const Query& o) const {
  56.             int b1 = r1 / B, b2 = o.r1 / B;
  57.             if (b1 != b2) return b1 < b2;
  58.             return (b1 & 1) ? (r2 < o.r2) : (r2 > o.r2);
  59.         }
  60.     };
  61.     int cnt1[N], cnt2[N];
  62.     ll ans[N], cur_ans = 0;
  63.     inline void add1(int p) {
  64.         cur_ans += cnt2[a[p]];
  65.         cnt1[a[p]]++;
  66.     }
  67.     inline void remove1(int p) {
  68.         cnt1[a[p]]--;
  69.         cur_ans -= cnt2[a[p]];
  70.     }
  71.     inline void add2(int p) {
  72.         cur_ans += cnt1[a[p]];
  73.         cnt2[a[p]]++;
  74.     }
  75.     inline void remove2(int p) {
  76.         cnt2[a[p]]--;
  77.         cur_ans -= cnt1[a[p]];
  78.     }
  79.     void solve() {
  80.         vector<Query> qs;
  81.         for (int i = 0; i < q; i++) {
  82.             int x, y, u, v; cin >> x >> y >> u >> v;
  83.             qs.push_back({y, v, i, 1});
  84.             qs.push_back({y, u - 1, i, -1});
  85.             qs.push_back({x - 1, v, i, -1});
  86.             qs.push_back({x - 1, u - 1, i, 1});
  87.         }
  88.         B = max(1, (int)(n / sqrt(4 * q)));
  89.         sort(qs.begin(), qs.end());
  90.         int R1 = 0, R2 = 0;
  91.         for (int i = 0; i < (int)qs.size(); i++) {
  92.             int r1 = qs[i].r1, r2 = qs[i].r2;
  93.             while (R1 < r1) add1(++R1);
  94.             while (R1 > r1) remove1(R1--);
  95.             while (R2 < r2) add2(++R2);
  96.             while (R2 > r2) remove2(R2--);
  97.             ans[qs[i].id] += qs[i].sign * cur_ans;
  98.         }
  99.         for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  100.     }
  101. }
  102.  
  103. void solve() {
  104.     cin >> n >> q;
  105.     for (int i = 1; i <= n; i++) cin >> a[i];
  106.     if (Subtask1::check()) Subtask1::solve();
  107.     else if (Subtask2::check()) Subtask2::solve();
  108.     else Fulltask::solve();
  109. }
  110.  
  111. int main() {
  112.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  113.  
  114.     #define TASK "DAYSO"
  115.     if (fopen(TASK".INP", "r")) {
  116.         freopen(TASK".INP", "r", stdin);
  117.         freopen(TASK".OUT", "w", stdout);
  118.     }
  119.  
  120.     int tests = 1; // cin >> tests;
  121.     while (tests--) solve();
  122.  
  123.     #ifdef LOCAL
  124.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  125.     #endif
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 3
2 1 3 1 2 1
2 2 6 6
1 6 2 6
3 3 5 5
stdout
copy 
1
12
0
https://ideone.com/0zDMa8
Chọn Đội tuyển HSGQG Bắc Ninh 2025 - Dãy số
language:
C++14 (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!