8.22 T3 escape from whk 3（2次幂相关）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141426364

http://cplusoj.com/d/senior/p/SS240709C

考虑一个 [l,r][l,r] 区间，我们有什么策略？

性质1：我们从大到小，能选就选，肯定最优

如果按照这样子，我们可以发现选出来的数肯定长成这个样子

在这里插入图片描述

因此我们可以：

在这里插入图片描述

这样子对于一个 [l,r][l,r] 的复杂度是 O(log⁡)O(\log) 的，我们解决掉了 num=0num=0 了

考虑统计全局，假设我们现在求 [1,r][1,r] ，肯定长成这样：

在这里插入图片描述

而当 ll 变化时，还是选 ll 右边的蓝色段：

在这里插入图片描述

所以我们在固定 rr 的时候，可以直接考虑蓝色短的贡献。

对于一个蓝色格子，它会在所有 ll 在它前面时有贡献。也就是说 ii 的贡献恰好为 ii ，这启示我们：

在这里插入图片描述

所以对于一个整个蓝色短，我们直接等差数列求和必然就是其贡献

这个可以递归，也可以直接dp实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 300010
int n, m, i, j, k, T;
int In[N], f[N], Q, o, l, r, ans; 

int solve(int l, int r) {
	int mid = In[r]; 
	if(l > r) return 0; 
	if(mid < l) return r - l + 1; 
	int ans = r - mid + 1, k = mid - ans; 
	return ans + solve(l, k); 
}

int calc(int l, int r) {
	debug("[%lld %lld]\n", l, r); 
	return (l + r) * (r - l + 1) / 2; 
}

//int solve2(int r) {
//	int mid = In[r]; 
//	debug("r is %llld\n", r); 
//	if(1 > r) return 0; 
//	if(mid <= 1) return calc(1, r); 
//	int ans = calc(mid, r), k = mid - (r - mid + 1); 
//	return ans + solve2(k); 
//}

signed main()
{
freopen("kuhu.in", "r", stdin);
	  freopen("kuhu.out", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); Q = read(); o = read(); 
	for(i = 1, k = 1; i <= n; ++i) {
		if((k << 1) <= i) k <<= 1; 
		In[i] = k; 
	}
	for(i = 1; i <= Q; ++i) {
		l = read(); r = read(); 
		printf("%lld\n", solve(l, r)); 
	}
	if(!o) return printf("0"), 0; 
	f[1] = 1; f[2] = 3; ans = 4; 
	for(i = 3; i <= n; ++i) {
		j = In[i]; k = max(0ll, j - (i - j + 1)); 
		f[i] = f[k] + calc(j, i); ans += f[i]; 
	}
	printf("%lld", ans); 
	return 0;
}