[BZOJ] 3781: 작은 B 의 질문 (모 팀 알고리즘)

http://www.lydsy.com/JudgeOnline/problem.php?id=3781
좀 더 나체로 하면 안 돼 요?

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }



const int N=50005;

struct dat { int l, r, id; }q[N];

int a[N], n, m, k, pos[N];

ll sum, ans[N], s[N];



inline bool cmp(const dat &a, const dat &b) { return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l; }

inline void fix(const int &x, const int &f) {

	sum-=s[x]*s[x];

	s[x]+=f;

	sum+=s[x]*s[x];

}

void init() {

	int sz=sqrt(0.5+n);

	for1(i, 1, n) pos[i]=i/sz;

	sort(q+1, q+1+m, cmp);

}

int main() {

	read(n); read(m); read(k);

	for1(i, 1, n) read(a[i]);

	for1(i, 1, m) read(q[i].l), read(q[i].r), q[i].id=i;

	init();

	int l=1, r=0;

	for1(i, 1, m) {

		int xl=q[i].l, xr=q[i].r, id=q[i].id;

		while(l<xl) fix(a[l++], -1);

		while(l>xl) fix(a[--l], 1);

		while(r<xr) fix(a[++r], 1);

		while(r>xr) fix(a[r--], -1);

		ans[id]=sum;

	}

	for1(i, 1, m) printf("%lld
", ans[i]);

	return 0;

}

　　
 
 
 
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
6
9
5
2
HINT
 
모든 데이터 에 대해 1 < = N, M, K < = 50000
 
 
Source