题解：P10680 [COTS/CETS 2024] 双双决斗 Dvoboj

xu_zhihao · 2024-09-28 17:59:27 · 题解

前言

• 只能说这题太模板了。

题目描述

• 什么？ 2^k 区间问题？那绝对得用 ST 表了。但很烦人的是这里有一个单点修改操作，若朴素 ST 表 O(1) 查询，O(n \log n) 修改，这复杂度是绝对过不了的。考虑均摊复杂度。

• 均摊复杂度可以使用根号分治。只用维护 2^k\le \sqrt{N}。区间查询使用递归求出未求部分，复杂度为 O(\sqrt{N})；单点修改复杂度为 O(\sqrt{N})。复杂度变为 O(Q \sqrt{N})。

upd 复杂度若有误请与我联系。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int st[200010][25];
int p[200010];
int s,t;
void Init(){
    for(int i=1;i<=n;i++){
        st[i][0]=p[i];
    }
    for(int j=1;j<=t;j++){
        for(int i=1;i<=n;i++)if(i+(1<<j)-1<=n){
            st[i][j]=abs(st[i][j-1]-st[i+(1<<(j-1))][j-1]);
        }
    }
    return;
}
int check(int l,int k){
    if(k<=t){
        return st[l][k];
    }
    int ans=abs(check(l,k-1)-check(l+(1<<(k-1)),k-1));
    return ans;
}
int Find(int l,int k){
    if(k<=t){
        int ans=st[l][k];
        return ans;
    }
    int ans=check(l,k);
    return ans;
}
void Work(int id,int r){
    st[id][0]=r;
    for(int j=1;j<=t;j++){
        int w=max(id-(1<<j)+1,1);
        for(int i=w;i<=id;i++)if(i+(1<<j)-1<=n){
            st[i][j]=abs(st[i][j-1]-st[i+(1<<(j-1))][j-1]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    s=sqrt(n);
    t=log2(s);
    Init();
    while(q--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int i,r;
            scanf("%d%d",&i,&r);
            Work(i,r);
        }
        else{
            int l,k;
            scanf("%d%d",&l,&k);
            int ans=Find(l,k);
            printf("%d\n",ans);
        }
    }
    return 0;
}