bzoj5286:[Hnoi2018]转盘(线段树)

Author Avatar
Sakits 6月 24, 2018

题解

  首先我一眼就看出了一个结论,肯定是在起点等待一段时间后走一圈完成,然后我就不会做了…
  环的话先倍增,然后这题就变成了求:

min(i+max(aj)),ijmin(i+max(a_j)), i\leq j

  学到了一个线段树的船新操作。大概是对于需要对每个点都维护后缀信息的线段树,可以变成每个节点只维护当前区间,在这题里就是维护区间最值和区间上式。询问的时候用右区间来更新左区间的答案,更新的方法就是递归左区间,找到需要修改的答案的位置即可,需要注意的是,递归进某个区间的时候,必须能够O(1)O(1)知道另外一个区间的答案,所以这题里面,我们对每个区间选择维护:

min(i+max(aj)),lijmidmin(i+max(a_j)), l\leq i\leq j\leq mid

  这样的话递归进右区间的时候,左区间的答案可以直接通过这整个区间维护的值来得到,而递归进左区间的时候,右区间的答案可以直接通过mid+1+mxmid+1+mx来得到,所以对每个区间只会以一条路径走到叶子节点,复杂度为O(nlog2n)O(nlog^2n)

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=500010, inf=1e9;
struct sgt{int mx, mn;}tree[maxn<<2];
int n, m, p, x, y;
int a[maxn];
 
template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
 
int find(int x, int mx, int l, int r)
{
//  printf("l:%d r:%d tree[x].mx:%d tree[x].mn:%d %d\n", l, r, tree[x].mx, tree[x].mn, mx);
	if(l==r) return l+max(tree[x].mx, mx);
	int mid=(l+r)>>1;
	if(tree[x<<1|1].mx>mx) return min(tree[x].mn, find(x<<1|1, mx, mid+1, r));
	return min(mid+1+mx, find(x<<1, mx, l, mid));
}
 
void up(int x, int l, int r)
{
	int mid=(l+r)>>1;
	tree[x].mx=max(tree[x<<1].mx, tree[x<<1|1].mx);
	tree[x].mn=find(x<<1, tree[x<<1|1].mx, l, mid);
}
 
void build(int x, int l, int r)
{
	if(l==r) {tree[x].mx=a[l]; tree[x].mn=l+a[l]; return;}
	int mid=(l+r)>>1;
	build(x<<1, l, mid); build(x<<1|1, mid+1, r);
	up(x, l, r);
}
 
void update(int x, int l, int r, int cx, int delta)
{
	if(l==r) {tree[x].mx=delta; tree[x].mn=l+delta; return;}
	int mid=(l+r)>>1;
	if(cx<=mid) update(x<<1, l, mid, cx, delta);
	else update(x<<1|1, mid+1, r, cx, delta);
	up(x, l, r);
//  printf("x:%d l:%d r:%d tree[x].mn:%d\n", x, l, r, tree[x].mn);
}
 
int main()
{
//  freopen("1.in", "r", stdin);
//  freopen("1.out", "w", stdout);
	read(n); read(m); read(p);
	for(int i=1;i<=n;i++) read(a[i]), a[i+n]=a[i];
	for(int i=1;i<=(n<<1);i++) a[i]-=i;
	build(1, 1, n<<1); 
	int lastans=tree[1].mn+n-1;
	printf("%d\n", lastans);
	for(int i=1;i<=m;i++)
	{
		read(x); read(y);
		if(p) x^=lastans, y^=lastans;
		update(1, 1, n<<1, x+n, y-x-n);
		update(1, 1, n<<1, x, y-x);
		printf("%d\n", lastans=tree[1].mn+n-1);
	}
}