JOISC 2019 Day3 穿越时空 Bitaro 题解

First Post:

Last Update:

比较套路的穿越时空题，但也有些妙处。

下文假设询问的起点下标小于终点，大于的把序列翻转再做一遍即可。

首先考虑平方怎么做，因为 Bitaro 可以原地等待，所以任何的绕路方法肯定不优，于是 Bitaro 只可能笔直地走到终点。维护两个变量 与 ，枚举走过的每条路进行更新，暴力代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline ll Query(int st, int stm, int ed, int edm) {
    assert(st < ed);
    int tim = stm;
    ll ans = 0;
    for (int i = st; i < ed; i++) {
        if (tim < L[i])
            tim = L[i];
        else if (tim >= R[i])
            ans += tim - R[i] + 1, tim = R[i] - 1;

        ++tim;
    }
    ans += max(0, tim - edm);
    return ans;
}

考虑如何加速这个过程。首先这里有个 ，这么一个突兀的常数让我们分析起来不是很方便。所以可以考虑把 ，相当于把在 点的时间向前平移了 个单位，这样我们从 走到 时就不用考虑 的问题了。（ 减 是因为题中给的是左闭右开区间）

接下来看 是如何变化的，我们设 表示走过路 后，原时间为 ，现在会变成啥，容易得到： 我们简称上述过程为 “把 向 取整”。

顺便设 表示走过 中的路后，原来的 会变成啥。

观察 的函数形态。如果所有 （其中 ） 的交集不为空，那么其也是一个区间 ，设为 ，那么， 在整个过程中，是不可能从 这个区间的一边跑到另一边的，而且最后肯定会停在 之中。那么发现， 这个函数对 的作用，就相当于把 对 取整！也就是说，这 个区间与区间 是完全等效的，不管是对 还是对 的作用。

这有什么用呢？有很多 不满足上面的情况。但我们可以考虑设 表示最大的 使得区间 中的所有 交集不为空，并求出其对应的 。那么对于 ，其就有两种情况： 或 ，两种情况是对称的，以第一种为例。

如果 ，那么不管输入的 是啥，此时都会变成 ，也就是说，最终的 以及 以后的区间对 的贡献已经确定，可以直接用两个值记录下来！

做到这里就可以使用数据结构维护了。这里选用更好理解的分块。我们对每一块 维护最大的 使得 中的所有区间都有交，并维护其对应的 。如果 ，那么再记录最终的 以及 以后对 的贡献。代码实现时可以直接记录三个一次函数，分别表示 时对 的贡献。修改时暴力重构所属块，查询时一块一块跳过去即可。时间复杂度 。

其实这个信息应该也可以使用线段树维护，但较麻烦。

于是本题就做完了！其实选的数据结构并不重要，关键在于本题的操作性质非常优秀，使得一个区间中的信息可以 用 的空间记录。这是妙处所在。

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 3e5 + 5;
typedef long long ll;
#define FI first
#define SE second
#define mkp make_pair
int n,Q;
int orl[N],orr[N];
int L[N],R[N];
int tp[N];
int cp[N],cx[N],cy[N];
int st[N],stm[N],ed[N],edm[N];


