[文章目录]
Description
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。n,m,k<=50000
潜心研究一发莫队。
首先，针对于区间的题目，并且是我们能通过[l,r]计算出[l-1,r]和[l+1,r]，[l,r+1]，[l,r-1]的题目。假如我们暴力的话，直接双指针跑啊，从上一个询问的[l1,r1]，跑到[l2,r2]，时间复杂度O()
【f(n)为由一个区间计算另一个区间的时间复杂度】，而莫队就是先将询问离线排个序，使得每次询问的出入不是那么大而降低复杂度。@ 一篇好博客
莫队的策略：
先按左端点分块，(1~√n)第一块，（√n~2√n）第二块...，使得每个块里左节点最大可移动幅度不超过√n。代码实现上直接左端点除以√n得出的值+1就是所在块的编号。然后每个块分别求解，每个块按照右端点排序，保证右端点的移动是递增的，所以每个块内右端点移动的复杂度是O(n)的，总共有√n块，所以时间O()，然后每个块内的左端点最大幅度也是√n，所以每个询问都是√n，时间，O()，然后块与块之间相连的初始化直接O(n)跑，会初始化√n块，时间O()，再加上排序O(m*logm)，所以按照这种计算方式总时间复杂度O()
然后，根据广大人民意愿就当成是O()的吧。【实际上也差不多了好吧】233
今天没时间了，题目明天写吧。(实际上由于是土豪题，拖了大概6.7~8.3。。。两个月啊。233)以下是代码。
直接修改答案。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,k,col[51000],num[51000];
struct quest
{
int l,r,bl,id,ans;
}a[51000];
bool cmp1(quest x,quest y)
{
return x.bl==y.bl? x.r<y.r : x.bl<y.bl;
}
bool cmp2(quest x,quest y)
{
return x.id<y.id;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%d",&col[i]);
int blo=sqrt(1.0*n)+1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i; a[i].bl=a[i].l/blo;
}
sort(a+1,a+m+1,cmp1);
int L=1,R=1,now=1; num[col[1]]++;
for(int i=1;i<=m;i++)
{
while(L>a[i].l)
{
L--;
now+=(num[col[L]]<<1)+1;
num[col[L]]++;
}
while(R<a[i].r)
{
R++;
now+=(num[col[R]]<<1)+1;
num[col[R]]++;
}
while(L<a[i].l)
{
now-=(num[col[L]]<<1)-1;
num[col[L]]--;
L++;
}
while(R>a[i].r)
{
now-=(num[col[R]]<<1)-1;
num[col[R]]--;
R--;
}
a[i].ans=now;
}
sort(a+1,a+m+1,cmp2);
for(int i=1;i<=m;i++)
printf("%d\n",a[i].ans);
return 0;
}