关键词:STST表   二分查找 相关题目:[ZJOI2018]胖

O2优化 时间限制:3000ms 空间限制:512MB

题目描述

    Cedyks 是九条可怜的好朋友(可能这场比赛公开以后就不是了),也是这题的主人公。

    Cedyks 是一个富有的男孩子。他住在著名的The Place(宫殿)中。

    Cedyks 是一个努力的男孩子。他每天都做着不一样的题来锻炼他的The Salt(灵魂)。

    这天,他打算在他的宫殿外围修筑一道城墙,城墙上有 nn 座瞭望塔。你可以把城墙看做一条线段,瞭望塔是线段上的 nn 个点,其中 11nn 分别为城墙的两个端点。其中第 ii 座瞭望塔和第 i+1i + 1 座瞭望塔的距离为 wiw_i​ ,他们之间的道路是双向的。

    城墙很快就修建好了,现在Cedyks 开始计划修筑他的宫殿到城墙的道路。因为这题的题目名称,Cedyks 打算用他的宫殿到每一个瞭望塔的最短道路之和来衡量一个修建计划。

    现在Cedyks 手上有 mm 个设计方案,第 kk 个设计方案会在宫殿和瞭望塔之间修建 TkT_k​ 条双向道路,第 ii 条道路连接着瞭望塔 aia_i ,长度为 lil_i​ 。

    计算到每一个瞭望塔的最短路之和是一个繁重的工程,本来Cedyks 想用广为流传的SPFA算法来求解,但是因为他的butter(缓冲区)实在是太小了,他只能转而用原始的贝尔福特曼算法来计算,算法的流程大概如下:

  1. 定义宫殿是 00 号点,第 ii 个瞭望塔是 ii 号点,双向边 (ui,vi,li)(u_i, v_i, l_i) 为一条连接 uiu_i​ 和 viv_i​ 的双向道路。令 dd 为距离数组,最开始
  2. 令辅助数组 c=dc = d 。依次对于每一条边 (ui,vi,wi)(u_i, v_i,w_i) 进行增广, cui=min(cui,dvi+wi)c_{u_i} = min(c_{u_i} , d_{v_i} + w_i)cvi=min(cvi,dui+wi)c_{v_i} = min(c_{v_i} , d_{u_i} + w_i)
  3. ttccdd 中不一样的位置个数,即令 ,则 t=St = |S| 。若 t=0t = 0 ,说明 dd 就是最终的最短路,算法结束。否则令 d=cd = c ,回到第二步。

    因为需要计算的设计方案实在是太多了,所以Cedyks 雇佣了一些人来帮他进行计算。为了避免这些人用捏造出来的数据偷懒,他定义一个设计方案的校验值为在这个方案上运行贝尔福特曼算法每一次进入第三步 tt 的和。他会让好几个雇佣来的人计算同样的设计方案,并比对每一个人给出的校验值。

    你是Cedyks 雇佣来的苦力之一,聪明的你发现在这个情形下计算最短路的长度的和是一件非常简单的事情。但是寄人篱下不得不低头,你不得不再计算出每一个方案的校验值来交差。

输入输出格式

输入格式: 第一行输入两个整数 n,mn,m ,表示瞭望塔个数和设计方案个数。 接下来一行 n1n - 1 个数 wiw_i ,表示瞭望塔 iii+1i + 1 之间道路的长度。 接下来 mm 行,每行描述一个设计方案。第一个整数 KK 表示设计方案中的道路数量,接下来 KK 个数对 (ai,li)(a_i, l_i) 为一条宫殿到瞭望塔的边。

输出格式: 对于每一个设计方案,输出一行一个整数表示校验值。

输入样例:

5 5
2 3 1 4
1 2 2
2 1 1 4 10
3 1 1 3 1 5 1
3 1 10 2 100
5 15 1 1 2 1 3 1 4 1 5 1

输出样例:

5
8
5
8
5

样例解释

  • 对于第一个设计方案,每一个阶段 dd 的变化为:

[0,1018,1018,1018,1018,1018][0,1018,2,1018,1018,1018][0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,10^{18},2,10^{18},10^{18},10^{18}] \rightarrow [0,4,2,5,1018,1018][0,4,2,5,6,1018][0,4,2,5,6,10][0,4,2,5,10^{18},10^{18}] \rightarrow [0,4,2,5,6,10^{18}] \rightarrow [0,4,2,5,6,10]

因此校验值为 1+2+1+1=51+2+1+1=5

  • 对于第二个设计方案,每一个阶段 dd 的变化为: [0,1018,1018,1018,1018,1018][0,1,1018,1018,10,1018][0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,10^{18},10^{18},10,10^{18}] \rightarrow [0,1,3,11,10,14][0,1,3,6,10,14][0,1,3,6,7,14][0,1,3,6,7,11][0,1,3,11,10,14] \rightarrow [0,1,3,6,10,14] \rightarrow [0,1,3,6,7,14] \rightarrow [0,1,3,6,7,11]

因此校验值为 2+3+1+1+1=82+3+1+1+1=8

  • 对于第三个设计方案,每一个阶段 dd 的变化为: [0,1018,1018,1018,1018,1018][0,1,1018,1,1018,1][0,1,3,1,2,1][0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,10^{18},1,10^{18},1] \rightarrow [0,1,3,1,2,1]

