UVa 1406 - A Sequence of Numbers

#数学 #树状数组 #预处理

Published on 2016-01-07

题目地址

描述

给定一个长度为 $n(n\le100000)$ 的序列，每个数的范围都是 $[0, 2^{16})$ ，现在有两种操作：

C T：给序列里的每一个数加上一个数 $T(T\ge0)$ ，如果某个数超过了 $2^{16}$ ，将其对 $2^{16}$ 取余数。
Q T：给定一个数 $T$ ，查询序列里有多少个数的二进制位的第 $T(0\le T\le 16)$ 位是 $1$ 。

现在给出 $m(m\le200000)$ 个查询，为了方便起见，请你输出所有 Q T 操作结果的和 $\mathrm{sum}(\mathrm{sum}\le10000000000)$ 。

样例输入

样例输出

Case 1: 5

附加输入

附加输出

Case 1: 17
Case 2: 9

分析

乍一看线段树搞一搞就行，但很大的问题就是查询是针对二进制位的，所以光打 $add$ 标记是无法知道数的二进制位的，于是得想办法。
由于一口气查询所有数的某一二进制位是不是 $1$ ，所以我们考虑维护 $16$ 个树状数组，第 $i(i \ge 0)$ 个树状数组维护所有数的二进制位 $[0, i]$ 位的和。每个树状数组的位置 $i$ 记录有几个数和为 $i$ 。
举个例子，对于数 $187$ 的二进制表示（仅给出前 8 位，最右边为最低位）： $10111011$ ，那么第 $0$ 位对应的和为 $1$ ，第 $7$ 位则对应 $187$ 。对应第 $7$ 个树状数组的 $187$ 位置的值为 $1$
如果遇到一个查询，记录之前所有增加操作的和 $\mathrm{sum}$ ，注意每次对 $2^{16}$ 取余。如果查询第 $k$ 位，那么第 $k$ 位的值显然与大于 $k$ 位没有一点关系，所以我们可以只考虑第 $k$ 个树状数组， $\mathrm{sum}$ 值也可以只要 $[0, k]$ 位。
接下来就是讨论 $[0, k]$ 位的数可取哪些值，加上 $\mathrm{sum}$ 值后仍为第 $k$ 位仍然为 $1$ ，很简单，拿纸算一下就行了，有几种情况（如果你只想要答案，懒得算就看下面）。
如果 $\mathrm{sum}$ 的第 $k$ 位是 $1$ ，要么数 $x$ 的第 $k$ 位是 $0$ 且之前位加上来没有进位，要么数 $x$ 的第 $k$ 位是 $1$ 且之前位加上来有进位。
如果 $\mathrm{sum}$ 的第 $k$ 位是 $0$ ，要么数 $x$ 的第 $k$ 位是 $1$ 且之前位加上来没有进位，要么数 $x$ 的第 $k$ 位是 $0$ 且之前位加上来有进位。
综合一下就是（设 $b_i$ 为 $\mathrm{sum}$ 的二进制第 $i$ 位）：

接下来树状数组求和就行，这题构造很巧妙，细节参见代码。

代码

//  Created by Sengxian on 1/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1406 树状数组
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <climits>
#include <cassert>
using namespace std;
const int maxn = 100000 + 3, maxBit = 17;

//Fenwick Tree 0 - indexed
struct Fenwick {
    vector<int> c;
    int n;
    //init [0, n)
    void init(int n) {
        this -> n = n;
        c = vector<int>(n + 1, 0);
    }
    static inline int lowbit(int x) {
        return x & -x;
    }
    //0 - indexed;
    void add(int x, int d) {
        x++;
        while(x <= n) {
            c[x] += d; x += lowbit(x);
        }
    }
    //sum of [0, x)
    int sum(int x) {
        int ret = 0;
        while(x > 0) {
            ret += c[x]; x -= lowbit(x);
        }
        return ret;
    }
    //sum of [l, r)
    int Sum(int l, int r) {
        return sum(r) - sum(l);
    }
}Bits[maxBit];

int n;

int main() {
    int caseNum = 0;
    while(~scanf("%d", &n) && ~n) {
        long long ans = 0;
        int sum = 0;
        for(int i = 0; i < maxBit; ++i) Bits[i].init(1 << (i + 1));
        for(int i = 0; i < n; ++i) {
            int x, tot = 0; scanf("%d", &x);
            for(int j = 0; j < maxBit; ++j) {
                if((x >> j) & 1) tot += 1 << j;
                Bits[j].add(tot, 1);
            }
        }
        char ch;
        while(getchar(), ch = getchar(), ch != 'E')
            if(ch == 'Q') {
                int x; scanf("%d", &x);
                int t = sum;
                sum %= 1 << (x + 1);
                if((sum >> x) & 1) {
                    //第 x 位为 1
                    sum -= 1 << x;
                    ans += Bits[x].Sum(0, (1 << x) - sum);
                    ans += Bits[x].Sum((1 << x + 1) - sum, 1 << x + 1);
                }else ans += Bits[x].Sum((1 << x) - sum, (1 << x + 1) - sum);
                sum = t;
            }else if(ch == 'C') {
                int a = 0; scanf("%d", &a);
                sum += a, sum %= 1 << 16;
            }
            else assert(false);
        printf("Case %d: %lld\n", ++caseNum, ans);
    }
    return 0;
}

POJ、BZOJ 题目排序 UVa 11992 - Fast Matrix Operations(线段树模板)

Sengxian's Blog