其实是偷懒不想写好多篇。

Table of Contents

  1. BZOJ 1577
    1. Description
    2. Solution
  2. BZOJ 2216
    1. Description
    2. Solution
  3. BZOJ 5055
    1. Description
    2. Solution

BZOJ 1577

Description

公交车一共经过$N(1 \le N \le 20000)$个站点，从站点$1$一直驶到站点$N$。

$K（1 \le K \le 50000)$群奶牛希望搭乘这辆公交车。第$i$群牛一共有$M_i（1 \le M_i \le N)$只. 他们希望从$S_i$到$E_i$去。

公交车只能坐$C(1 \le C \le 100)$只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛的要求。

注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。

Solution

贪心。

线段树上维护区间min，按右端点排序，每次让当前时间下车的牛能上的都上车。

右端点相同时，选左端点靠后的不会变差。

区间减就可以了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

const int maxn = 20005;
const int maxm = 50005;

struct grp
{
	int l, r, cnt;
	bool operator < (const grp &rhs) const
	{
		return (r == rhs.r) ? (l > rhs.l) : (r < rhs.r);
	}
}cow[maxm];
int n, m, c;
int b[maxn];
int mn[maxn << 2], tag[maxn << 2], ans;

inline int rd()
{
	register int x = 0; register char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
	return x;
}
inline void pushdown(int cur)
{
	if(tag[cur])
	{
		mn[cur << 1] += tag[cur], mn[cur << 1|1] += tag[cur];
		tag[cur << 1] += tag[cur], tag[cur << 1|1] += tag[cur];
		tag[cur] = 0;
	}
}
inline void pushup(int cur)
{
	mn[cur] = min(mn[cur << 1], mn[cur << 1|1]);
}
void update(int cur, int l, int r, int L, int R, int c)
{
	if(L <= l && r <= R)
	{
		mn[cur] += c; tag[cur] += c;
		return;
	}
	int mid = (l + r) >> 1; pushdown(cur);
	if(L <= mid) update(cur << 1, l, mid, L, R, c);
	if(R > mid) update(cur << 1|1, mid + 1, r, L, R, c);
	pushup(cur);
}
int query(int cur, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return mn[cur];
	int mid = (l + r) >> 1, ret = 0x3f3f3f3f; pushdown(cur);
	if(L <= mid) ret = query(cur << 1, l, mid, L, R);
	if(R > mid) ret = min(ret, query(cur << 1|1, mid + 1, r, L, R));
	return ret;
}

int main()
{
	m = rd(); n = rd(); c = rd();
	for(int i = 1; i <= m; ++i)
		cow[i].l = rd(), cow[i].r = rd(), cow[i].cnt = rd();
	sort(cow + 1, cow + 1 + m);
	update(1, 1, n, 1, n, c);
	for(int i = 1; i <= m; ++i)
	{
		int now = query(1, 1, n, cow[i].l, cow[i].r - 1);
		int delta = min(cow[i].cnt, now);
		if(!delta) continue;
		else 
		{
			ans += delta; update(1, 1, n, cow[i].l, cow[i].r - 1, -delta);
		}
	}
	printf("%d\n", ans);
	return 0;
}

BZOJ 2216

决策单调性DP。

Description

给一个长度为$n$的序列 $a_1, a_2, \ldots, a_n$.

对于每一个 $i \in [1, n]$, 计算最小的非负整数$p$, 使得对于任意$j$, 有$a_j \le a_i + p - \sqrt{|i-j|}$.

Solution

第一眼以为是单调队列做的… 但其实信息没法转移的.

第一次做一般的决策单调性优化, 平时都是斜率优化或者四边形不等式之类的…

首先方程可以很容易的变个形: $p_i = min\{ a_j + \sqrt{|i-j|} - a_i \}$

我们来证明决策点的单调性.

考虑 $p_i$ 的最优决策点在 $g_i$. 那么有任意 $k > 0$, 满足$a_{g_i - k} + \sqrt{i - g_i + k} \le a_{g_i} + \sqrt{i - g_i}$.

然后sqrt的斜率是在降的, 因为 $\frac{d}{dx} \sqrt{x} = \frac{1}{2\sqrt{x}}$.

这样的话，我们将决策点向前移动时，就会有：

$\because i - g_i + k > i - g_i$

$\therefore \sqrt{i + 1 - g_i + k} - \sqrt{i - g_i + k} < \sqrt{i - g_i} - \sqrt{i + 1 - g_i}$

