P10680 题解

wukaichen888 · 2024-07-04 19:10:36 · 题解

小清新数据结构。

首先这个唐氏 |A-B| 嵌套感觉不可维护，考虑暴力根号。

静态查询自然想到 st 表。

单点修改自然就是动态 st 表。

修改时暴力将包含这个点的信息暴力改。

将 st 表的长度维度限制在 2^9=512 以内。

查询时尽量分长块，然后暴力合并即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int n,q,a[N],b[1024],tree[4096],tot;
int f[10][N];
void work(int x){
    if(x>1) f[0][x-1]=abs(a[x-1]-a[x]);
    if(x<n) f[0][x]=abs(a[x]-a[x+1]);
    for(int i=1,len;i<=8;i++){
        len=(1<<(i+1));
        for(int l=max(1,x-len+1);l<=min(x,n-len+1);l++)
            f[i][l]=abs(f[i-1][l]-f[i-1][l+(1<<i)]);
    }
}
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
void get(int k,int l,int r){
    if(l==r){
        tree[k]=b[l];
        return ;
    }
    int mid=l+r>>1;
    get(ls);get(rs);
    tree[k]=abs(tree[lc]-tree[rc]);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) f[0][i]=abs(a[i]-a[i+1]);
    for(int i=1,len;i<=8;i++){
        len=(1<<(i+1));
        for(int l=1;l+len-1<=n;l++)
            f[i][l]=abs(f[i-1][l]-f[i-1][l+(1<<i)]);
    }
    int op,x,y,z;
    while(q--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            a[x]=y;
            work(x);
        }
        else{
            tot=0;
            z=min(y-1,8);
            y=x+(1<<y)-1;
            for(int i=x;i<=y;i+=(1<<(z+1))) b[++tot]=f[z][i];
            get(1,1,tot);
            printf("%d\n",tree[1]);
        }
    }
    return 0;
}