bzoj 3781: 小B的询问（莫队）-白红宇

bzoj 3781: 小B的询问（莫队）

阅读量：2143 次

发布时间：2019-04-30

本文共 1047 字，大约阅读时间需要 3 分钟。

Time Limit: 10 Sec

Memory Limit: 128 MB

Submit: 1064

Solved: 713

[ ][ ][ ]

Description

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行，三个整数N、M、K。

第二行，N个整数，表示小B的序列。

接下来的M行，每行两个整数L、R。

Output

M行，每行一个整数，其中第i行的整数表示第i个询问的答案。

Sample Input

6 4 3

1 3 2 1 1 3

1 4

2 6

3 5

5 6

Sample Output

很简单的O(1)修改

莫队模板题。。

#include
   
    #include
    
     #include
     
      using namespace std;#define LL long longtypedef struct Res{	int x;	int y, id;}Res;Res s[100005];int a[100005], bel[100005];LL ans[100005], sum[100005];bool comp(Res a, Res b){	if(bel[a.x]
      
       =B)			x = 0, y++;	}	sort(s+1, s+m+1, comp);	L = R = 1;	sum[a[1]] = val = 1;	for(i=1;i<=m;i++)	{		while(L
       
        s[i].x)		{			L--;			val -= (sum[a[L]])*(sum[a[L]]);			sum[a[L]]++;			val += (sum[a[L]])*(sum[a[L]]);		}		while(R
        
         s[i].y) { val -= (sum[a[R]])*(sum[a[R]]); sum[a[R]]--; val += (sum[a[R]])*(sum[a[R]]); R--; } ans[s[i].id] = val; } for(i=1;i<=m;i++) printf("%lld\n", ans[i]); return 0;}

转载地址：http://vmmgf.baihongyu.com/

你可能感兴趣的文章