• 树状数组解题报告

    [NOIP2013 提高组] 火柴排队

    题意：

    有两个数组 a [ i ] , b [ i ] a[i],b[i] a[i],b[i]，每次可以交换各个数组中相同的元素，问至少交换多少次后使得 ∑ i = 1 n ( a [ i ] − b [ i ] ) 2 \sum_{i=1}^{n}{(a[i]-b[i])^2} ∑i=1n​(a[i]−b[i])2的值最小。

    思路：

    这题其实并不难，考的只是简单的逆序对，但是关键是怎么发现是逆序对。我们分析这个式子： ∑ i = 1 n ( a [ i ] − b [ i ] ) 2 = a [ i ] 2 + b [ i ] 2 − 2 ∗ a [ i ] ∗ b [ i ] \sum_{i=1}^{n}{(a[i]-b[i])^2}=a[i]^2+b[i]^2-2*a[i]*b[i] ∑i=1n​(a[i]−b[i])2=a[i]2+b[i]2−2∗a[i]∗b[i],既然要取和式的最小值，那么只需求 ∑ ( a [ i ] ∗ b [ i ] ) \sum(a[i]*b[i]) ∑(a[i]∗b[i])的最大值即可。数学不等式中有个结论：顺序之乘>=乱序之乘，也就是说 a a a中第k大的元素要和 b b b中第k大的元素一一对应。那么我们可以先把数组离散化一下，问题就转化为了换多少次后 a a a数组等于 b b b数组。但是我们仍没有一个合适的算法去求解。不妨举个例子：假设我们有离散化后的序列 a = { 1 , 4 , 2 , 3 } , b = { 3 , 4 , 2 , 1 } a=\{ 1,4,2,3\},b=\{3,4,2,1\} a={1,4,2,3},b={3,4,2,1},我们令 q [ a [ i ] ] = b [ i ] q[a[i]]=b[i] q[a[i]]=b[i]相当于以 a [ i ] 为关键字对 b 排序 a[i]为关键字对b排序 a[i]为关键字对b排序，那么我们目标的状态应该是 q [ a [ i ] ] = b [ i ] , 即 q [ i ] = i q[a[i]]=b[i],即q[i]=i q[a[i]]=b[i],即q[i]=i,那么问题就是求至少交换多少次后是数组 q q q升序。这就是逆序对了呀。

    code:

    template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 1e5 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e8 - 3;

//----------------------------------------------------------------------------------------//
template<typename T>
struct BIT{
#ifndef lowbit
    #define lowbit(x) (x & (-x));
#endif
    static const int maxn = 1e5+50;
    int n;
    T t[maxn];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};

int n, a[N], b[N], c[N], d[N], q[N];
void solve() {
    in(n);
    for(int i = 1; i <= n; i++) in(a[i]), c[i] = i;
    for(int i = 1; i <= n; i++) in(b[i]), d[i] = i;
    sort(c + 1, c + 1 + n, [&](int i, int j) {
        return a[i] < a[j];
    });
    sort(d + 1, d + 1 + n, [&](int i, int j) {
        return b[i] < b[j];
    });
    for(int i = 1; i <= n; i++) q[c[i]] = d[i];
    BIT<LL> bit1(n);
    LL res = 0;
    for(int i = 1; i <= n; i++) {
        bit1.add(q[i], 1);
        res += i - bit1.sum(q[i]);
    }
    cout << res;
    
}   
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);

    int T = 1;
    // read(T);
    while(T--) {
        solve();
    }    

    return 0;
}   

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    [USACO17JAN]Promotion Counting P

    题意：

    给定一颗树，每个节点有权值 p [ i ] p[i] p[i]，求每个节点 u u u的子树中满足 p [ i ] > p [ u ] p[i]>p[u] p[i]>p[u]的子节点 i i i的个数。

    分析：

    读完题：好像树状数组？不过树状数组不是处理一段区间的逆序对吗？咋办？我们自然的想到了 d f s 序 dfs序 dfs序，对于当前节点，在求完 d f s 序 dfs序 dfs序后，它的所有子节点都在区间 [ i + 1 , i + s i z e [ i ] ] [i+1,i+size[i]] [i+1,i+size[i]]中，那么我们就可以按照普通的求逆序对来写就可以了。唯一的需要注意的就是先处理权值大的节点。

    code：

    
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 1e5 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e8 - 3;

//----------------------------------------------------------------------------------------//
template<typename T>
struct BIT{
#ifndef lowbit
    #define lowbit(x) (x & (-x));
#endif
    static const int maxn = 1e5+50;
    int n;
    T t[maxn];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};
