Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef double db;
- typedef string str;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef pair<ld, ld> pd;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<ld> vd;
- typedef vector<str> vs;
- typedef vector<pi> vpi;
- typedef vector<pl> vpl;
- typedef vector<pd> vpd;
- #define sz(x) (int)x.size()
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define mp make_pair
- #define nxt_prm next_permutation
- #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
- #define F0R(i, a) FOR(i, 0, a)
- #define ROF(i, a, b) for (int i = (b); i >= (a); --i)
- #define R0F(i, a) ROF(i, 0, a)
- #define trav(a, x) for (auto& a : x)
- const int INT_INF = 2e9;
- const ll LL_INF = 1e18;
- const ld PI = acos(ld(-1));
- int dx[] = { 0, 0, 1, -1 };
- int dy[] = { 1, -1, 0, 0 };
- template<class T> bool ckmin(T &a, const T &b) {
- return a > b ? a = b, 1 : 0;
- }
- template<class T> bool ckmax(T &a, const T &b) {
- return a < b ? a = b, 1 : 0;
- }
- namespace io {
- void setIn(string s) { freopen(s.c_str(), "r", stdin); }
- void setOut(string s) { freopen(s.c_str(), "w", stdout); }
- void setIO(string s = "", bool inter = false) {
- #ifdef ac
- if (!inter) {
- setIn("a.txt");
- }
- #endif
- cout.setf(ios::fixed);
- cout.precision(20);
- ios_base::sync_with_stdio(0); cin.tie(0);
- if (sz(s)) { setIn(s + ".in"), setOut(s + ".out"); }
- }
- }
- using namespace io;
- pi getNorm(pi a) {
- if (a.first > a.second) swap(a.first, a.second);
- return a;
- }
- ll safeMult(ll a, ll b) {
- if (a == 0 || b == 0)
- return 0;
- if (!((LL_INF / a) / b))
- return LL_INF;
- return a * b;
- }
- mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
- const int MAXN = 1e6 + 2;
- int ans[MAXN], Q, cnt[MAXN], beg[MAXN], kek[MAXN];
- vpi o[MAXN];
- vi query[MAXN];
- int main() {
- setIO();
- fill(beg, beg + MAXN, INT_INF);
- cin >> Q;
- FOR(i, 0, Q - 1) {
- int t, x;
- cin >> t >> x;
- if (t == 1) {
- cnt[x]++;
- ckmin(beg[x], i);
- }
- else if (t == 2) {
- cnt[x]--;
- if (cnt[x] == 0) {
- o[x].push_back({ beg[x], i });
- beg[x] = INT_INF;
- }
- }
- else {
- kek[i] = 1;
- query[x].push_back(i);
- }
- }
- FOR(i, 0, MAXN - 1) {
- if (beg[i] != INT_INF) {
- o[i].push_back({ beg[i], Q + 1 });
- }
- }
- FOR(i, 1, MAXN - 1) {
- if (sz(query[i]) == 0) continue;
- vpi scan;
- for (int j = i; j < MAXN; j += i) {
- trav(k, o[j]) {
- scan.push_back({ k.first, -1 });
- scan.push_back({ k.second + 1, 1 });
- }
- }
- sort(all(scan));
- vi pref(sz(query[i]));
- int ptr = 0;
- trav(j, scan) {
- while (ptr < sz(query[i]) && query[i][ptr] < j.first)
- ptr++;
- if (ptr < sz(query[i]))
- pref[ptr] += -1 * j.second;
- }
- FOR(j, 0, sz(query[i]) - 1) {
- if (j > 0) pref[j] += pref[j - 1];
- ans[query[i][j]] += pref[j];
- }
- }
- FOR(i, 0, Q - 1) {
- if (kek[i]) {
- cout << ans[i] << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement