#P2906. 颜色

    ID: 2013 传统题 1000ms 512MiB 尝试: 209 已通过: 51 难度: 7 上传者: 标签>CF2200提高根号分块一维前缀和增量维护时间戳避免清空数组

颜色

题目描述

给定一个长度为 nn 的颜色序列 cc,对于该序列中的任意一个元素 cic_i,都有 1≤ci≤m1\le c_i\le m。对于一种颜色 kk 来说,区间 [L,R][L,R] 内的权值定义为这种颜色在该区间中出现的次数的平方,即区间 [L,R][L,R] 内中满足 ci=kc_i=k 的元素个数的平方。接下来给出 QQ 个询问,询问区间 [L,R][L,R] 内颜色 [a,b][a,b] 的权值总和。

输入格式

  • 第 11 行三个整数 n,m,Qn,m,Q。分别代表序列长度,颜色总数和询问总数。
  • 第 22 行 nn 个整数,代表序列 cic_i。
  • 第 33 行到第 Q+2Q+2 行,每行 44 个整数 l,r,a,bl,r,a,b。记上一次计算出的答案为 LansLans。那么实际的 l,r,a,bl,r,a,b 为给出的l,r,a,bl,r,a,b xorxor 上 LansLans。第一个询问的时候 Lans=0Lans=0。

输出格式

  • 总共 QQ 行,对于每一个询问,输出权值总和。
4 2 3
1 1 2 2 
1 4 1 2
10 11 9 10
3 0 0 0
8
2
0

数据规模与约定

对于 100%100\% 的数据,1≤n,Q≤5×1041\le n,Q\le 5\times 10^4,m≤2×104m\le 2\times 10^4。