一个nn元环，在00时刻从任意一个位置出发，每一秒可以选择往后或者留在原地

每个点有个参数TiT_i，当你走到ii的时间t≥Tit\ge T_i时就可以把ii标记

求把整个环上的点都标记最小需要多长时间，需要支持TiT_i修改,强制在线

3≤n≤105,0≤m≤105,0≤Ti/Tx≤1053\le n\le 10^5, 0\le m\le 10^5, 0\le T_i/T_x\le 10^5

Luogu P4425

Solution

感性考虑一下可以发现最优方案肯定是现在所选起点停留足够长时间再往后直接走一圈

破环为链后实际上是求mini=1n{maxj=ii+n−1{Tj−(j−i+1)+n}}\min_{i=1}^{n} \{\max_{j=i}^{i+n-1} \{T_j-(j-i+1)+n\}\}

可以转化成mini=1n{maxj=i2n{Tj−j}+i+n−1}\min_{i=1}^{n} \{\max_{j=i}^{2n} \{T_j-j\}+i+n-1\}

设aj=Tj−ja_j=T_j-j，化简得到mini=1n{maxj=i2n{aj}+i}+n−1\min_{i=1}^{n} \{\max_{j=i}^{2n} \{a_j\}+i\}+n-1

考虑用线段树维护这个东西

对于当前根rootroot对应的区间[L,R][L,R]，考虑如何维护val[root]=mini=Lmid{maxj=iR{aj}+i}val[root]=\min_{i=L}^{mid} \{\max_{j=i}^{R} \{a_j\}+i\}

定义query(L,R,suf)query(L,R,suf)计算mini=LR{max{maxj=iR{aj},suf}+i}\min_{i=L}^{R} \{\max\{\max_{j=i}^{R} \{a_j\},suf\}+i\}

那么有val[root]=query(L,mid,max[rson])val[root] = query(L, mid, max[rson]) （其中max[root]max[root]表示区间最大值）

考虑如何计算query(L,R,suf)query(L,R,suf)

可以发现，若suf≤max[rson]suf\le max[rson]，则val[root]val[root]就等于左儿子的答案，于是只需要递归右儿子

否则mid+1+sufmid+1+suf就等于右儿子的答案，此时只需要递归左儿子

（以上两个结论都很好证明，直接带到原式中观察一下就能发现是对的）

那么就能在O(logn)O(\log n)的时间内求出queryquery的值了

总复杂度O(nlog2n)O(n\log ^2n)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 2e5 + 100;

int N, M, P, A[Maxn];

namespace SEG
{
#define ls Tree[root << 1]
#define rs Tree[root << 1 | 1]
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
	struct tree
	{
		int val, max;
	}Tree[Maxn << 2];

	inline int query (int root, int l, int r, int suf)
	{
		if (l == r) return Tree[root].val = max (Tree[root].max, suf) + l;
		int mid = l + r >> 1;
		if (suf <= rs.max) return min (Tree[root].val, query (rson, suf));
		return min(query (lson, suf), suf + mid + 1);
	}

	inline void push_up (int root, int l, int r, int mid)
	{
		Tree[root].max = max(ls.max, rs.max);
		Tree[root].val = query (lson, rs.max);
	}

	inline void build (int root, int l, int r)
	{
		if (l == r)
		{
			Tree[root].max = A[l], Tree[root].val = A[l] + l;
			return ;
		}
		int mid = l + r >> 1;
		build (lson), build (rson);
		push_up (root, l, r, mid);
	}

	inline void update (int root, int l, int r, int x)
	{
		if (l == r)
		{
			Tree[root].max = A[l], Tree[root].val = A[l] + l;
			return ;
		}
		int mid = l + r >> 1;
		if (x <= mid) update (lson, x);
		else update (rson, x);
		push_up (root, l, r, mid);
	}
}

inline void Solve ()
{
/**/SEG :: build (1, 1, N << 1);
	int ans = SEG :: Tree[1].val + N - 1;
	cout<<ans<<endl;
	while (M--)
	{
		int x = read(), y = read();
		if (P) x ^= ans, y ^= ans;
		A[x] = y - x, A[x + N] = y - x - N;
		SEG :: update (1, 1, N << 1, x), SEG :: update (1, 1, N<< 1, x + N);
		printf("%d\n", ans = SEG :: Tree[1].val + N - 1);
	}
}

inline void Input ()
{
	N = read(), M = read(), P = read();
	for (int i = 1; i <= N; ++i) A[i] = read() - i, A[i + N] = A[i] - N;
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

Debug

  • 89L, 97L: n<<1写成1<<n。。。