정수 에 대한 함수 은 다음과 같이 정의된다.
즉, 위 함수는 정수 을 이진수로 나타내었을 때 1의 개수를 에 대한 함숫값으로 한다.
길이가 인 수열 과 이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하라.
1 l r x : 인 에 대해 를 수행한다.첫 번째 줄에 수열의 크기 이 주어진다.
두 번째 줄에는 이 주어진다.
3번 쿼리가 주어질 때마다 정답을 줄 바꿈으로 구분하여 출력한다.
2 l r x k : 인 에 대해 를 수행한다.3 l r : 을 출력한다.세 번째 줄에는 이 주어진다.
네 번째 줄에는 쿼리의 개수 가 주어진다.
다섯 번째 줄부터 개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.