[HNOI/AHOI2018]转盘

[HNOI/AHOI2018]转盘

题目大意：

一个环上有(n(nle10^5))个物品。在时间为(0)的时候，你可以任选一个点作为起点出发。每秒钟你可以选择留在当前点或走到下一个点。每个物品有一个出现的时间(t_i)。对于每一时刻，若当前位置上的物品已经出现了，则可以获得该物品。问何时可以获得所有物品。

另有(m(mle10^5))次修改操作，对于每次修改(t_x=y)，求出修改后的答案。强制在线。

思路：

将环复制一遍接在(n)的后面，变成一个链。

设起点(iin[n,2n))，往前走到(jin(i-n,i])。设我们在时刻(s)到达(j)，并获得(j)上的物品。那么我们可以知道(s-(i-j)ge t_j)，因此(s_{min}=max{t_j-j}+i)。

令(a_i=t_i-i)，(displaystyle ans=min_{iin[n,2n)}{max_{jin(i-n,i]}a_j+i}=min_{iin[1,n]}{max_{jin[i,2n]}a_j+i}+n-1)。使用线段树维护单调栈即可。时间复杂度(mathcal O(nlog^2 n))。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=1e5+1;
struct SegmentTree {
	#define _left <<1
	#define _right <<1|1
	int max[N<<2],val[N<<2];
	int query(const int &p,const int &b,const int &e,const int &x) const {
		if(b==e) return max[p]>x?x+b:INT_MAX;
		const int mid=(b+e)>>1;
		return max[p _right]>x?std::min(val[p],query(p _right,mid+1,e,x)):query(p _left,b,mid,x);
	}
	void push_up(const int &p,const int &b,const int &e) {
		const int mid=(b+e)>>1;
		max[p]=std::max(max[p _left],max[p _right]);
		val[p]=query(p _left,b,mid,max[p _right]);
	}
	void build(const int &p,const int &b,const int &e) {
		if(b==e) {
			max[p]=getint()-b;
			return;
		}
		const int mid=(b+e)>>1;
		build(p _left,b,mid);
		build(p _right,mid+1,e);
		push_up(p,b,e);
	}
	void modify(const int &p,const int &b,const int &e,const int &x,const int &y) {
		if(b==e) {
			max[p]=y-b;
			return;
		}
		const int mid=(b+e)>>1;
		if(x<=mid) modify(p _left,b,mid,x,y);
		if(x>mid) modify(p _right,mid+1,e,x,y);
		push_up(p,b,e);
	}
	#undef _left
	#undef _right
};
SegmentTree t;
int main() {
	const int n=getint(),m=getint(),p=getint();
	t.build(1,1,n);
	int ans;
	printf("%d
",ans=t.query(1,1,n,t.max[1]-n)+n);
	for(register int i=0;i<m;i++) {
		const int x=getint()^(ans*p),y=getint()^(ans*p);
		t.modify(1,1,n,x,y);
		printf("%d
",ans=t.query(1,1,n,t.max[1]-n)+n);
	}
	return 0;
}