如何卡

前n/2次基于上一个版本修改

后n/2次基于n/2次的版本查询前n/2次没有修改的位置

则复杂度为$O(n^2)$

记录

改进

这个做法就是将上一个版本和修改的位置做了个链表

实际上 如果修改次数超过$\sqrt n$就暴力重构成块状链表

采用memcpy加速复制 和常数问题 我感觉不一定可以卡掉改进后的$O(n\sqrt n)$做法

暴力做法的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int get(){
    int x=0,f=1;
    char c=getchar_unlocked();
	for (;!isdigit(c);c=getchar_unlocked())if(c=='-')f=-1;
	for (;isdigit(c);c=getchar_unlocked()) x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
void put(int a) {
    if(a<0){
        a=-a;
        putchar_unlocked('-');
    }
    if(a>9){
        put(a/10);
    }
    putchar_unlocked(a%10+'0');
}
int v[(int)1e6+5],ops[(int)1e6+5][3];
int find(int idx,int base){
    if(base==0) return v[idx];
    else if(ops[base][1]==idx) return ops[base][2];
    else return find(idx,ops[base][0]);
}
signed main(){
    int n=get(),m=get();
    //base,idx,val
    for(int i=0;i<n;++i) v[i]=get();
    for(int i=1;i<=m;++i){
        int v=get(),op=get(),p=get();
        p--;
        if(op==1){
            int c=get();
            ops[i][0]=v;
            ops[i][1]=p;
            ops[i][2]=c;
        }
        else{
            ops[i][0]=v;
            ops[i][1]=p;
            ops[i][2]=find(p,v);
            put(ops[i][2]);
            putchar_unlocked(10);
        }
    }
    return 0;
}