AHOI/HNOI2018 转盘（线段树）

发表于 |
字数统计: 1,318字 | 阅读时长 ≈ 6min

「AHOI / HNOI2018」转盘

问题描述

一次小 G 和小 H 原本准备去聚餐，但由于太麻烦了于是题面简化如下：

一个转盘上有摆成一圈的 $n$ 个物品（编号 $1$ 至 $n$）其中第 $i$ 个物品会在 $T_i$ 时刻出现。

在 $0$ 时刻时,小 G 可以任选 $n$ 个物品中的一个，我们将其编号记为 $s_0$ 。并且如果 $i$ 时刻选择了物品 $s_i$ ，那么 $i + 1$ 时刻可以继续选择当前物品或者选择下一个物品。当 $s_i$ 为 $n$ 时，下一个物品为物品 $1$，否则下一个物品为 $s_{i + 1}$。在每一时刻（包括 $0$ 时刻），如果小 G 所选择的物品已经出现了，那么小 G 将会标记它。小 H 想知道，在物品选择的最优策略下，小 G 什么时候能标记所有物品？

但麻烦的是，物品的出现时间会不时修改。我们将其描述为 $m$ 次修改，每次修改将改变其中一个物品的出现时间。每次修改之后，你也需要求出当前局面的答案。对于其中部分测试点，小 H 还追加了强制在线的要求。

输入格式

第一行三个非负整数 $n,m,p$，代表一共有 $n$ 个物品，$m$ 次修改。$p$ 只有 $0$ 或 $1$ 两种取值，强制在线时 $p$ 为 $1$，否则为 $0$。本节后面将解释如何使用 $p$。

接下来一行，有 $n$ 个用空格隔开的非负整数，第 $i$ 个数 $T_i$ 代表物品 $i$ 的出现时间。

接下来 $m$ 行，每行两个非负整数 $x,y$，代表一次修改及询问。修改方式如下：

  • 如果 $p = 0$，则表示物品 $x$ 的出现时间 $T_x$ 修改为 $y$。
  • 如果 $p = 1$，则先将 $x$ 和 $y$ 分别异或 $LastAns$ 得到 $x′$ 和 $y′$：即 $x′ = x \oplus LastAns, y′ = y \oplus LastAns$。然后将物品 $x′$ 的出现时间 $T_{x′}$ 修改为 $y′$ 。其中的 $LastAns$ 是前一个询问的答案；特别的，第一次修改时的 $LastAns$ 为初始局面的答案。其中的 $\oplus$ 为按位异或运算，例如 $1 \oplus 2 = 3,4 \oplus 5 = 1,6 \oplus 11 = 13$。

保证输入合法。

输出格式

第一行一个整数代表初始局面的答案。

接下来 $m + 1$ 行每行一个整数分别代表每次修改后的答案。

样例输入

5 3 0
1 2 3 4 5
3 5
5 0
1 4

样例输出

5
7
6
7

提示

首先可以发现一定存在一种最优解是从某个点开始，等一段时间，然后一步不停的走完一圈。

那么将序列倍长，我们要求的答案即是$Min_{i=1}^{n}{Max_{j=i}^{2n}{T_j-j+i+n-1}}$

化简一下得到$Min_{i=1}^{n}{Max_{j=i}^{2n}{T_j-j}+i}+n-1$，考虑用线段树来维护。

每个节点上分别维护$Max$和$Min$，其中$Max=Max_{j=l}^{r}{T_j-j}$，$Min=Min_{i=l}^{mid}{Max_{j=i}^{r}{T_j-j}+i}$

Max很容易维护，主要考虑维护Min

可以通过一个查询$Query(l,mid,Rmax)$来实现这一点，每次比较一下右儿子的$Max$和$Rmax$的大小关系，如果$Max>=Rmax$那么返回左儿子的$Min$与右儿子查询的结果的较小者。否则返回左儿子查询结果与$mid+1$处答案的较小者。

这样做的时间复杂度是$O(n \log^2 n)$，可以接受。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,m,ty,T[N];
struct node
{
	node *ls,*rs;
	int Max,Min;
}Seg[N<<2],*rt,*tl,*null;
void Init()
{
	rt=tl=null=&Seg[0];
	null->ls=null->rs=null;
}
int GM(node *p,int l,int r,int k)
{
	if(l==r)return l+max(k,p->Max);
	int mid=l+r>>1;
	if(k>=p->rs->Max)return min(mid+1+k,GM(p->ls,l,mid,k));
	return min(p->Min,GM(p->rs,mid+1,r,k));
}
void MT(node *p,int l,int r)
{
	p->Max=max(p->ls->Max,p->rs->Max);
	p->Min=GM(p->ls,l,l+r>>1,p->rs->Max);
}
void MD(node *p,int l,int r,int k)
{
	if(l==r){p->Max=T[l]-l;p->Min=T[l];return;}
	int mid=l+r>>1;
	if(k<=mid)MD(p->ls,l,mid,k);
	else MD(p->rs,mid+1,r,k);
	MT(p,l,r);
}
void BT(node *&p,int l,int r)
{
	p=++tl;p->ls=p->rs=null;
	if(l==r){p->Max=T[l]-l;p->Min=T[l];return;}
	int mid=l+r>>1;
	BT(p->ls,l,mid);
	BT(p->rs,mid+1,r);
	MT(p,l,r);
}
int main()
{
	int i,j,k,x,y,ans;
	_R(n);_R(m);_R(ty);
	for(i=1;i<=n;i++)_R(T[i]),T[i+n]=T[i];
	Init();BT(rt,1,n+n);
	printf("%d\n",ans=rt->Min+n-1);
	for(i=1;i<=m;i++)
	{
		_R(x);_R(y);
		x^=ty*ans;y^=ty*ans;
		T[x]=T[x+n]=y;
		MD(rt,1,n+n,x);
		MD(rt,1,n+n,x+n);
		printf("%d\n",ans=rt->Min+n-1);
	}
}