D. Strange Queries

Codeforces

IDCF10113D

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an array with n integers a1, a2, ..., an, and q queries to answer. Each query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) satisfying the following conditions: The first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n). The third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries. Each of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query. For each query count the number of sought pairs of indices (i, j) and print it in a separate line. ## Input The first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array.The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).The third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries.Each of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query. ## Output For each query count the number of sought pairs of indices (i, j) and print it in a separate line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the size of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ a_i \in \{1, 2, \dots, n\} $. Let $ q \in \mathbb{Z}^+ $ be the number of queries. **Constraints** 1. $ 1 \leq n \leq 50{,}000 $ 2. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq q \leq 50{,}000 $ 4. For each query $ k \in \{1, \dots, q\} $: - $ 1 \leq l_{1,k} \leq r_{1,k} \leq n $ - $ 1 \leq l_{2,k} \leq r_{2,k} \leq n $ **Objective** For each query $ k $, compute: $$ C_k = \left| \left\{ (i, j) \mid i \in [l_{1,k}, r_{1,k}],\ j \in [l_{2,k}, r_{2,k}],\ a_i = a_j \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "D. Strange Queries",
    "description": {
      "content": "You are given an array with n integers a1, a2, ..., an, and q queries to answer. Each query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) sa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10113D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array with n integers a1, a2, ..., an, and q queries to answer.\n\nEach query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) sa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\{1, 2, \\dots, n\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments