P5268 [SNOI2017]一个简单的询问

    • 178通过
    • 278提交
  • 题目提供者 memset0 管理员
  • 评测方式 云端评测
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给你一个长度为 $N$ 的序列 $a_i$,$1\leq i\leq N$,和 $q$ 组询问,每组询问读入 $l_1,r_1,l_2,r_2$,需输出

    $$ \sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\cdot \text{get}(l_2,r_2,x) $$

    $ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中,数字 $x$ 出现了多少次。

    输入输出格式

    输入格式:

    第一行,一个数字 $N$,表示序列长度。
    第二行,$N$ 个数字,表示 $a_1\sim a_N$。
    第三行,一个数字 $Q$,表示询问个数。
    第 $4\sim Q+3$ 行,每行四个数字 $l_1,r_1,l_2,r_2$,表示询问。

    输出格式:

    对于每组询问,输出一行一个数字,表示答案。

    输入输出样例

    输入样例#1: 复制
    5
    1 1 1 1 1
    2
    1 2 3 4
    1 1 4 4
    输出样例#1: 复制
    4
    1

    说明

    对于 $20\%$ 的数据,$1\leq N,Q\leq 1000$;
    对于另外 $30\%$ 的数据,$1\leq a_i\leq 50$;
    对于 $100\%$ 的数据,$N,Q\leq 50000$,$1\leq a_i\leq N$,$1\leq l_1\leq r_1\leq N$,$1\leq l_2\leq r_2\leq N$。

    数据范围与原题相同,但测试数据由 LibreOJ 自制,并非原数据。

    注意:答案有可能超过 int 的最大值。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。