LuoguP3939 - [mNOIP Day1] 数颜色

2017/11/03

题面

懒得复制了

错误解法 #-1

写树套树或者带修改莫队之类的东西。

Orz…

解法 #1

对每种颜色建一个位置数组,注意到如果相邻两种颜色不同交换他们不会影 响到在位置数组中的位置。

对于查询可以做成在位置数组上二分查找。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int SIZ = 5e5 + 2007;

int N, M;
int C[SIZ];
vector<int> W[SIZ];

#define all(x) (x).begin(), (x).end()
int count(int x, int y, int z) {
    int ret = upper_bound(all(W[z]), y) - lower_bound(all(W[z]), x);
    return ret;
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i=1;i<=N;i++) {
        scanf("%d", &C[i]);
        W[C[i]].push_back(i);
    }

    int op, x, y, z;
    while(M--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %d %d", &x, &y, &z);
            printf("%d\n", count(x, y, z));
        } else {
            scanf("%d", &x); y = x + 1;
            int cx = C[x], cy = C[y];
            if(C[x] == C[y]) continue;
            *(lower_bound(all(W[cx]), x)) = y;
            *(lower_bound(all(W[cy]), y)) = x;
            swap(C[x], C[y]);
        }
    }
}

解法 #2

用平衡树维护 size 域,可能会被测试点 15 卡成 95pt 。

如果被卡的话,特判一下如果待修改的两个元素颜色相同就跳过即可。

  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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
const int SIZ = 3e5 + 2007;

int rand() {
    static int k = 1364684679;
    return (k += (k<<2) + 1);
}

#define SZ(x) ((x) ? (x)->sz : 0)
struct node {
    node *l, *r;
    int k, w, sz;

    static node* mknod(node*);

    void up() {
        sz = 1 + SZ(l) + SZ(r);
    }
} POOL[SIZ], *GC[SIZ]; int ppos, gpos;

node* node::mknod(node* w = NULL) {
    if(w) {
        GC[gpos++] = w;
    } else {
        w = (gpos ? GC[--gpos] : &POOL[ppos++]);
        w->sz = w->k = 0; w->w = rand();
        w->l = w->r = NULL;
    }

    return w;
}

struct treap {
    node* root;
    treap() : root(NULL) {}

    void ins(node* &p, int k) {
        if(!p) {
            p = node::mknod();
            p->k = k;
            p->sz = 1;
        } else {
            if(p->k > k) {
                ins(p->l, k);
                node* q = p->l;
                if(q->w < p->w) {
                    p->l = q->r; q->r = p;
                    p = q; p->r->up();
                }
            } else {
                ins(p->r, k);
                node* q = p->r;
                if(q->w < p->w) {
                    p->r = q->l; q->l = p;
                    p = q; p->l->up();
                }
            }
            p->up();
        }
    }

    static void merge(node *&p, node* x, node* y) {
        if(!x || !y) p = x ? x : y;
        else {
            if(x->w < y->w) {
                merge(x->r, x->r, y);
                x->up(); p = x;
            } else {
                merge(y->l, x, y->l);
                y->up(); p = y;
            }
        }
    }

    void del(node* &p, int k) {
        if(p->k == k) {
            node* q = p;
            merge(p, p->l, p->r);
            node::mknod(q);
        } else {
            if(p->k > k) {
                del(p->l, k);        
            } else {
                del(p->r, k);
            }
            p->up();
        }
    }

    int binary_bound(node* x, int k) {
        if(!x || x->k == k) return x ? SZ(x->l) + 1 : 0;
        else {
            if(x->k > k)
                return binary_bound(x->l, k);
            else
                return SZ(x->l) + 1 + binary_bound(x->r, k);
        }
    }

    void insert(int k) {
        ins(root, k);
    }

    void erase(int k) {
        del(root, k);
    }

    int bound(int k) {
        return binary_bound(root, k);
    }

    void dfs(node* p, int dep = 0) {
        if(!p) return;
        if(p->l) dfs(p->l, dep + 4);
        for(int i=0;i<dep;i++) putchar(' ');
        printf("%d %d \n", p->k, p->sz);
        if(p->r) dfs(p->r, dep + 4);
    }

    void dfs() { dfs(root); }

} TR[SIZ];

int C[SIZ];

int N, M;
int main() {
    scanf("%d %d", &N, &M);

    for(int i=1, v;i<=N;i++) {
        scanf("%d", &v);
        C[i] = v;
        TR[v].insert(i);
    }

    int op, x, y, z;
    while(M--) {
        scanf("%d", &op);
        if(op == 1) {
            // Query
            scanf("%d %d %d", &x, &y, &z);
            int sz = TR[z].bound(y) - TR[z].bound(x-1);
            printf("%d\n", sz);
        } else {
            scanf("%d", &x); y = x+1;
            if(C[x] == C[y]) continue;
            TR[C[x]].erase(x); TR[C[x]].insert(y);
            TR[C[y]].erase(y); TR[C[y]].insert(x);
            swap(C[x], C[y]);
        }
        
        /*
        for(int i=1;i<=3;i++) {
            printf("%d\n=======\n", i);
            TR[i].dfs();
            printf("============\n");
        } puts("");
        */
    }
}