当前位置：首页 > news >正文

BZOJ5286：[HNOI/AHOI2018]转盘——题解

news 来源：原创 2024/4/29 19:17:15

https://www.lydsy.com/JudgeOnline/problem.php?id=5286

https://www.luogu.org/problemnew/show/P4425

https://loj.ac/problem/2495

题面见上面。

然后因为懒得写公式了所以看这个人的博客吧：https://www.luogu.org/blog/litble-blog/solution-p4425

合并的原理如果看了那个博客还没看懂的话，不妨看看下面这张图：

我们要求的是最上面区间的答案，但显然不能是tr[a]=min(tr[a<<1]],tr[a<<1|1])，因为中间的区间还需要合并。

因为参考博客已经证明了tr[a]表示的区间长度对答案没有影响了所以我们就考虑所有的区间即可。

我们的suan函数的a是最上边区间的左区间，mx和num就是当前区间的mx[a]。

显然当mx>=num的时候a的左区间答案只受mx的影响，而右区间的靠右位置有可能不受mx的影响，因此递归处理。

当mx<num的时候a的右区间只受num的影响，取一个最小值为mid+1+num，再递归处理左区间即可（因为左区间的mx可能比num大）。

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+5;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,m,p,t[N],b[N],tr[N*4],mx[N*4];
int suan(int a,int l,int r,int num){
    if(l==r)return l+max(mx[a],num);
    int mid=(l+r)>>1;
    if(mx[a<<1|1]>=num)
    return min(tr[a],suan(a<<1|1,mid+1,r,num));
    else return min(suan(a<<1,l,mid,num),mid+1+num);
}
void upt(int a,int l,int r){
    mx[a]=max(mx[a<<1],mx[a<<1|1]);
    tr[a]=suan(a<<1,l,(l+r)>>1,mx[a<<1|1]);
}
void build(int a,int l,int r){
    if(l==r){
    tr[a]=t[l];mx[a]=b[l];
    return;
    }
    int mid=(l+r)>>1;
    build(a<<1,l,mid);build(a<<1|1,mid+1,r);
    upt(a,l,r);
}
void mdy(int a,int l,int r,int x){
    if(l==r){
    tr[a]=t[l];mx[a]=b[l];
    return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)mdy(a<<1,l,mid,x);
    else mdy(a<<1|1,mid+1,r,x);
    upt(a,l,r);
}
int main(){
    n=read(),m=read(),p=read();
    for(int i=1;i<=n;i++){
    t[i]=t[i+n]=read();
    b[i]=t[i]-i;
    b[i+n]=t[i+n]-i-n;
    }
    build(1,1,n<<1);
    int lastans=tr[1]+n-1;printf("%d\n",lastans);
    for(int i=1;i<=m;i++){
    int x=read(),y=read();
    if(p)x^=lastans,y^=lastans;
    t[x]=t[x+n]=y;b[x]=y-x;b[x+n]=y-x-n;
    mdy(1,1,n<<1,x);mdy(1,1,n<<1,x+n);
    lastans=tr[1]+n-1;printf("%d\n",lastans);
    }
    return 0;
}