結果

問題 No.2568 列辞書順列列
コンテスト
ユーザー soto800
提出日時 2023-12-02 19:30:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,590 bytes
コンパイル時間 2,873 ms
コンパイル使用メモリ 260,232 KB
実行使用メモリ 17,112 KB
最終ジャッジ日時 2024-09-26 21:31:25
合計ジャッジ時間 17,863 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// #include <atcoder/all>

#define lli long long int
#define REP(i, s, n) for (int i = s; i < n; i++)
#define INF (1LL << 50)
#define DEBUG 0
#define mp(a, b) make_pair(a, b)
#define SORT(V) sort(V.begin(), V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) #VariableName
#define LOG(x) \
    if (DEBUG) cout << TO_STRING(x) << "=" << x << " " << endl;
#define LOG2(x, y)                                                          \
    if (DEBUG)                                                              \
        cout << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
             << endl;
#define LOG3(x, y, z)                                                       \
    if (DEBUG)                                                              \
        cout << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
             << " " << TO_STRING(z) << "=" << z << endl;
#define LOG4(w, x, y, z)                                                      \
    if (DEBUG)                                                                \
        cout << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x   \
             << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" \
             << z << endl;

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
const int mod = 998244353;
class mint {
    long long x;

   public:
    mint(long long x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(lli t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint& a) { return (*this) *= a.inv(); }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream& operator<<(ostream& os, const mint& m) {
        os << m.x;
        return os;
    }
};
/* from https://nyaannyaan.github.io/library/misc/mo.hpp.html*/
struct Mo {
    int width;
    vector<int> left, right, order;

    Mo(int N, int Q) : order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(begin(order), end(order), 0);
    }

    void insert(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL& add_left, const AR& add_right, const DL& delete_left,
             const DR& delete_right, const REM& rem) {
        assert(left.size() == order.size());
        sort(begin(order), end(order), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            if (ablock & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        int nl = 0, nr = 0;
        for (auto idx : order) {
            while (nl > left[idx]) add_left(--nl);
            while (nr < right[idx]) add_right(nr++);
            while (nl < left[idx]) delete_left(nl++);
            while (nr > right[idx]) delete_right(--nr);
            rem(idx);
        }
    }
};

/* ABC174-F https://atcoder.jp/contests/abc174/tasks/abc174_f*/
mint anss[500100];

// Generated by 2.12.0 https://github.com/kyuridenamida/atcoder-tools  (tips:
// You use the default template now. You can remove this line by using your
// custom template)
int main() {
    lli N, M, Q;
    cin >> N >> M >> Q;

    vector<lli> a(N);
    REP(i, 0, N) { cin >> a[i]; }

    Mo mo(N, Q);

    REP(i, 0, Q) {
        int l, r;
        cin >> l >> r;

        // 1-index -> 0-index
        mo.insert(l - 1, r);
    }

    mint ans = 0;
    lli length = 0;
    auto al = [&](int nowIndex) {
        mint now = a[nowIndex];
        mint base = M;
        mint offset = (now - 1) * base.pow(length);
        LOG2(nowIndex, offset);
        ans += offset;
        length++;
    };
    auto ar = [&](int nowIndex) {
        int now = a[nowIndex];
        length++;
        LOG3(ans, now, ans * M);
        ans *= M;

        ans += (now - 1);
    };
    auto el = [&](int nowIndex) {
        LOG("el");
        mint now = a[nowIndex];
        mint base = M;
        mint offset = (now - 1) * base.pow(length - 1);
        length--;
        ans -= offset;
    };
    auto er = [&](int nowIndex) {
        LOG("er");
        int now = a[nowIndex];
        ans -= (now - 1);
        ans /= M;
        length--;
    };
    auto q = [&](int i) {
        LOG2("q", i);
        anss[i] = ans;
    };

    mo.run(al, ar, el, er, q);

    REP(i, 0, Q) { cout << anss[i] + 1 << endl; }

    return 0;
}
0