// 分块
const int B = 455;
int kl[N],kr[N],pos[N];
int ftl[N],ftr[N];
int kk[N][3];ll kb[N][3]; // 在 ftl,ftr 所分三段中的一次函数
bool osp[N];
int edp[N];
inline int Tl(int id) { return L[id] - id;}
inline int Tr(int id) { return R[id] - 1 - id;}
inline pair<long long,int> Brute(int tim,int l,int r) {
	ll ans = 0;
	for(int i = l;i <= r;i++) {
		if(tim < Tl(i)) tim = Tl(i);
		else if(tim > Tr(i)) ans += tim - Tr(i),tim = Tr(i);
	}
	return mkp(ans,tim);
}
inline void Rebuild(int id) {
	ftl[id] = Tl(kl[id]);ftr[id] = Tr(kl[id]);
	int &nl = ftl[id],&nr = ftr[id];
	for(int i = kl[id] + 1;i <= kr[id];i++) {
		if(Tl(i) <= nl && Tr(i) >= nl) { nr = min(nr,Tr(i));continue;}
		if(Tl(i) <= nr && Tr(i) >= nr) { nl = max(nl,Tl(i));continue;}
		if(nl <= Tl(i) && Tr(i) <= nr) { nl = Tl(i);nr = Tr(i);continue;}
		// 此时 ftl,ftr 与 li,ri 无交
		kk[id][0] = 0;kb[id][0] = 0;
		kk[id][2] = 1;kb[id][2] = -nr;
		if(Tr(i) < nl) {
			kk[id][1] = 1;kb[id][1] = -Tr(i);
			kb[id][0] += nl - Tr(i);kb[id][2] += nr - Tr(i);
			auto tmp = Brute(Tr(i),i + 1,kr[id]);
			osp[id] = false; // 没有贯穿一块
			kb[id][0] += tmp.FI;kb[id][1] += tmp.FI;kb[id][2] += tmp.FI;
			edp[id] = tmp.SE;
			return;
		}
		if(Tl(i) > nr) {
			kk[id][1] = kb[id][1] = 0;
			auto tmp = Brute(Tl(i),i + 1,kr[id]);
			kb[id][0] += tmp.FI;kb[id][1] += tmp.FI;kb[id][2] += tmp.FI;
			osp[id] = false;edp[id] = tmp.SE;
			return;
		}
		assert(0);
	}
	osp[id] = true;
}
inline pair<long long,int> pass_block(int id,int tim) {
	ll ans = 0;
	if(osp[id]) {
		if(tim < ftl[id]) tim = ftl[id];
		else if(tim >= ftr[id]) ans += ftr[id] - tim,tim = ftr[id];
		return mkp(ans,tim);
	}
	if(tim < ftl[id]) ans = kk[id][0] * tim + kb[id][0];
	else if(tim > ftr[id]) ans = kk[id][2] * tim + kb[id][2];
	else ans = kk[id][1] * tim + kb[id][1];
	return mkp(ans,edp[id]);
}

inline ll Query(int st,int stm,int ed,int edm) {
	assert(st < ed);
	stm -= st;edm -= ed;
	int p = pos[st],q = pos[ed - 1];
	if(p == q) { auto tmp = Brute(stm,st,ed - 1);return tmp.FI + max(0,tmp.SE - edm);}
	ll ans = 0;
	auto tmp = Brute(stm,st,kr[p]);
	ans += tmp.FI;stm = tmp.SE;
	for(int i = p + 1;i < q;i++) {
		auto tmp = pass_block(i,stm);
		ans += tmp.FI;stm = tmp.SE;
	}
	tmp = Brute(stm,kl[q],ed - 1);
	ans += tmp.FI;stm = tmp.SE;
	ans += max(0,stm - edm);
	return ans;
}
ll ans[N];
inline void work() {
	for(int i = 1;i <= n;i++) L[i] = orl[i],R[i] = orr[i];
	for(int i = 1;i <= pos[n - 1];i++) Rebuild(i);
	for(int i = 1;i <= Q;i++) 
		if(tp[i] == 1) {
			L[cp[i]] = cx[i];R[cp[i]] = cy[i];
			Rebuild(pos[cp[i]]);
		} 
		else if(st[i] < ed[i]) ans[i] = Query(st[i],stm[i],ed[i],edm[i]);
}
int main() {
	read(n);read(Q);
	for(int i = 1;i < n;i++) read(orl[i]),read(orr[i]);
	for(int i = 1;i < n;i++) pos[i] = (i - 1) / B + 1;
	for(int i = 1;i < n;i++) kr[pos[i]] = i;
	for(int i = n - 1;i >= 1;i--) kl[pos[i]] = i;

	for(int i = 1;i <= Q;i++) {
		read(tp[i]);
		if(tp[i] == 1) read(cp[i]),read(cx[i]),read(cy[i]);
		else read(st[i]),read(stm[i]),read(ed[i]),read(edm[i]);
	}
	work();
	reverse(orl + 1,orl + n);
	reverse(orr + 1,orr + n);
	for(int i = 1;i <= Q;i++)
		if(tp[i] == 1) cp[i] = n - cp[i];
		else st[i] = n - st[i] + 1,ed[i] = n - ed[i] + 1;
	work();
	for(int i = 1;i <= Q;i++) if(st[i] == ed[i]) ans[i] = max(0,stm[i] - edm[i]);
	for(int i = 1;i <= Q;i++) if(tp[i] == 2) write(ans[i]);
	return 0;
}
≡