codeforces E2 - Rollbacks (Easy Version and Hard Version)

思路

• 考虑记录元素第一次出现的位置 $pos[x]$ ，$n$ 记录有多少个元素。
• $+$ 则 $++n$ ，$?k$ 则 $n?=k$ ，用树状数组来记录，询问时则可以查询区间 $[1,n]$ 。
• $+$ ：容易想到 ${}^{\prime }{?}^{\prime }$ 是直接 $n?=k$ 对于$[n?k+1,n]$ 这段区间存储的信息是没有复原的。所以当我们 ${}^{\prime }{+}^{\prime }$ 的时候需要注意两种情况：当前位置的旧值是否有贡献（这个值第一次出现的位置是否是当前位置），如果是则要减去其贡献；当前想要添加的值第一次出现的位置是否 $>$ 当前位置，如果是则要减去原位置贡献，加上当前位置贡献。
• $!$ ：回滚操作就是把 ${}^{\prime }{+}^{\prime \prime }{?}^{\prime }$ 复原，所以我们需要记录这两个操作改变了什么，所以用$vector$ 记录。如果上一步操作是 ${}^{\prime }{?}^{\prime }$ 直接 $n+=k$ 。如果是 ${}^{\prime }{+}^{\prime }$ 则上述操作 ${}^{\prime }{+}^{\prime }$ 的两个情况改变没有，改变了直接复原就可以。
  Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int ,int > pii;
int read(void)
{
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x)
{
    if(x<0) x=-x,put(45);
    if(x>9) write(x/10);
    put((x%10)^48);
}
#define writeln(a) write(a),put(10)
#define writesp(a) write(a),put(32)
#define writessp(a) put(32),write(a)
const int N = 1e6 + 10, M = 3e4 + 10, SN = 5e3 + 10, mod = 998244353;
int n, x, q, Q, a[N], tr[N], pos[N];
char c;
signed main()
{
    q = read(); Q = q + 1;
    mem(pos, 0x3f);
    vector<array<int, 4>> op;
    auto add = [] (int x, int v) {
        for (int i = x; i <= Q; i += lowbit(i)) tr[i] += v;
    };
    auto query = [&] (int x) {
        int ans = 0;
        for (int i = x; i ; i -= lowbit(i)) ans += tr[i];
        return ans;
    };
    while (q--) {
        cin >> c;
        if (c == '+') {
            x = read();
            ++n;
            op.push_back({x, pos[x], a[n], pos[a[n]]});
            if (pos[a[n]] == n) add(n, -1), pos[a[n]] = Q;
            if (pos[x] > n) add(pos[x], -1), pos[x] = n, add(n, 1);
            a[n] = x;
        }
        else if (c == '-') x = read(), n -= x, op.push_back({-1, x});
        else if (c == '?') writeln(query(n));
        else {
            auto [xx, yy, zz, ww] = op.back(); op.pop_back();
            if (xx ^ -1) {
                if (yy ^ pos[xx]) add(pos[xx], -1), pos[xx] = yy, add(yy, 1);
                if (ww ^ pos[zz]) add(pos[zz], -1), pos[zz] = ww, add(ww, 1);
                a[n] = zz, --n;
            }
            else n += yy;
        }
    }
    return 0;
}