Question

跪求ACM大神帮助，各位麻烦帮我看看这道题到底要用什么算法解决，不用写出代码。只要说要用的算法就好。

这题是福建省2012大学生程序设计竞赛的题目，如果知道怎样做，
请告诉我方法，谢谢
Problem Description

Given N integersA={A[0],A[1],...,A[N-1]}. Here we have some operations:

Operation 1: AND opn L R
Here opn, L and R areintegers.
For L≤i≤R, we doA[i]=A[i] AND opn (here "AND" is bitwise operation).

Operation 2: OR opn L R
Here opn, L and R areintegers.
For L≤i≤R, we doA[i]=A[i] OR opn (here "OR" is bitwise operation).

Operation 3: XOR opn L R
Here opn, L and R areintegers.
For L≤i≤R, we doA[i]=A[i] XOR opn (here "XOR" is bitwise operation).

Operation 4: SUM L R
We want to know theresult of A[L]+A[L+1]+...+A[R].
Now can you solve thiseasy problem?

Input
The first line of theinput contains an integer T, indicating the number of test cases. (T≤100)
Then T cases, for anycase, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000),
indicating the number of elements in A and the number of operations.

Then one line follows nintegers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).
Then m lines, each linemust be one of the 4 operations above. (0≤opn≤15)

Output
For each test case and for each "SUM"operation, please output the result with a single line.

Sample Input
1
4 4
1 2 4 7
SUM 0 2
XOR 5 00
OR 6 03
SUM 0 2

Sample Output
7
18

Hint
A = [1 2 4 7]
SUM 0 2, result=1+2+4=7;
XOR 5 0 0, A=[4 2 4 7];

Answer 1

这题是用线段树来做的，这题用的是位操作，可以发现题目中的元素比较小，只有2的4次方，我们可以，建立四棵线段树，第i棵代表2的i次方所对应的位。分别对这四个位进行处理。

这样可以在每一次logn的时间内出解。可以过此题。

追问

你好，请问知不知道哪个oj有类似的题目

追答

codeforces上有的，这个题就是从那儿改过来的。