题解

（请在此补充题目的中文题解与思路描述。）

#include <cstdio>
#define min(A, B) (A < B ? A : B)
#define max(A, B) (A < B ? B : A)
#define minx(A, B) (A = min(A, B))
#define INF 1e9

const int MX = 100010;

int t[MX];

namespace solve
{
namespace sgt
{
int mn[MX << 3], mn2[MX << 3], mx[MX << 3], n;

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

void push_up(int p, int cl, int cr)
{
	if (mx[ls(p)] <= mx[rs(p)])
		mn[p] = cl + mx[rs(p)],
		mn2[p] = cl + mx[rs(p)];
	else
	{
		int t = ls(p), mid = (cl + cr) >> 1;
		cr = mid;
		mn2[p] = INF;
		while (cl != cr)
		{
			mid = (cl + cr) >> 1;
			if (mx[rs(t)] <= mx[rs(p)])
				minx(mn2[p], mid + 1 + mx[rs(p)]),
				t = ls(t),
				cr = mid;
			else
				minx(mn2[p], mn2[t]),
				t = rs(t),
				cl = mid + 1;
		}
		minx(mn2[p], mn[t]);
		mn[p] = min(mn2[p], mn[rs(p)]);
	}
	mx[p] = max(mx[ls(p)], mx[rs(p)]);
}

void build(int arr[], int p = 1, int cl = 1, int cr = n)
{
	if (cl == cr)
		mn[p] = cl + arr[cl],
		mn2[p] = INF,
		mx[p] = arr[cl];
	else
	{
		int mid = (cl + cr) >> 1;
		build(arr, ls(p), cl, mid);
		build(arr, rs(p), mid + 1, cr);
		push_up(p, cl, cr);
	}
}

void update(int x, int v, int p = 1, int cl = 1, int cr = n)
{
	if (cl == cr)
		mn[p] = cl + v,
		mx[p] = v;
	else
	{
		int mid = (cl + cr) >> 1;
		if (x <= mid)
			update(x, v, ls(p), cl, mid);
		else
			update(x, v, rs(p), mid + 1, cr);
		push_up(p, cl, cr);
	}
}

int query()
{
	return mn2[1];
}

#undef ls
#undef rs
}

int n;

void init(int n)
{
	solve::n = n;
	static int arr[MX << 1];
	for (int i = 1; i <= n; arr[i] = t[i] - i, arr[i + n] = t[i] - i - n, i++);
	sgt::n = n << 1;
	sgt::build(arr);
}

void set(int p, int x)
{
	sgt::update(p, x - p);
	sgt::update(p + n, x - p - n);
}

int query()
{
	return n - 1 + sgt::query();
}
}

int main()
{
	int n, m, p, x, y;
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= n; scanf("%d", t + i++));
	solve::init(n);
	int lst = solve::query();
	printf("%d\n", lst);
	while (m--)
	{
		scanf("%d%d", &x, &y);
		x ^= p * lst; y ^= p * lst;
		solve::set(x, y);
		printf("%d\n", lst = solve::query());
	}
}