[数据结构与算法]I-Interval Queries_2021牛客暑期多校训练营5

Interval Queries

I-Interval Queries_2021牛客暑期多校训练营5 (nowcoder.com)

题意： 给一个序列A，q次询问，每次询问给一个区间[L,R]， 再给一个k，要求
∑ i = 0 k ? 1 f ( { A l ? i … A r + i } ) × ( n + i ) i ( m o d ?? p ) d e f : f ( S ) = m a x { l e n ∣ ? x , ? u ∈ { x , … , x + l e n ? 1 } , u ∈ S } \sum_{i = 0}^{k - 1} f(\{A_{l - i} \dots A_{r + i}\}) \times (n + i)^i(\mod p) \\ def: f(S) = max\{len|\exist x, \forall u \in \{x, \dots, x + len - 1\}, u \in S\} i=0∑k?1?f({Al?i?…Ar+i?})×(n+i)i(modp)def:f(S)=max{len∣?x,?u∈{x,…,x+len?1},u∈S}
莫队+链表

回滚莫队：

将所有$[L,R]$ 的询问离线排序，分块，以L所在块为第一关键字R为第二关键字排序，处理每个块内询问的时候，R单调递增，相当于右指针一直往右，左指针在块内小范围波动，

1. 暴力求$[L,R]$ 完全在块内的区间
2. 将维护区间的左端点维护到下一个块的第一个位置

先不考虑k，可以发现每个区间加入的时候更新答案是很容易的，（看该数左右两个数字是否已经出现，更新区间，更新答案），题目又保证$\sum k\le 1e7$， 这个k可以直接暴力做，每次回滚的时候不用对答案作改变，只更新链表，需要在很多个“节点”（非链表节点）处对答案作备份，回到这个地方的时候直接取备份就可以了。

双向链表存+维护每段区间的长度，具体是把每个数字当做一个节点，并对链表的左右端点记录这段区间的左右端点，就可以知道这段区间的长度，还要记录每个节点的个数，加入节点的时候看它是不是第一次被加入，删除的时候看它是不是删到没有了再去改链表

或者可以循环链表头尾给他接起来，额外存一个区间长度，也是上述条件再做修改。

原本代码在在链表中删点的时候出现了一点问题，这里换了写法才过的注释不想删了（数组模拟堆栈）= =，本来想的是在备份处加了几次记录次数然后一起删掉就可以，答案中出现了一些0
先这样吧，有空再看看（咕咕

btw, 回滚莫队这里用的是y总的板子直接拿来改的，yxcyyds。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 1e5 + 10;

const ll mod = 998244353;

ll n, q, len;
ll cnt[N], L[N], R[N];
ll ans[N];
ll a[N];

struct Query {
    ll id, l, r, k, tag;
} query[N];

inline ll get(ll x) {
    return x / len;
}

inline bool cmp(const Query &a, const Query &b) {
    ll i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

stack<ll> st;
int tmm;
int sta[N * 4];

inline void add(ll x, ll &res) {
//    st.push(x);
    sta[tmm++] = x;
    cnt[x]++;
    if (cnt[x] == 1) {
        L[x] = R[x] = x;
        if (L[x - 1]) L[x] = L[x - 1];
        if (R[x + 1])R[x] = R[x + 1];
        if (R[L[x]])R[L[x]] = R[x];
        if (L[R[x]])L[R[x]] = L[x];
        res = max(res, R[x] - L[x] + 1);
    }
}

inline void reduce() {
    if (st.empty()) return;
    auto num = st.top();
    st.pop();
    cnt[num]--;
    if (cnt[num] == 0) {
        L[num] = R[num] = 0;
        if (L[num - 1]) R[L[num - 1]] = R[num - 1] = num - 1;
        if (R[num + 1]) L[R[num + 1]] = L[num + 1] = num + 1;
    }
}

inline void clear_link() {
    while (!st.empty()) {
        auto num = st.top();
        st.pop();
        cnt[num]--;
        if (cnt[num] == 0) {
            L[num] = R[num] = 0;
            if (L[num - 1]) R[L[num - 1]] = R[num - 1] = num - 1;
            if (R[num + 1]) L[R[num + 1]] = L[num + 1] = num + 1;
        }
    }
}


inline void Back(int x) {
    while (tmm > x) {
        int num = sta[--tmm];
        cnt[num]--;
        if (cnt[num] == 0) {
            L[num] = R[num] = 0;
            if (L[num - 1])R[L[num - 1]] = R[num - 1] = num - 1;
            if (R[num + 1])L[R[num + 1]] = L[num + 1] = num + 1;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q;
    len = sqrt(n);
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (ll i = 0; i < q; ++i) {
        cin >> query[i].l >> query[i].r >> query[i].k;
        query[i].id = i;
    }
    sort(query, query + q, cmp);

//    for(int i = 0; i < q; ++ i) {
//        cout <<query[i].id << " " <<query[i].l << " " << query[i].r << " " << query[i].k << endl;
//    }

//    cout << len <<endl;


    for (ll x = 0; x < q;) {
        for (int i = 0; i <= n; ++i) cnt[i] = L[i] = R[i] = 0;
        tmm =0;
        ll y = x;
        while (y < q && get(query[y].l) == get(query[x].l)) y++; //[x, y]为该块内的所有询问
        ll right = get(query[x].l) * len + len - 1; // 这块的最后一个数

        // 暴力求块内的询问
        while (x < y && query[x].r <= right) {
            ll res = 0;
            ll id = query[x].id, l = query[x].l, r = query[x].r, k = query[x].k;
            query[x].tag = 1;
            for (ll i = l; i <= r; i++) add(a[i], res);
            ll backup = res;
            ll fac = 1;
            ll anss = res;
            for (ll i = 1; i < k; ++i) {
                fac = fac * (n + 1) % mod;
                add(a[l - i], res);
                add(a[r + i], res);
                anss = (anss + res * fac% mod) % mod;
            }
            ans[id] = anss;
//            for (ll i = l - k + 1; i <= r + k - 1; i++) reduce();
//            clear_link();
            Back(0);

//            cout << l << " " << r << " "<< k << endl;
//            for(int i = 1; i <= n; ++ i) {
//                cout << cnt[i] << " " << L[i] << " " << R[i] << endl;
//            }
            x++;
        }

        //求块外的询问
        ll res = 0;
        ll i = right;
        while (x < y) {
            int j = right + 1;
            ll id = query[x].id, l = query[x].l, r = query[x].r, k = query[x].k;
            while (i < r) add(a[++i], res);
            ll backup = res; // [nxt_block + 1, R]
            ll here = tmm;

            while (j > l) add(a[--j], res);

            ll fac = 1;
            ll anss = res;
            for (ll ii = 1; ii < k; ++ii) {
                fac = fac * (n + 1) % mod;
                add(a[l - ii], res);
                add(a[r + ii], res);
                anss = (anss + res * fac % mod) % mod;
            }
            ans[id] = anss;

//            for (int ii = 0; ii < tot; ++ii) reduce();
            Back(here);

//            cout << l << " " << r << " " << k << endl;
//            for (int ii = 1; ii <= n; ++ii) {
//                cout << cnt[ii] << " " << L[ii] << " " << R[ii] << endl;
//            }

            res = backup;
            x++;
        }

    }

    for (ll i = 0; i < q; ++i) {
        cout << ans[i] << endl;
    }
    return 0;

}