$\therefore a_{g_i - k} + \sqrt{i + 1 - g_i + k} < a_{g_i} + \sqrt{i + 1 - g_i}$

也就是说， 在当前决策最优的情况下，下一位的决策点一定不会后退。

这样我们在求解出一个 $p_i$ 后, 就可以二分地更新它可以作为后面多少个位置的决策点了.

用一个三元组表示 $pos$ 决策点的有效区间 $[l, r]$, 在单调队列/单调栈中维护即可.

这是通常意义的决策单调性优化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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

const int maxn = 5e+5 + 5;

struct node
{
    int l, r, pos;
}q[maxn];
int n, a[maxn];
double f[maxn], g[maxn];

inline int rd()
{
    register int x = 0; register char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
}
double calc(int x, int y)
{
    return a[x] + sqrt(abs(x - y)) - a[y];
}
int bins(node x, int y)
{
    int l = x.l, r = x.r;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(calc(x.pos, mid) > calc(y, mid))
            l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
void solve(double *dp)
{
    int hd = 1, tl = 0;
    for(int i = 1; i <= n; ++i)
    {
        q[hd].l++;
        if(hd <= tl && q[hd].r < q[hd].l) hd++;
        if(hd > tl || calc(i, n) > calc(q[tl].pos, n))
        {
            while(hd <= tl && calc(q[tl].pos, q[tl].l) < calc(i, q[tl].l))
                tl--;
            if(hd > tl)
                q[++tl] = (node){i, n, i};
            else
            {
                int t = bins(q[tl], i);
                q[tl].r = t - 1;
                q[++tl] = (node){t, n, i};
            }
        }
        dp[i] = calc(q[hd].pos, i);
    }
}

int main()
{
    n = rd();
    for(int i = 1; i <= n; ++i) a[i] = rd();
    solve(f);
    reverse(a + 1, a + 1 + n);
    solve(g);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", max(0, (int)ceil(max(f[i], g[n - i + 1]))));
    return 0;
}

Orz 黄学长, Miracle

BZOJ 5055

膜法树状数组.

Description

给定长度为 $n$ 的序列 $a[]$.

求出所有满足$i<j<k$ 且 $a_i<a_j<a_k$ 的 $a_i \times a_j \times a_k$ 的和

即求 $\sum_{i < j < k \wedge a_i < a_j < a_k} {a_i \times a_j \times a_k}$.

Solution

开始的想法是先求出一个数后面比他大的数的和， 计算出 $a_j \times a_k$ 那一部分，然后再做一次同样的事，计算第一个数。

但其实有个更好想也好写的做法。就是直接把前面比这个数小的，后面比这个数大的，和自己乘起来，就可以直接累加答案了。

树状数组维护即可。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdlib>
#include <utility>
#include <set>
#include <cctype>

typedef long long ll;

using namespace std;

const ll p = 19260817;
const int maxn = 3e+5 + 5;

int n, a[maxn], cpy[maxn], rev[maxn], tot;
ll presum[maxn], sufsum[maxn], ans;

struct BIT
{
	ll b[maxn];
	BIT() {memset(b, 0, sizeof b);}
	inline void add(int x, ll c) {for(;x<=tot;x+=(x&-x)) b[x] = (b[x] + c) % p;}
	inline ll query(int x){ll ret(0); for(;x;x-=(x&-x)) ret = (ret + b[x]) % p; return ret;}
}bmn, bmx;

inline int rd()
{
	register int x = 0; register char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
	return x;
}

int main()
{
	n = rd();
	for(int i = 1; i <= n; ++i) a[i] = cpy[i] = rd();
	sort(cpy + 1, cpy + 1 + n);
	tot = unique(cpy + 1, cpy + 1 + n) - (cpy + 1);
	for(int i = 1; i <= n; ++i)
	{
		int p = lower_bound(cpy + 1, cpy + 1 + tot, a[i]) - cpy;
		rev[p] = a[i]; a[i] = p;
	}
	for(int i = 1; i <= n; ++i)
	{
		presum[i] = bmn.query(a[i] - 1);
		bmn.add(a[i], rev[a[i]] % p);
	}
	for(int i = n; i >= 1; --i)
	{
		sufsum[i] = (bmx.query(tot) - bmx.query(a[i]) + p) % p;
		bmx.add(a[i], rev[a[i]] % p);
	}
	for(int i = 1; i <= n; ++i)
		ans = (ans + presum[i] * sufsum[i] % p * (ll)rev[a[i]] % p) % p;
	printf("%lld\n", ans);
	return 0;
}