【TopCoder SRM714】NAddOdd

相关链接

题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=14408&rd=16883
神犇题解：http://codeforces.com/blog/entry/50602?#comment-358475

解题报告

设$f(x)=\sum\limits_{i=1}^{x}{g(k+i)}$
那么奇偶讨论，可以得到递推式$f(x)=(f(\frac{x-k}{2})+\frac{x}{2})+(f(\frac{x}{2})+x)$
于是递归算$f(\frac{x-k}{2})$，$\sum\limits_{i=\frac{x-k}{2}+1}^{\frac{x}{2}}{g(i)}$暴力算
时间复杂度：$O(k \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

class NAddOdd {
    public:
    	long long solve(long long L, long long R, int K) {
			return Cal(R - K, K) - Cal(L - 1 - K, K);
   		}
   	private:
   		inline LL Cal(LL n, int k) {
			if (n <= 0) {
				return 0;
			} else {
				LL ret = Cal((n - k) >> 1, k) << 1;
				ret += n + (n >> 1);
				for (LL i=((n-k)>>1)+1;i*2<=n;i++) {
					ret += g(i + k, k);
				}
				return ret;
			}
		}
		inline int g(LL x, int k) {
			LL ret = 0, w = x;
			while (w > k) {
				++ret;
				w = (((w&1)? (w+k): (w>>1)));
			} 
			return ret;
		} 
};