Untitled
unknown
plain_text
8 days ago
7.4 kB
2
Indexable
Never
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #ifndef ONLINE_JUDGE #define dbg(...) cerr << __LINE__ << ": [", _DEBUG_UTIL_::printer(#__VA_ARGS__, __VA_ARGS__) #define dbgArr(arr, n) cerr << __LINE__ << ": [", _DEBUG_UTIL_::printerArr(#arr, arr, n) #else #define dbg(x...) #define dbgArr(arr, n) #endif namespace _DEBUG_UTIL_ { void print(const char *x) {} void print(bool x) { cerr << (x ? "T" : "F"); } void print(char x) { cerr << '\'' << x << '\''; } void print(signed short int x) { cerr << x; } void print(unsigned short int x) { cerr << x; } void print(signed int x) { cerr << x; } void print(unsigned int x) { cerr << x; } void print(signed long int x) { cerr << x; } void print(unsigned long int x) { cerr << x; } void print(signed long long int x) { cerr << x; } void print(unsigned long long int x) { cerr << x; } void print(float x) { cerr << x; } void print(double x) { cerr << x; } void print(long double x) { cerr << x; } void print(string x) { cerr << '\"' << x << '\"'; } template <size_t N> void print(bitset<N> x) { cerr << x; } void print(vector<bool> x) { int f = 0; cerr << '{'; for (bool i : x) { cerr << (f++ ? "," : ""); cerr << (i ? "T" : "F"); } cerr << "}"; } /* Template Datatypes Declarations */ template <typename T> void print(T x); template <typename T> void print(vector<vector<T>> mat); template <typename T, size_t N> void print(T (&arr)[N]); template <typename T, size_t N, size_t M> void print(T (&mat)[N][M]); template <typename F, typename S> void print(pair<F, S> x); template <typename T> void print(priority_queue<T> pq); template <typename T> void print(priority_queue<T, vector<T>, greater<T>> pq); template <typename T> void print(stack<T> st); template <typename T> void print(queue<T> q); /* Template Datatypes Definitions */ template <typename T> void print(T x) { int f = 0; cerr << '{'; for (auto i : x) cerr << (f++ ? "," : ""), print(i); cerr << "}"; } template <typename T> void print(vector<vector<T>> mat) { int f = 0; cerr << "{\n"; for (auto i : mat) cerr << (f++ ? ",\n" : ""), print(i); cerr << "}\n"; } template <typename T, size_t N> void print(T (&arr)[N]) { int f = 0; cerr << '{'; for (auto &i : arr) cerr << (f++ ? "," : ""), print(i); cerr << "}"; } template <typename T, size_t N, size_t M> void print(T (&mat)[N][M]) { int f = 0; cerr << "{\n"; for (auto &i : mat) cerr << (f++ ? ",\n" : ""), print(i); cerr << "}\n"; } template <typename F, typename S> void print(pair<F, S> x) { cerr << '('; print(x.first); cerr << ','; print(x.second); cerr << ')'; } template <typename T> void print(priority_queue<T> pq) { int f = 0; cerr << '{'; while (!pq.empty()) cerr << (f++ ? "," : ""), print(pq.top()), pq.pop(); cerr << "}"; } template <typename T> void print(priority_queue<T, vector<T>, greater<T>> pq) { int f = 0; cerr << '{'; while (!pq.empty()) cerr << (f++ ? "," : ""), print(pq.top()), pq.pop(); cerr << "}"; } template <typename T> void print(stack<T> st) { int f = 0; cerr << '{'; while (!st.empty()) cerr << (f++ ? "," : ""), print(st.top()), st.pop(); cerr << "}"; } template <typename T> void print(queue<T> q) { int f = 0; cerr << '{'; while (!q.empty()) cerr << (f++ ? "," : ""), print(q.front()), q.pop(); cerr << "}"; } /* Printer */ template <typename T> void printer(const char *name, T &&head) { cerr << name << " = "; print(head); cerr << "]\n"; } template <typename T, typename... V> void printer(const char *names, T &&head, V &&...tail) { int bracket = 0, i = 0; while (names[i] != ',' or bracket != 0) { if (names[i] == '(') bracket++; else if (names[i] == ')') bracket--; i++; } cerr.write(names, i) << " = "; print(head); cerr << " ||"; printer(names + i + 1, tail...); } /* PrinterArr */ template <typename T> void printerArr(const char *name, T arr[], int N) { cerr << name << " : {"; for (int i = 0; i < N; i++) { cerr << (i ? "," : ""), print(arr[i]); } cerr << "}]\n"; } } #define ll long long #define el "\n" #define fi first #define se second #define sz(x) (int)x.size() #define all(v) v.begin(), v.end() const ll N = 1e6 + 6, mod = 1e9 + 7, OO = 1e18; int dx[] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[] = {0, -1, 0, 1, -1, 1, -1, 1}; char di[] = {'D', 'L', 'U', 'R'}; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void file() { #ifndef ONLINE_JUDGE freopen("moon-in.txt", "r", stdin); freopen("moon-out.txt", "w", stdout); #endif } struct item { int freq[41]; ll cnt; }; item e; struct segtree { int size; vector<item> values; item NEUTRAl_ELEMENT = e; void init(int n) { size = 1; while (size < n)size *= 2; values.resize(2 * size); } item single(int a) { item b; memset(b.freq , 0 ,sizeof b.freq); b.freq[a]++; b.cnt = 0; return b; } item marge(item b, item a) { item c; c.cnt = 0; memset(c.freq , 0 ,sizeof c.freq); for (int i = 0; i < 41; ++i) { c.freq[i] = a.freq[i] + b.freq[i]; } for (int i = 0; i < 41; ++i) { for (int j = i+1; j < 41; ++j) { c.cnt += (a.freq[i] * b.freq[j]); } } c.cnt += a.cnt + b.cnt; return c; } void build(vector<int> &a, int x, int lx, int rx) { if (rx - lx == 1) { if (lx < sz(a)) values[x] = single(a[lx]); return; } int m = (lx + rx) / 2; build(a, 2 * x + 1, lx, m); build(a, 2 * x + 2, m, rx); values[x] = marge(values[2 * x + 1], values[2 * x + 2]); } void build(vector<int> &a) { build(a, 0, 0, size); } void set(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { values[x] = single(v); return; } int m = (lx + rx) / 2; if (i < m) { set(i, v, 2 * x + 1, lx, m); } else { set(i, v, 2 * x + 2, m, rx); } values[x] = marge(values[2 * x + 1], values[2 * x + 2]); } void set(int i, int v) { set(i, v, 0, 0, size); } item calc(int l, int r, int x, int lx, int rx) { if (lx >= r || l >= rx)return NEUTRAl_ELEMENT; if (lx >= l && rx <= r)return values[x]; int m = (lx + rx) / 2; item s1 = calc(l, r, 2 * x + 1, lx, m); item s2 = calc(l, r, 2 * x + 2, m, rx); return marge(s1, s2); } item calc(int l, int r) { return calc(l, r, 0, 0, size); } }; void go(int tt) { int n , m; cin >> n >> m; vector<int>a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } segtree st; st.init(n); st.build(a); while(m--){ int op; cin >> op; if(op==1){ int l , r; cin >> l >> r; cout<<st.calc(--l ,r).cnt<<el; }else{ int i , v; cin >> i >> v; st.set(--i , v); } } } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); file(); int t{1}; // cin >> t; e.cnt = 0; memset(e.freq , 0 , sizeof e.freq); for (int tt = 1; tt <= t; ++tt) { go(tt); } return 0; }
Leave a Comment