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

TH911 · 2025-07-18 16:20:34 · 题解

题目传送门

题意分析

首先注意到一个非常特殊的性质，区间查询形如 \left[l,l+2^k-1\right]，长度为 2^k。

其次，单点修改很简单，区间查询较为复杂。

所以，考虑使用相关数据结构和算法维护。

考虑 ST 表，这可以很好的维护长度为 2^k 的区间信息。记 \left[l,l+2^k-1\right] 的答案为 \textit{st}_{l,k}。在操作之前，使用普通 ST 表 \mathcal O(n\log n) 预处理。

但是，ST 表是静态的，单点修改后重构的复杂度为 \mathcal O(n)。（并非 \mathcal O(n\log n)，设修改 x，则信息包含 x 的点的区间 [x-2^i+1,x] 需要满足 i\leq\log n，数量即 1+2+4+\cdots+n\leq 2n。）

因此，考虑复杂度均摊，考虑分治。设块长 2^B，并进行阈值分治。

单点修改重构后，处理 \textit{st}_{x,k} 时，我们仅处理 k\leq B 的情况，复杂度 \mathcal O\left(2^B\right)。

查询时，设 \textit{query}(x,k) 表示答案。

• 若 \textit{query}(x,k) 满足 k\leq B，则直接查询 \textit{st}_{x,k}。

• 否则有：

  \textit{query}(x,k)=\vert\textit{query}(x,k-1)-\textit{query}(x+2^{k-1},k-1)\vert

  这样的复杂度是 \mathcal O\left(\dfrac{n}{2^B}\right)。

  因为考虑到会递归 k-B 层，即 \mathcal O(\log n-B) 层。每一层都是双分支，复杂度即 \mathcal O\left(2^{\log n-B}\right)=\mathcal O\left(\dfrac n{2^B}\right)。

取 B=\dfrac{1}{2}\log n，可得最优复杂度。总复杂度为 \mathcal O\left(n\log n+q\sqrt n\right)。

AC 代码

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=200000;
int n,a[N+1],st[N+1][__lg(N+1)+1];
int B;
void stPre(){
    for(int i=1;i<=n;i++){
        st[i][0]=a[i];
    }
    for(int i=1;(1<<i)<=n;i++){
        for(int x=1;x+(1<<i)-1<=n;x++){
            st[x][i]=abs(st[x][i-1]-st[x+(1<<i-1)][i-1]);
        }
    }
}
void change(int p,int r){
    st[p][0]=a[p]=r;
    for(int i=1;i<=B;i++){
        for(int x=max(p-(1<<i)+1,1);x<=p&&x+(1<<i)-1<=n;x++){
            st[x][i]=abs(st[x][i-1]-st[x+(1<<i-1)][i-1]);
        }
    }
}
int query(int l,int k){
    if(k<=B){
        return st[l][k];
    }else{
        return abs(query(l,k-1)-query(l+(1<<k-1),k-1));
    }
}
int main(){
    /*freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);*/

    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int q;
    cin>>n>>q;
    B=__lg(n)>>1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    stPre();
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        switch(op){
            case 1:
                change(x,y);
                break;
            case 2:
                cout<<query(x,y)<<'\n';
                break;
        }
    }

    cout.flush();

    fclose(stdin);
    fclose(stdout);
    return 0;
}