題目描述

小B有一個序列，包含N個1~K之間的整數(shù)。他一共有M個詢問，每個詢問給定一個區(qū)間[L..R]，求Sigma(c(i)^2)的值,其中i的值從1到K，其中c(i)表示數(shù)字i在[L..R]中的重復(fù)次數(shù)。小B請你幫助他回答詢問。

輸入輸出格式

輸入格式：

?

第一行，三個整數(shù)N、M、K。

第二行，N個整數(shù)，表示小B的序列。

接下來的M行，每行兩個整數(shù)L、R。

?

輸出格式：

?

M行，每行一個整數(shù)，其中第i行的整數(shù)表示第i個詢問的答案。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 輸出樣例#1：?復(fù)制 6 9 5 2

說明

對于全部的數(shù)據(jù)，1<=N、M、K<=50000

題解：莫隊模板吧，稍加修改

#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int N=50005; inline int get(){int f=1;char c=getchar();int res=0;while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){res=(res<<3)+(res<<1)+c-'0';c=getchar();}return res*f; } struct node{int l,r,id; }e[N]; int a[N],n,m,jjj[N],f[N],ans,k,kk;bool cmp(node p,node q){if((p.l-1)/kk==(q.l-1)/kk) return p.r<q.r;else return (p.l-1)/kk<(q.l-1)/kk; }void add(int x){if(++f[x]==1) ans+=2*f[x]-1; } void remove(int x){if(--f[x]==0) ans-=2*f[x]-1; } int main(){freopen("02709.in","r",stdin);freopen("02709.out","w",stdout);n=get(); m=get(); k=get();kk=sqrt(n);for(int i=1;i<=n;i++)a[i]=get();for(int i=1;i<=m;i++){e[i].l=get();e[i].r=get();e[i].id=i;}sort(e+1,e+m+1,cmp);int L=1,R=0;for(int i=1;i<=m;i++){//while(L>e[i].l) add(a[--L]);//while(R<e[i].r) add(a[++R]);//while(L<e[i].l) remove(a[L++]);//while(R>e[i].r) remove(a[R--]);while(L>e[i].l) L--,f[a[L]]++,ans+=2*f[a[L]]-1;while(R<e[i].r) R++,f[a[R]]++,ans+=2*f[a[R]]-1;while(L<e[i].l) f[a[L]]--,ans-=2*f[a[L]]+1,L++;while(R>e[i].r) f[a[R]]--,ans-=2*f[a[R]]+1,R--;jjj[e[i].id]=ans;}for(int i=1;i<=m;i++)printf("%d\n",jjj[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wuhu-JJJ/p/11235072.html

總結(jié)

以上是生活随笔為你收集整理的【洛谷 2709】小B的询问的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。