记录编号	404148	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	迷妹	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.761 s
提交时间	2017-05-12 21:39:14	内存使用	6.80 MiB

# include <bits/stdc++.h>
# define MAXN 100023
using namespace std;
inline int get_num() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
int n, q, mei[MAXN];
struct zkw_segtree {
	int a[4][MAXN << 2], M;
	inline zkw_segtree() {
		memset(a, 0, sizeof(a));
		M = 0;
	}
	inline void push_up(int x) {
		for(int i = 1; i <= 3; i++) {
			a[i][x] = a[i][x << 1] + a[i][x << 1 | 1];
		}
	}
	inline void build() {
		for(M = 1; M <= n + 1; M <<= 1);
		for(int i = M + 1; i <= M + n; i++) {
			a[mei[i - M]][i]++;
		}
		for(int i = M; i >= 1; i--) {
			push_up(i);
		}
	}
	inline void query(int l, int r) {
		int ans[4];
		memset(ans, 0, sizeof(ans));
		for(l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
			if(~l & 1) {
				for(int k = 1; k <= 3; k++) ans[k] += a[k][l + 1];
			} 
			if(r & 1) {
				for(int k = 1; k <= 3; k++) ans[k] += a[k][r - 1];
			}
		}
		for(int i = 1; i <= 3; i++) printf("%d ", ans[i]);
		printf("\n");
	}
}T;
int main() {
	freopen("fans.in", "r", stdin);
	freopen("fans.out", "w", stdout);
	n = get_num();
	q = get_num();
	for(int i = 1; i <= n; i++) {
		mei[i] = get_num();
	}
	T.build();	
	while(q--) {
		int s = get_num();
		int t = get_num();
		T.query(s, t);
	}
	return 0;
}