int n, id[N], num, sz[N];
int h[N], e[N], ne[N], idx;
pii p[N];
void dfs(int u) {
    sz[u] = 1, id[u] = ++num;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        sz[u] += sz[j];
    }
}
void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void solve() {
    memset(h, -1, sizeof h);
    in(n);
    for(int i = 1; i <= n; i++) in(p[i].fi), p[i].se = i;
    for(int i = 2; i <= n; i++) {
        int x; in(x);
        add(x, i);
    }
    BIT<int> bit(n);
    dfs(1);
    sort(p + 1, p + 1 + n, [](pii a, pii b) {
        return a.fi > b.fi;
    });
    vi ans(n + 1);
    for(int i = 1; i <= n; i++) {
        int L = id[p[i].se] + 1, R = id[p[i].se] + sz[p[i].se] - 1;
        ans[p[i].se] = bit.sum(R) - bit.sum(L - 1);
        bit.add(id[p[i].se], 1);
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
         
}   
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);

    int T = 1;
    // read(T);
    while(T--) {
        solve();
    }    

// #ifdef JANGYI
//     cout << "================================" << endl;
//     cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
// #endif
    return 0;
}   



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109

    [POI2015] LOG

    题意：

    维护一个长度为 n n n 的序列，一开始都是 0 0 0，支持以下两种操作：

    1. U k a 将序列中第 k k k 个数修改为 a a a。
    2. Z c s 在这个序列上，每次选出 c c c 个正数，并将它们都减去 1 1 1，询问能否进行 s s s 次操作。

    每次询问独立，即每次询问不会对序列进行修改。

    输入格式

    第一行包含两个正整数 n , m n,m n,m，分别表示序列长度和操作次数。

    接下来 m m m 行为 m m m 个操作。

    输出格式

    包含若干行，对于每个 Z 询问，若可行，输出 TAK，否则输出 NIE。

    思路：

    第一个操作很简单，我们用一个能进行单点修改的数据结构（很多）维护一下就可以，但是现在还不确定用哪个。看第二个操作，看完后第一想法就是先把 ≥ s \ge s ≥s的数先用上再说，设 ≤ s \leq s ≤s的数有 c n t cnt cnt个，它们的和为 s u m sum sum，那么 ≥ s \ge s ≥s的数有 c n t 2 = n − c n t cnt2=n-cnt cnt2=n−cnt个。接下来干什么？？？？？我们再想一下这个操作，能不能把它转换一下？它其实就相当于让我们选择 c ∗ s c*s c∗s个数，构造 s s s个大小为 c c c的数列，前提是数列中不能有重复的数。那么我们先把 ≥ s \ge s ≥s的数填完s行cnt2列，判断剩下的位置有没有 s u m sum sum个即可。相当于需满足 s u m + ( n − c n t ) ∗ s ≥ c ∗ s sum+(n-cnt)*s\ge c*s sum+(n−cnt)∗s≥c∗s。如何维护呢？我们观察到数据范围很大，所以我们可以先给它进行离散化，然后我们设两个树状数组 t r 1 [ i ] , t r 2 [ i ] tr_1[i],tr_2[i] tr1​[i],tr2​[i]， t r 1 [ i ] tr_1[i] tr1​[i]表示小于等于 i i i的数的个数（即 c n t cnt cnt)， t r 2 [ i ] tr_2[i] tr2​[i]表示小于等于 i i i的数的权值的和(即 s u m sum sum)。因为用到权值，我们离散化的时候需双向映射。

    code:

    typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 1e6 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e8 - 3;
