# Divide (four provincial contests postponed due to epidemic, continued fighting)

Magical Number

Title Description
Adds the bits of a number and, if the sum is even, calls it a magical number.
Ask for the number of magical numbers in [a,b].

Input Format
The first behavior is a positive integer n, which represents the number of groups of data.
Next n rows, two positive integers a and b each.
0 < n < 1000;
0 < a,b < INT_MAX;

Output Format
Each set of data outputs a row, a magical number.

sample input
2
2 3
101 105

sample output
1
3

```#include<iostream>
using namespace std;
bool check(int x){
int t=0;
while(x){
t+=x%10;
x/=10;
}
return t%2==0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int a,b,ans=0;
cin>>a>>b;
if(a/10==b/10){
for(int i=a;i<=b;i++)
if(check(i))
ans++;
}
else{
for(int i=a;i<=a/10*10+9;i++)
if(check(i))
ans++;
ans+=(b/10*10-(a/10+1)*10)/2;
for(int i=b/10*10;i<=b;i++)
if(check(i))
ans++;
}
cout<<ans<<endl;
}
}
```

The magic of the Bishop
Title Description
The bishop has recently learned a magic trick to make people grow tall. So he's ready to show it to every hero in the XMYZ message group. So N heroes gathered together again, this time in a row numbered 1, 2,..., N.
Each person's height starts with a positive integer of no more than 1000. The bishop's magic adds an integer W to the heights of heroes in the closed interval [L, R] (1 < L < R < N) each time. (Although L=R does not conform to the interval writing conventions, we can consider adding L(R) hero height alone)
CYZ, Guangge and ZJQ do not believe in the evil of the religious master, so they sometimes ask how many heroes are taller than or equal to C in the WD closed interval [L, R] to verify whether the magic of the religious master really works.
WD is so lazy that he gives you the task of answering this question.
Input Format
The first behavior is two integers N, Q. Q is the sum of the number of questions and the number of Master's actions.
Line 2 has N positive integers, and the number i represents the height of the hero i I.
Rows 3 through Q+2 have one action per line:
(1) If the first letter is M, then there are three numbers L, R, W. Represents the addition of W to the height of all heroes in the closed interval [L, R].
(2) If the first letter is "A", then there are three numbers L, R, and C. Ask how many heroes in the closed range [L, R] are taller than or equal to C.
Output Format
Output one line for each "A" query, with only one integer, indicating the number of heroes whose inner height is greater than or equal to C in the closed interval [L, R].

sample input
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

sample output
2
3

Tips
The original five heroes were 1, 2, 3, 4, 5. At this time, two heroes were greater than or equal to 4 in [1, 5]. When the bishop casts the spell and becomes 1, 2, 4, 5, 6, there are three heroes between [1, 5] who are taller than or equal to 4.
For 100% of the data, N < 1000000, Q < 3000, 1 < W < 1000, 1 < C < 1,000,000.

```#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=1000010;
int a[MAX],b[MAX],lazy[MAX];
int sze,cnt;
int n,q;
void Init(int id){
int st=(id-1)*sze+1;
int ed=min(id*sze,n);
for(int i=st;i<=ed;i++)
a[i]=b[i]+lazy[id];
sort(a+st,a+ed+1);
lazy[id]=0;
}
int cal(int id,int val){
int st=(id-1)*sze+1;
int ed=min(id*sze,n);
return (a+ed+1)-lower_bound(a+st,a+ed+1,val-lazy[id]);
}
int query(int l,int r,int val){
int lid=(l-1)/sze+1,rid=(r-1)/sze+1;
int res=0;
if(lid==rid){
for(int i=l;i<=r;i++)
if(b[i]+lazy[lid]>=val)
res++;
}
else{
int led=lid*sze;
int rst=(rid-1)*sze+1;
for(int i=l;i<=led;i++)
if(b[i]+lazy[lid]>=val)
res++;
for(int i=rst;i<=r;i++)
if(b[i]+lazy[rid]>=val)
res++;
for(int i=lid+1;i<rid;i++)
res+=cal(i,val);
}
return res;
}
void add(int l,int r,int val){
int lid=(l-1)/sze+1,rid=(r-1)/sze+1;
if(lid==rid){
for(int i=l;i<=r;i++)
b[i]+=val;
Init(lid);
}
else{
int led=lid*sze;
int rst=(rid-1)*sze+1;
for(int i=l;i<=led;i++)
b[i]+=val;
Init(lid);
for(int i=rst;i<=r;i++)
b[i]+=val;
Init(rid);
for(int i=lid+1;i<rid;i++)
lazy[i]+=val;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
sze=max((int)sqrt(n),1);
cnt=n%sze?n/sze:n/sze+1;
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=cnt;i++)
Init(i);
for(int i=1;i<=q;i++){
char str[5];
int l,r,val;
cin>>str>>l>>r>>val;
if(str[0]=='A')
cout<<query(l,r,val)<<endl;
else