因此校验值为 3+1+1=53+1+1=5

  • 对于第四个设计方案,每一个阶段 dd 的变化为: [0,1018,1018,1018,1018,1018][0,10,100,1018,1018,1][0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,10,100,10^{18},10^{18},1] \rightarrow [0,10,12,103,5,1][0,10,12,6,5,1][0,10,9,5,1][0,10,12,103,5,1] \rightarrow [0,10,12,6,5,1] \rightarrow [0,10,9,5,1]

因此校验值为 3+3+1+1=83+3+1+1=8

  • 对于第五个设计方案,每一个阶段 dd 的变化为: [0,1018,1018,1018,1018,1018][0,1,1,1,1,1][0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,1,1,1,1]

因此校验值为 55

数据范围

测试点nn</th>mm</th>KK</th>其他约定
1,21000\le 1000</td>1000\le 1000</td>100\le 100</td>
3,42×105\le 2 \times 10^5</td>2×105\le 2 \times 10^5</td>100\le 100</td>
5,62×105\le 2 \times 10^5</td>2×105\le 2 \times 10^5</td>2×105\le 2 \times 10^5</td>1wi,li501 \le w_i,l_i \le 50</td>
7,8,9,102×105\le 2 \times 10^5</td>2×105\le 2 \times 10^5</td>2×105\le 2 \times 10^5</td>

对于 100%100\% 的数据,保证每个设计方案 aia_i​ 两两不同且 1ain1\le a_i\le n 。 对于 100%100\% 的数据,保证 1wi,li109,1K2×1051\le w_i,l_i\le 10^9,1\le\sum K\le 2\times 10^5

AC代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
const int N = 200020;
inline void read(int &x) {
x = 0;
int f = 1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f = -1; ch = getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48); ch = getchar();}
x *= f;
}

int n, m, k;
int bit[20], lg[N], st1[N][20], st2[N][20];
ll ma[N], mi[N];
ll s[N];
inline void _init() {
int x;
bit[0] = 1, lg[1] = 0;
rep(i,2,n) {
read(x), s[i] = s[i-1]+x;
lg[i] = lg[i/2] + 1;
}
rep(i,1,18) bit[i] = bit[i-1]*2;
}

inline int Max(int a, int b) {
if(ma[a] == ma[b]) return max(a, b);
return ma[a] > ma[b] ? a : b;
}
inline int Min(int a, int b) {
if(mi[a] == mi[b]) return min(a, b);
return mi[a] < mi[b] ? a : b;
}
inline int getmax(int l, int r) {
int t = lg[r-l+1];
return Max(st1[l][t], st1[r-bit[t]+1][t]);
}
inline int getmin(int l, int r) {
int t = lg[r-l+1];
return Min(st2[l][t], st2[r-bit[t]+1][t]);
}

struct node {
int id, w;
node() {};
node(int _id, int _w) {id = _id, w = _w;}
inline bool operator < (const node &rhs)const {
return id < rhs.id;
}
} t[N];

inline void init() {
sort(t+1, t+k+1);
rep(i,1,k) {
ma[i] = s[t[i].id] - t[i].w;
mi[i] = s[t[i].id] + t[i].w;
st1[i][0] = st2[i][0] = i;
}
rep(l,1,lg[k])
for(re i=1;i+bit[l]-1<=k;++i) {
st1[i][l] = Max(st1[i][l-1], st1[i+bit[l-1]][l-1]);
st2[i][l] = Min(st2[i][l-1], st2[i+bit[l-1]][l-1]);
}
}

inline void Chkbet(int &bet, int test, int m) {
ll ans1 = (ll)t[bet].w + abs(s[t[bet].id] - s[m]);
ll ans2 = (ll)t[test].w + abs(s[t[test].id] - s[m]);
if(ans1 != ans2)
bet = ans1 < ans2 ? bet : test;
else if(abs(t[bet].id - m) != abs(t[test].id - m))
bet = abs(t[bet].id - m) < abs(t[test].id - m) ? bet : test;
else bet = min(bet, test);
}

inline int check(int m, int i) {
int d = abs(t[i].id - m), bet = i;
int l, r, mid;
l = lower_bound(t+1, t+k+1, node(m-d, 0)) - t;
r = upper_bound(t+1, t+k+1, node(m+d, 0)) - t-1;
mid = upper_bound(t+1, t+k+1, node(m, 0)) - t-1;
if(l <= mid) Chkbet(bet, getmax(l,mid), m);
if(bet != i) return 0;
if(mid < r) Chkbet(bet, getmin(mid+1,r), m);
return bet == i;
}

inline ll solve() {
ll ans = 0;
int l, r, L, R, mid;
rep(i,1,k) {
l = 1, r = t[i].id;
while(l < r)
if(check(mid = (l+r)>>1, i)) r = mid;
else l = mid + 1;
L = l;

l = t[i].id, r = n;
while(l < r)
if(check(mid = (l+r+1)>>1, i)) l = mid;
else r = mid - 1;
R = r;
ans += R-L+1;
}
return ans;
}

signed main() {
read(n), read(m);
_init();
while(m--) {
read(k);
rep(i,1,k) read(t[i].id), read(t[i].w);
init();
printf("%lld\n", solve());
}
}

相关题目: [ZJOI2018]线图 [ZJOI2018]历史 [ZJOI2018]迷宫 [ZJOI2018]树 [ZJOI2018]保镖