题目概述

CF1491H

解题报告

这么诡异的操作，考虑分块。

每个元素记录 $last_i$ 表示 $i$ 往前跳，最后一个没有跳出 $i$ 所在块的位置。查询的时候，先将 $x$ 和 $y$ 跳到 $last_x=last_y$ 的位置，然后慢慢往前跳就行了，复杂度 $O(\sqrt n)$ 。

但是要如何维护 $last$ 呢？观察题目，我们发现 $a$ 数组是只减不增的，因此，一旦 $a_i$ 超出了 $i$ 所在块，$last_i$ 就一直等于 $i$ 自己了。

所以每次对于操作1，直接暴力检查 $[l,r]$ 中 $last_i\not=i$ 的点（可以利用并查集快速访问）重新维护就行了。由于 $a_i$ 被减最多 $\sqrt n$ 次就会使得 $last_i=i$ ，所以总复杂度为 $O(n\sqrt n)$ 。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxs=317;

int n,S,te,lst[maxn+5],L[maxn+5],fat[maxn+5];LL a[maxn+5],tag[maxs+5];

int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
int A(int i) {LL fa=a[i]-tag[(i-1)/S+1];return fa<1?1:fa;}
int main(){
    scanf("%d%d",&n,&te);S=ceil(sqrt(n));
    for (int i=2;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=n;i++) L[i]=(i-1)/S*S+1;
    for (int i=1;i<=n+1;i++) fat[i]=i;
    for (int i=1;i<=n;i++) if (a[i]<L[i]) lst[i]=i,fat[i]=getfa(i+1); else lst[i]=lst[a[i]];
    for (int t=1;t<=te;t++){
        int tp,x,y;scanf("%d%d%d",&tp,&x,&y);
        if (tp==1){
            int w;scanf("%d",&w);
            int l=(x-1)/S+1,r=(y-1)/S+1;
            if (l==r) for (int i=x;i<=y;i++) a[i]-=w; else {
                for (int i=x,R=l*S;i<=R;i++) a[i]-=w;
                for (int i=l+1;i<=r-1;i++) tag[i]+=w;
                for (int i=(r-1)*S+1;i<=y;i++) a[i]-=w;
            }
            for (int i=getfa(x);i<=y;i=getfa(i+1))
                if (A(i)<L[i]) lst[i]=i,fat[i]=getfa(i+1); else lst[i]=lst[A(i)];
            for (int i=y+1,R=r*S;i<=R && i<=n;i++) if (A(i)>=L[i]) lst[i]=lst[A(i)];
        } else {
            while (lst[x]!=lst[y]) x>y?x=A(lst[x]):y=A(lst[y]);
            while (x!=y) x>y?x=A(x):y=A(y);
            printf("%d\n",x);
        }
    }
    return 0;
}