ABC278D模拟撤销时间复杂度

由于每个操作2只会执行1次、撤销1次，操作1只有第一次回全部修改，之后都是O(1)打标记，所以不会超时。

#include <stdio.h>
#define N 200005
int n, m, i, j, k, gai, s[N], x[N], p[N];
long long a[N], c;
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%lld", &a[i]);
    }
    scanf("%d", &m);
    for(i=1; i<=m; i++){
        scanf("%d", &s[i]);
        if(s[i] == 1){
            scanf("%d", &x[i]);
            if(gai){
                for(j=i-1; j>gai; j--){
                    if(s[j] == 3) continue;
                    a[p[j]] -= x[j];
                }
                c += x[i] - x[j], gai = i;
            }//再次赋值：撤销操作2，c记录全部需要加多少
            else{
                for(j=1; j<=n; j++) a[j] = x[i];
                c = 0, gai = i;
            }//首次赋值：O(n)初始化
        }
        if(s[i] == 2){
            scanf("%d%d", &p[i], &x[i]);
            a[p[i]] += x[i];
        }
        if(s[i] == 3){
            scanf("%d", &p[i]);
            printf("%lld\n", a[p[i]]+c);
        }
    }
    return 0;
}

xielr代码：空间换代码，代码简洁、拓展性强

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5;
int n,m,cnt,sum;
map<int,int>a[MAXN];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i][sum]);
    scanf("%lld",&m);
    while(m--){
        int opt,x,y;
        scanf("%lld",&opt);
        if(opt==1){
            scanf("%lld",&x);
            cnt=x;
            sum++;
        }
        else if(opt==2){
            scanf("%lld%lld",&x,&y);
            a[x][sum]+=y;
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",a[x][sum]+cnt);
        }
    }
    return 0;
}