Binary system

Title Description

You are an algorithm enthusiast , I'm trying to learn computer knowledge . You know, , The most beautiful thing about computers is binary , You are pressing on this point o I have deep experience in it , Of course, binary is used in co and o It's also very clever , Not to mention T say nini Games can follow xor It's a matter of fact , And today you have another binary problem , For you who love to think , I decided to cut off this binary problem all the time .
You come across a lot of decimal numbers , For these numbers , They all manage their corresponding layers , Such as digital 8, Its binary is 1, Then it manages 4(10),2(10), Two segments , When the numbers break in 2,4 When the interval increases , Foam stands for binary (10) and (10) Two floors in [2,4] The interval increases 3.
This question has two operations , Read into one opt
opt by 1 when : Read in a number q_i, An interval l_i, r_i And an increased value k_i, Indicates that each interval in the hierarchy managed by this number increases k_i value .
opt by 2 when : Read in a number a_i, An interval l_i,r_i, Represents the sum of the values of each interval in the hierarchy managed by this number .

Input

The first line has two integers n,q, Express n Indicates the interval length (1≤l_i ≤r_i ≤n≤100000),q Express q(1≤q≤100000) operations . Data assurance (1≤a_i≤1024),k_i stay int Within the scope of
Back q That's ok , Each line starts with a number opt Indicates the operation performed
opt= 1 When followed by an integer a_i Indicates management hierarchy ,l_i,r_i Indicates the interval ,k_i Indicates the increased value opt= 2 When followed by an integer a_i Indicates management hierarchy ,l_i,r_i Indicates the interval

Output

For each second operation , Output a line indicating the answer to the query .

Sample Input

5 3
1 3 1 5 2
2 1 1 2
2 3 1 2

Sample Output

4
8

Thinking analysis

open 12 A line tree , Don't ask why 12 One question is that I don't want to get stuck .
Then detect that the binary bit of the number is 1 The serial number of , Push （ queue ）, Then maintain the segment tree of the serial number in turn .
At the last reading , It is also to query the line segment tree of all serial numbers , Just ask for a peace OK 了 .

Accepted Code

//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
    
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    
	return a / gcd(a, b) * b;
}
inline ll read() {
    
	ll c = getchar(), Nig = 1, x = 0;
	while (!isdigit(c) && c != '-')c = getchar();
	if (c == '-')Nig = -1, c = getchar();
	while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
	return Nig * x;
}
inline void out(ll a) {
    
	if (a < 0)putchar('-'), a = -a;
	if (a > 9)out(a / 10);
	putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
    
	ll res = 1;
	while (n > 0) {
    
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}
#define read read()
const int N = 100007;
struct node
{
    
	ll sum, num;
	bool lazy;
}tree[12][N << 2];
void pushup(int k, int rt)
{
    
	tree[k][rt].sum = tree[k][rt << 1].sum + tree[k][rt << 1|1].sum;
}
void pushdown(int k, int len, int rt)
{
    
	if (tree[k][rt].lazy)
	{
    
		tree[k][rt << 1].lazy = tree[k][rt << 1 | 1].lazy = true;
		tree[k][rt].lazy = false;
		tree[k][rt << 1].num += tree[k][rt].num;
		tree[k][rt << 1 | 1].num += tree[k][rt].num;
		tree[k][rt << 1].sum += tree[k][rt].num * (len - (len >> 1));
		tree[k][rt << 1 | 1].sum += tree[k][rt].num * (len >> 1);
		tree[k][rt].num = 0;
	}
}
void update(int L, int R, ll val, int k, int l, int r, int rt)
{
    
	if (L <= l && r <= R)
	{
    
		tree[k][rt].lazy = true;
		tree[k][rt].num += val;
		tree[k][rt].sum += (r - l + 1) * val;
		return;
	}
	pushdown(k, r - l + 1, rt);
	int mid = l + r >> 1;
	if (L <= mid)update(L, R, val, k, l, mid, rt << 1);
	if (R >= mid + 1)update(L, R, val, k, mid + 1, r, rt << 1 | 1);
	pushup(k, rt);
}
ll query(int L, int R, int k, int l, int r, int rt)
{
    
	if (L <= l && r <= R)return tree[k][rt].sum;
	pushdown(k, r - l + 1, rt);
	int mid = l + r >> 1;
	ll res = 0;
	if (L <= mid)res += query(L, R, k, l, mid, rt << 1);
	if (R > mid)res += query(L, R, k, mid + 1, r, rt << 1 | 1);
	return res;
}
stack<ll>s;
int main()
{
    
	accelerate;
	int n, m;
	cin >> n >> m;
	while (m--)
	{
    
		ll mark, id;
		cin >> mark >> id;
		if (mark == 1)
		{
    
			for (ll i = 1, cnt = 0; i <= 1024; i <<= 1, cnt++)
				if (i & id)s.push(cnt);
			ll l, r, val;
			cin >> l >> r >> val;
			while (!s.empty())
			{
    
				ll now = s.top();
				s.pop();
				update(l, r, val, now, 1, n, 1);
			}
		}
		else
		{
    
			for (ll i = 1, cnt = 0; i <= 1024; i <<= 1, cnt++)
				if (i & id)s.push(cnt);
			ll ans = 0;
			ll l, r;
			cin >> l >> r;
			while (!s.empty())
			{
    
				ll now = s.top();
				s.pop();
				ans += query(l, r, now, 1, n, 1);
			}
			cout << ans << endl;
		}
	}
}

By-Round Moon