Submission #72213639

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll MOD = 998244353;

ll mult(ll a, ll b){
    return ((a % MOD) * (b % MOD)) % MOD;
}

ll add(ll a, ll b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

ll subt(ll a, ll b){
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

ll binpow(ll a, ll b){
    if(b == 0) return 1;
    if(b & 1){
        return mult(a, binpow(a, b-1));
    }

    ll tmp = binpow(a, b/2);
    return mult(tmp, tmp);
}

ll inv(ll x){
    return binpow(x, MOD-2);
}

class SegmentTree{
private:
  std::vector<int> aint;
  int n;
 
  int join(int x, int y) {
    return add(x, y);
  }
  
  void _update(int node, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        _update(node * 2, from, mid, x, val);
      else
        _update(node * 2 + 1, mid + 1, to, x, val);
      aint[node] = join(aint[node * 2], aint[node * 2 + 1]);
    } else
      aint[node] = val;
  }
 
  int _query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return aint[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return _query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return _query(node * 2 + 1, mid + 1, to, x, y);
      else
        return join(_query(node * 2, from, mid, x, mid),
                    _query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
  
  void _print(int node, int from, int to) {
    if(from < to) {
      int mid = (from + to) / 2;
      _print(node * 2, from, mid);
      _print(node * 2 + 1, mid + 1, to);
    } else
      std::cout << aint[node] << " ";
  }
 
public:
  SegmentTree(int n_) {
    n = n_;
    aint.resize(1 + 4 * n);
  }
  
  void update(int x, int val) {
    _update(1, 1, n, x, val);
  }
  
  int query(int x, int y) {
    if(x > y) return 0;
    return _query(1, 1, n, x, y);
  }
 
  void print() {
    std::cout << "Print array\n";
    _print(1, 1, n);
    std::cout << '\n';
  }
};

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n;
    cin>>n;

    int a[n+5];
    for(int i=1; i<=n; i++) cin>>a[i];

    SegmentTree tmp(n+5), turun(n+5), naik(n+5);
    for(int i=1; i<=n; i++){
        // ll x = tmp.query(1, a[i] - 1) + naik.query(1, a[i] - 1) + turun.query(1, a[i] - 1);
        // ll y = naik.query(a[i] + 1, n) + turun.query(a[i] + 1, n);

        ll x = add(tmp.query(1, a[i] - 1), add(naik.query(1, a[i] - 1), turun.query(1, a[i] - 1)));
        ll y = add(naik.query(a[i] + 1, n), turun.query(a[i] + 1, n));
        naik.update(a[i], x);
        turun.update(a[i], y);
        tmp.update(a[i], 1);
    }
    
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans = add(ans, turun.query(i, i));
    }
    cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result