二进制

题目描述

你是一个算法爱好者，在努力学习计算机知识。你知道，计算机最优美的地方在于二进制，这一点你在状压加o里面深有体会，当然二进制用在co and o时的也非常巧妙，更不用T说nini游戏都能跟于xor扯上关系了，而今天你又遇到了一道二进制的题目，对于爱思考的你，决定一直要把这道二进制题给切掉。
你遇到了很多十进制的数，对于这些数，它们都管理着它们对应的分层，比如数字8，它的二进制是1，则它管理着4(10),2(10)，两个分段，当数字闯的在2,4区间上增加时，沬代表二进制(10)和(10)两层在[2,4]区间增加3。
本道题有两种操作，读入一个opt
opt为1时:读入一个数q_i，一个区间l_i, r_i和一个增加的值k_i，表示在这个数管理的分层中的每一个区间增加k_i值。
opt为2时:读入一个数a_i，一个区间l_i,r_i，表示询问这个数管理的分层中每一个区间的值的总和。

输入

第一行两个整数n,q，表示n表示区间长度(1≤l_i ≤r_i ≤n≤100000)，q表示有q(1≤q≤100000)次操作。数据保证(1≤a_i≤1024),k_i在int范围内
后面q行，每行首先一个数opt表示进行的操作
opt= 1时后接整数a_i表示管理分层，l_i,r_i表示区间，k_i表示增加的值opt= 2时后接整数a_i表示管理分层，l_i,r_i表示区间

输出

对于每个第二个操作，输出一行表示询问的答案。

Sample Input

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

Sample Output

4
8

思路解析

开12个线段树，别问为什么是12个问就是我不想卡边界。
然后侦测该数的二进制位是1的序号，入栈（队列）,然后依次维护该序列号的线段树。
最后读取的时候，也是把所有序号的线段树查询一遍，求一个和就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