3781: 小B的询问
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 288 Solved: 196
[Submit][Status][Discuss]
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
1 3 2 1 1 3
1 4
2 6
3 5
5 6
Sample Output
6
9
5
2
9
5
2
HINT
对于全部的数据，1<=N、M、K<=50000
Source
和上一篇小Z的袜子几乎一样。。。可以看上一篇题解-->http://wyxoi.is-programmer.com/posts/182400.html
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 50000+10;
struct data{ll l,r,ans,id;} q[N];
ll s[N],c[N],pos[N],n,m,ans,l,r,blk,K;
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
bool cmpid(data a,data b){return a.id<b.id;}
bool cmp(data a,data b){if (pos[a.l]==pos[b.l]) return a.r<b.r;return pos[a.l]<pos[b.l];}
void init(){
n = read();m = read();K = read();
blk = (int)sqrt(n);
for (ll i=1;i<=n;i++) pos[i] = (i-1)/blk+1;
for (ll i=1;i<=n;i++) c[i] = read();
for (ll i=1;i<=m;i++){q[i].l = read();q[i].r = read();q[i].id = i;}
}
ll work(ll x){return x*x;}
void Update(ll p,ll val){
if (c[p]>K) return;
ans-=work(s[c[p]]);s[c[p]]+=val;ans+=work(s[c[p]]);
}
void solve(){
l = 1,r = 0,ans = 0;
for (ll i=1;i<=m;i++){
while (r<q[i].r) Update(r+1,1),r++;
while (r>q[i].r) Update(r,-1),r--;
while (l<q[i].l) Update(l,-1),l++;
while (l>q[i].l) Update(l-1,1),l--;
q[i].ans = ans;
}
}
int main(){
init();
sort(q+1,q+1+m,cmp);
solve();
sort(q+1,q+1+m,cmpid);
for (ll i=1;i<=m;i++) printf("%lld\n",q[i].ans);
}
评论 (0)
