提出 #15631254

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std; const int inf = numeric_limits<int>::max();
struct __io{__io(){ios_base::Init i; ios_base::sync_with_stdio(0); cin.tie(0);}} __io; // fast I/O
#ifdef LOCAL // setting up print debugging (yes lol)
template<class K, class V>ostream& operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.x<<", "<<p.y<<'>';return s;}
template<class T, class=typename T::value_type, class=typename enable_if<!is_same<T,string>::value>::type>
ostream& operator<<(ostream&s,const T&v){s<<'[';for(auto&x:v){s<<x<<", ";}if(!v.empty()){s<<"\b\b";}s<<']';return s;}
void __prnt(){cerr<<endl;} template<class T, class...Ts>void __prnt(T&&a,Ts&&...etc){cerr<<a<<' ';__prnt(etc...);}
#define print(...) __prnt(__VA_ARGS__)
#else
#define print(...)
#endif

struct query {
    int l;
    int r;
    int i;
    int ans;
};

signed main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<query> q(t);
    for (int i = 0; i < t; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].i = i;
        q[i].l--;
        q[i].r--;
    }

    int sqrtn = sqrt(n) + 1;
    sort(q.begin(), q.end(), [&sqrtn](query &a, query &b) {
        if (a.l / sqrtn != b.l / sqrtn) {
            return a.l / sqrtn < b.l / sqrtn;
        }
        return a.r < b.r;
    });

    vector<int> m(n+1);
    int l = 0;
    int r = -1;
    int cnt = 0;

    for (auto &q : q) {
        if (r < q.l || q.r < l) {
            print("!");
            m.assign(n+1, 0);
            cnt = 0;
            l = q.l;
            r = q.l - 1;
        }
        while (r < q.r) {
            r++;
            if (m[a[r]] == 0) cnt++;
            m[a[r]]++;
        }
        while (r > q.r) {
            m[a[r]]--;
            if (m[a[r]] == 0) cnt--;
            r--;
        }
        while (l < q.l) {
            m[a[l]]--;
            if (m[a[l]] == 0) cnt--;
            l++;
        }
        while (l > q.l) {
            l--;
            if (m[a[l]] == 0) cnt++;
            m[a[l]]++;
        }
        q.ans = cnt;
    }
    sort(q.begin(), q.end(), [](query &a, query &b) {return a.i < b.i;});

    for (auto &q : q) {
        cout << q.ans << '\n';
    }
}

提出情報

ジャッジ結果