Post 24

Veröffentlicht am

导言：Po主最近太懒，状态太差，不想Coding…..

希望自己能早点找回原来精力充沛的状态。。

话说感觉这次月考稳定1000+名啊，无话可说，智商硬伤。。

点分治略解

我们来抽象一点描述（好掩盖不会的事实.?）

对于一类树上路径统计问题，我们在选取任意一点p为根后，发现路径可以分为这样的两类：过p和不过p的，然后就可以递归分治。在我们每次选取树的重心的情况下可以证明递归层数是$logn$层。

每一层一般处理的时候需要一个较高效的统计方法，一般是$O(nlogn)$或$O(n)$的。

略解就到这里233.

分块初步

（终于写了道题，结果调了半天）

分块是一种根号算法，主要是利用根号平衡的思想均摊每项操作的复杂度。

操作上很简单，自己体会下“大段维护，小段朴素”的思想自己yy出代码并不难。

不过就是边界情况容易漏掉就是了。。我调了一个小时区间加就是因为忘了查询修改可以在同一块，必须特殊处理。。

上道模板题

A Simple Problem with Integers

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.InputThe first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c“ means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b“ means querying the sum of Aa, Aa+1, … , Ab.OutputYou need to answer all Q commands in order. One answer in a line.

Sample Input10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4

Sample Output4 55 9 15HintThe sums may exceed the range of 32-bit integers.

题解

懒得调格式了，总之就是区间加。

上分块代码，主要就是记录序列每个位置是哪个块，以及当前块的左右端点就可以轻松维护啦。

写的挺长的。。。可能是我姿势不对

Code：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#define maxn 100005
int n , m , L[maxn] , R[maxn] , pos[maxn]  , st;
long long s[maxn>>3] , tag[maxn>>3] , a[maxn];
inline void pre()
{
	st = std::sqrt(n);
	for(int i = 1 ; i <= st ; ++i)
		L[i] = (i-1)*st+1 , R[i] = i * st;
	if(R[st] < n) ++st , L[st] = R[st-1] + 1 , R[st] = n;
	for(int i = 1 ; i <= st ; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j)
			pos[j] = i , s[i] += a[j];
}
inline long long query(int l , int r)
{
	long long ans = 0;
	if(pos[l] == pos[r]) // special situation
	{
		int p = pos[l];
		for(int i = L[p] ; i <= R[p] ; ++i)
			a[i] += tag[p];
		tag[p] = 0;
		for(int i = l ; i <= r ; ++i)
			ans += a[i];
		return ans;
	}
	if(l != L[pos[l]])
	{
		for(int i = L[pos[l]] ; i <= R[pos[l]] ; ++i)
			a[i] += tag[pos[l]];
		tag[pos[l]] = 0;
		for(int i = l ; i <= R[pos[l]] ; ++i)
			ans += a[i];
		l = L[pos[l] + 1];
	}
	if(r != R[pos[r]])
	{
		for(int i = L[pos[r]] ; i <= R[pos[r]] ; ++i)
			a[i] += tag[pos[r]];
		tag[pos[r]] = 0;
		for(int i = L[pos[r]] ; i <= r ; ++i)
			ans += a[i];
		r = R[pos[r] - 1];
	}
	for(int i = pos[l] ; i <= pos[r] ; ++i)
		ans += s[i];
	return ans;
}

inline void update(int l , int r , int v)
{
	if(pos[l] == pos[r])
	{
		for(int i = l ; i <= r ; ++i)
			a[i] += v;
		s[pos[l]] += 1ll * (r - l + 1) * v;
		return ;
	}
	if(l != L[pos[l]])
	{
		for(int i = l ; i <= R[pos[l]] ; ++i)
			a[i] += v , s[pos[i]] += v;
		l = L[pos[l]+1];
	}
	if(r != R[pos[r]])
	{
		for(int i = L[pos[r]] ; i <= r ; ++i)
			a[i] += v , s[pos[i]] += v;
		r = R[pos[r]-1];
	}
	for(int i = pos[l] ; i <= pos[r] ; ++i)
		s[i] += 1ll * (R[i] - L[i] + 1) * v , tag[i] += v;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lld",&a[i]);
	pre();
	while(~--m)
	{
		int  l , r;
		char op;
		scanf("\n%c%d%d",&op,&l,&r);
		if(op == 'C')
		{
			int v;
			scanf("%d",&v);
			update(l , r, v);
		}
		else if(op == 'Q')
			printf("%lld\n",query(l,r));
	}

}