inline LL ksm(LL a, LL b, int mod){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

//----------------------------------------------------------------------------------------//
template<typename T>
struct BIT{
#ifndef lowbit
#define lowbit(x) (x & (-x));
#endif
    static const int maxn = 1e6 + 50;
    int n;
    T t[maxn];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};
int n, m, a[N], cnt;
struct Node {
    char ch; int x, y;
}p[N];
vi v;
map<int, int> mp;
int val[N];
BIT<LL> bit1(N), bit2(N);

void update(int x, int y) {
    bit1.add(a[x], -1);
    bit1.add(y, 1);
    bit2.add(a[x], -val[a[x]]);
    bit2.add(y, val[y]);
    a[x] = y;
}
void solve() {
    cin >> n >> m;
    v.pb(0);
    for(int i = 1; i <= m; i++) {
        char ch; int x, y; 
        cin >> ch; cin >> x >> y;
        p[i] = {ch, x, y};
        v.pb(y);
    }
    sort(all(v));
    int cnt = 1;
    val[1] = 0;
    for(int i = 1; i < v.size(); i++) {
        if(v[i] != v[i - 1]) cnt++;
        mp[v[i]] = cnt; val[cnt] = v[i];
    }
    for(int i = 1; i <= n; i++) a[i] = 1, bit1.add(1, 1);
    for(int i = 1; i <= m; i++) {
        if(p[i].ch == 'U') {
            update(p[i].x, mp[p[i].y]);
        } else {
            LL cnt = bit1.sum(mp[p[i].y]), sum = bit2.sum(mp[p[i].y]);
            if(sum + (n - cnt) * p[i].y >= p[i].x * 1LL * p[i].y) puts("TAK");
            else puts("NIE");
        }
    }
}    

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    [SDOI2009] HH的项链

    题意：

    HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

    有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

    输入格式

    一行一个正整数 n n n，表示项链长度。
    第二行 n n n 个正整数 a i a_i ai​，表示项链中第 i i i 个贝壳的种类。

    第三行一个整数 m m m，表示 HH 询问的个数。
    接下来 m m m 行，每行两个整数 l , r l,r l,r，表示询问的区间。

    思路：

    考虑这样一个结论：对于所有r相等的区间的询问，我们只需考虑最后一个出现相同的数字即可。
    例如：1 2 3 4 1
    对于所有r等于5的询问，第一个位置的1是没有用的，因为第5个1可以完全取代它，那么用树状数组维护一下前缀和即可。

    code：

    typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 1e6 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e8 - 3;
inline LL ksm(LL a, LL b, int mod){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

//----------------------------------------------------------------------------------------//
template<typename T>
struct BIT{
#ifndef lowbit
#define lowbit(x) (x & (-x));
#endif
    static const int maxn = 1e6+50;
    int n;
    T t[maxn];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};
int a[N], vis[N];
int ans[N];
struct Node {
    int l, r, i;
}p[N];
void solve() {
    int n; in(n);
    for(int i = 1; i <= n; i++) in(a[i]);
    BIT<int> bit(N - 1);
    int m; in(m);
    for(int i = 1; i <= m; i++) in(p[i].l), in(p[i].r), p[i].i = i;
    sort(p + 1, p + 1 + m, [](Node x, Node y) {
        return x.r < y.r;
    });
    int now = 1;
    for(int i = 1; i <= m; i++) {
        for(int j = now; j <= p[i].r; j++) {
            if(vis[a[j]]) bit.add(vis[a[j]], -1);
            bit.add(j, 1);
            vis[a[j]] = j;
        }
        now = p[i].r + 1;
        ans[p[i].i] = bit.sum(p[i].r) - bit.sum(p[i].l - 1);
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}    
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);

    int T = 1;
    // read(T);
    while(T--) {
        solve();
    }    

// #ifdef JANGYI
//     cout << "================================" << endl;
//     cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
// #endif
    return 0;
}   



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104

    [HEOI2012]采花

    题意：

    给定一个数列，每次询问一个区间内只出现2次的数字的种类。

    思路：

    好像和上一题有点像，但是不知道哪里像。。。
    先随便考虑5 1 2 1这个区间，询问[2,4]，那么我们和上一题一样维护个前缀和就行，但细节之处就在于我们要在第一个1出现的位置加1，即 0 1 0 0,而不是0 0 0 1，这样的话如果我们询问[3,4]的话就错了。出现两次以上的位置，我们只需在倒数第二个位置+1，其它位置全置为0.

    code：

    
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 2e6 + 50, M = N * 2, mod1 = 998244353, mod2 = 1e8 - 3;
inline LL ksm(LL a, LL b, int mod){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

//----------------------------------------------------------------------------------------//
template<typename T>
struct BIT{
#ifndef lowbit
    #define lowbit(x) (x & (-x));
#endif
    static const int maxn = 2e6 + 50;
    int n;
    T t[maxn];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};
int n, c, m;
int a[N], pos1[N], pos2[N];
struct Node {
    int l, r, id;
}p[N];

BIT<int> bit(N - 1);
void solve() {
    cin >> n >> c >> m;
    vector<int> ans(N);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> p[i].l >> p[i].r;
        p[i].id = i;
    }
    sort(p + 1, p + 1 + m, [](Node a, Node b) {
        if(a.r == b.r) return a.l < b.l;
        return a.r < b.r;
    });
    int j = 1;
    for(int i = 1; i <= m; i++) {
        for(; j <= p[i].r; j++) {
            int x = a[j];
            if(!pos1[x]) pos1[x] = j;
            else {
                if(!pos2[x]) {
                    pos2[x] = j;
                    bit.add(pos1[x], 1);
                } else {
                    bit.add(pos1[x], -1);
                    pos1[x] = pos2[x];
                    pos2[x] = j;
                    bit.add(pos1[x], 1);
                }
            }
        }
        ans[p[i].id] = bit.sum(p[i].r) - bit.sum(p[i].l - 1);
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}    
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);

    int T = 1;
    // in(T);
    while(T--) {
        solve();
    }    

// #ifdef JANGYI
//     cout << "================================" << endl;
//     cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
// #endif
    return 0;
}   



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
  • 相关阅读:
    ubuntu重装cuda，cudnn，并挂载计息硬盘到home
    如何使用Portainer创建Nginx容器并搭建web网站发布至公网可访问【内网穿透】
    退化维度详解
    ElasticSearch实操入门(四)
    常用的分布式ID解决方案原理解析
    猿创征文 | C++基础学习一
    Excel中如何用计算公式或表达式直接计算出结果？
    csharp写一个招聘信息采集的程序
    Java8中的 LocalDateTime
    netty系列之:NIO和netty详解
  • 原文地址：https://blog.csdn.net/weixin_60896526/article/details/126131907