1407 - 郁闷的小J
小J是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。
具体说来，书架由N个书位组成，编号从1到N。每个书位放着一本书，每本书有一个特定的编码。
小J的工作有两类：
- 图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。
- 小J需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。
例如，共5个书位，开始时书位上的书编码为1，2，3，4，5
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：1
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：1
此时，图书馆购进一本编码为“1”的书，并将它放到2号书位。
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：0
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：2
……
你的任务是写一个程序来回答每个顾客的询问。
- INPUT
第一行两个整数N，M，表示一共N个书位，M个操作。
接下来一行共N个整数数A1,A2…AN，Ai表示开始时位置i上的书的编码。
接下来M行，每行表示一次操作，每行开头一个字符
若字符为‘C’，表示图书馆购进新书，后接两个整数A(1<=A<=N)，P，表示这本书被放在位置A上，以及这本书的编码为P。
若字符为‘Q’，表示一个顾客的查询，后接三个整数A，B，K(1<=A<=B<=N)，表示查询从第A书位到第Ｂ书位（包含Ａ和Ｂ）中编码为Ｋ的书共多少本。
（1<=N,M<=100000，所有出现的书的编码为不大于2147483647的正数。）
- OUTPUT
对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。
sl： 首先随便写了个 线段树套set的方法，不出预料的TLE .
然后又写了个线段树套SBT的写法 ，不能忍的TIE.
最后托人写了个二进制trie的方法 ，AC。但是本若菜不想写虽然很短。
继续yy, 发现用map 吧相同的数字的位置维护一下，这个可以用sbt，或是任何的数据结构都可以吧。然后就能过了。但是不想敲了，囧。
先贴上几份sb了的代码。AC代码随后补上。
正确代码可以参考： http://vjudge.net/vjudge/problem/viewSource.action?id=2690221 （我就不贴了。。）
我的两份 ：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <set>
6 using namespace std;
7 const int MAX = 100000+10;
8 int a[MAX];
9
10 struct Node {
11 int key, val;
12 Node(){};
13 Node(int a, int b) { key = a; val = b; }
14 bool operator < (Node b) { return val < b.val; }
15 bool operator <= (Node b) { return val <= b.val; }
16 bool operator > (Node b) { return val > b.val; }
17 bool operator >= (Node b) { return val >= b.val; }
18 bool operator == (Node b) { return val == b.val; }
19 Node operator + (int a) {
20 return Node(key, val+a) > Node(key, val) ? Node(key, val+a) : Node(key, val-a);
21 }
22 };
23
24 int sz[MAX*30];
25 int key[MAX*30];
26 int lch[MAX*30];
27 int rch[MAX*30];
28 int tot;
29
30 template<typename Type>
31 class SBT
32 {
33 public:
34 SBT() { Clear(); }
35 void Clear() { root = 0; lch[0] = rch[0] = sz[0] = 0; }
36 static void ClearAll() { tot = 0; }
37 int Size() { return sz[root]; }
38 bool Empty() { return 0 == sz[root]; }
39 bool Find(Type k) { return Find(root, k); }
40 void InsertR(Type k) { Insert(root, k); } // 可重复插入
41 void Insert(Type k) { if (!Find(k)) Insert(root, k); }
42 void Delete(Type k) { if (Find(k)) Delete(root, k); }
43 void DeleteSmaller(Type k) { DeleteSmaller(root, k); }
44 int GetRank(Type k) { return GetRank(root, k); }
45 Type GetKth(int k) { return GetKth(root, k); }
46 Type GetMin() { return GetKth(root, 1); }
47 Type GetMax() { return GetKth(root, Size()); }
48 Type GetPre(Type k) { return GetPre(root, k); }
49 Type GetSuc(Type k) { return GetSuc(root, k); }
50 int GetSmaller(Type k) { return GetSmaller(root, k); } // 返回小于k的元素的个数
51
52 private:
53 void LeftRotate(int &t) {
54 int k = rch[t];
55 rch[t] = lch[k];
56 lch[k] = t;
57 sz[k] = sz[t];
58 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
59 t = k;
60 }
61 void RightRotate(int &t) {
62 int k = lch[t];
63 lch[t] = rch[k];
64 rch[k] = t;
65 sz[k] = sz[t];
66 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
67 t = k;
68 }
69 void Maintain(int &t, bool flag) {
70 if (0 == t) return ;
71 if (false == flag) {
72 if (sz[lch[lch[t]]] > sz[rch[t]]) {
73 RightRotate(t);
74 } else if (sz[rch[lch[t]]] > sz[rch[t]]) {
75 LeftRotate(lch[t]);
76 RightRotate(t);
77 } else {
78 return ;
79 }
80 } else {
81 if (sz[rch[rch[t]]] > sz[lch[t]]) {
82 LeftRotate(t);
83 } else if (sz[lch[rch[t]]] > sz[lch[t]]) {
84 RightRotate(rch[t]);
85 LeftRotate(t);
86 } else {
87 return ;
88 }
89 }
90 Maintain(lch[t], false);
91 Maintain(rch[t], true);
92 Maintain(t, false);
93 Maintain(t, true);
94 }
95 Type GetPre(int t, Type k) {
96 if (0 == k) return k;
97 if (k <= key[t]) return GetPre(lch[t], k);
98 Type tmp = GetPre(rch[t], k);
99 if (tmp == k) return key[t];
100 return tmp;
101 }
102 Type GetSuc(int t, Type k) {
103 if (0 == root) return k;
104 if (k >= key[t]) return GetSuc(rch[t], k);
105 Type tmp = GetSuc(lch[t], k);
106 if (tmp == k) return key[t];
107 return tmp;
108 }
109 Type GetKth(int t, int k) {
110 if (sz[lch[t]] >= k) return GetKth(lch[t], k);
111 if (sz[lch[t]] == k - 1) return key[t];
112 return GetKth(rch[t], k - sz[lch[t]] - 1);
113 }
114 int GetRank(int t, Type k) {
115 if (0 == t) return 0;
116 if (k < key[t]) return GetRank(lch[t], k);
117 return sz[lch[t]] + 1 + GetRank(rch[t], k);
118 }
119 int GetSmaller(int t, Type k) {
120 if (0 == t) return 0;
121 if (k <= key[t]) return GetSmaller(lch[t], k);
122 return sz[lch[t]] + 1 + GetSmaller(rch[t], k);
123 }
124 bool Find(int t, Type k) {
125 if (0 == t) return false;
126 else if (k < key[t]) return Find(lch[t], k);
127 else return (key[t] == k || Find(rch[t], k));
128 }
129 void Insert(int &t, Type k) {
130 if (0 == t) {
131 t = ++tot;
132 lch[t] = rch[t] = 0;
133 sz[t]= 1;
134 key[t] = k;
135 return ;
136 }
137 sz[t]++;
138 if (k < key[t]) Insert(lch[t], k);
139 else Insert(rch[t], k);
140 Maintain(t, k >= key[t]);
141 }
142 void DeleteSmaller(int &t , Type k) {
143 if (0 == t) return ;
144 if ( key[t] < k ) {
145 t = rch[t];
146 DeleteSmaller(t , key);
147 } else {
148 DeleteSmaller(lch[t] , k);
149 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
150 }
151 }
152 Type Delete(int &t, Type k) {
153 sz[t]--;
154 if ((key[t] == k) || (k < key[t] && 0 == lch[t]) || (k > key[t] && 0 == rch[t])) {
155 Type tmp = key[t];
156 if (0 == lch[t] || 0 == rch[t]) {
157 t = lch[t] + rch[t];
158 } else {
159 key[t] = Delete(lch[t], key[t] + 1);
160 }
161 return tmp;
162 } else {
163 if (k < key[t]) {
164 return Delete(lch[t], k);
165 } else {
166 return Delete(rch[t], k);
167 }
168 }
169 }
170 private:
171 int root;
172 };
173
174 SBT<int> sbt[MAX<<2];
175 inline int read()
176 {
177 int m=0;
178 char ch=getchar();
179 while(ch<'0'||ch>'9'){ch=getchar(); }
180 while(ch>='0'&&ch<='9'){m=m*10+ch-'0'; ch=getchar(); }
181 return m;
182 }
183 void build(int L,int R,int o) {
184 //sbt[o].Clear();
185 for(int i=L;i<=R;i++) {
186 sbt[o].InsertR(a[i]);
187 }
188 if(L==R) return;
189 int mid=(L+R)>>1;
190 build(L,mid,o<<1);
191 build(mid+1,R,o<<1|1);
192 }
193 void Update(int L,int R,int o,int pos,int val) {
194 sbt[o].Delete(a[pos]);
195 sbt[o].InsertR(val);
196 if(L==R) return ;
197 int mid=(L+R)>>1;
198 if(pos<=mid) Update(L,mid,o<<1,pos,val);
199 else Update(mid+1,R,o<<1|1,pos,val);
200 }
201 int Query(int L,int R,int o,int ls,int rs,int val) {
202 if(ls<=L&&rs>=R) {
203 int ans=sbt[o].GetRank(val)-sbt[o].GetRank(val-1);
204 return ans;
205 }
206 int mid=(L+R)>>1;
207 int res=0;
208 if(ls<=mid) res+=Query(L,mid,o<<1,ls,rs,val);
209 if(rs>mid) res+=Query(mid+1,R,o<<1|1,ls,rs,val);
210 return res;
211 }
212
213 int main() {
214 int n,m; char op[10];
215 int ls,rs,val;
216 while(scanf("%d %d",&n,&m)==2) {
217 for(int i=1;i<=n;i++) {
218 a[i]=read();
219 }
220
221 build(1,n,1);
222 for(int i=1;i<=m;i++) {
223 scanf("%s",op);
224 if(op[0]=='Q') {
225 ls=read(); rs=read(); val=read();
226 int ans=Query(1,n,1,ls,rs,val);
227 printf("%d ",ans);
228 }
229 else {
230 ls=read(); val=read();
231 Update(1,n,1,ls,val);
232 a[ls]=val;
233 }
234 }
235 }
236 return 0;
237 }
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <set>
6 using namespace std;
7 const int MAX = 100000+10;
8 int a[MAX];
9
10 struct Node {
11 int key, val;
12 Node(){};
13 Node(int a, int b) { key = a; val = b; }
14 bool operator < (Node b) { return val < b.val; }
15 bool operator <= (Node b) { return val <= b.val; }
16 bool operator > (Node b) { return val > b.val; }
17 bool operator >= (Node b) { return val >= b.val; }
18 bool operator == (Node b) { return val == b.val; }
19 Node operator + (int a) {
20 return Node(key, val+a) > Node(key, val) ? Node(key, val+a) : Node(key, val-a);
21 }
22 };
23
24 int sz[MAX*30];
25 int key[MAX*30];
26 int lch[MAX*30];
27 int rch[MAX*30];
28 int tot;
29
30 template<typename Type>
31 class SBT
32 {
33 public:
34 SBT() { Clear(); }
35 void Clear() { root = 0; lch[0] = rch[0] = sz[0] = 0; }
36 static void ClearAll() { tot = 0; }
37 int Size() { return sz[root]; }
38 bool Empty() { return 0 == sz[root]; }
39 bool Find(Type k) { return Find(root, k); }
40 void InsertR(Type k) { Insert(root, k); } // 可重复插入
41 void Insert(Type k) { if (!Find(k)) Insert(root, k); }
42 void Delete(Type k) { if (Find(k)) Delete(root, k); }
43 void DeleteSmaller(Type k) { DeleteSmaller(root, k); }
44 int GetRank(Type k) { return GetRank(root, k); }
45 Type GetKth(int k) { return GetKth(root, k); }
46 Type GetMin() { return GetKth(root, 1); }
47 Type GetMax() { return GetKth(root, Size()); }
48 Type GetPre(Type k) { return GetPre(root, k); }
49 Type GetSuc(Type k) { return GetSuc(root, k); }
50 int GetSmaller(Type k) { return GetSmaller(root, k); } // 返回小于k的元素的个数
51
52 private:
53 void LeftRotate(int &t) {
54 int k = rch[t];
55 rch[t] = lch[k];
56 lch[k] = t;
57 sz[k] = sz[t];
58 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
59 t = k;
60 }
61 void RightRotate(int &t) {
62 int k = lch[t];
63 lch[t] = rch[k];
64 rch[k] = t;
65 sz[k] = sz[t];
66 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
67 t = k;
68 }
69 void Maintain(int &t, bool flag) {
70 if (0 == t) return ;
71 if (false == flag) {
72 if (sz[lch[lch[t]]] > sz[rch[t]]) {
73 RightRotate(t);
74 } else if (sz[rch[lch[t]]] > sz[rch[t]]) {
75 LeftRotate(lch[t]);
76 RightRotate(t);
77 } else {
78 return ;
79 }
80 } else {
81 if (sz[rch[rch[t]]] > sz[lch[t]]) {
82 LeftRotate(t);
83 } else if (sz[lch[rch[t]]] > sz[lch[t]]) {
84 RightRotate(rch[t]);
85 LeftRotate(t);
86 } else {
87 return ;
88 }
89 }
90 Maintain(lch[t], false);
91 Maintain(rch[t], true);
92 Maintain(t, false);
93 Maintain(t, true);
94 }
95 Type GetPre(int t, Type k) {
96 if (0 == k) return k;
97 if (k <= key[t]) return GetPre(lch[t], k);
98 Type tmp = GetPre(rch[t], k);
99 if (tmp == k) return key[t];
100 return tmp;
101 }
102 Type GetSuc(int t, Type k) {
103 if (0 == root) return k;
104 if (k >= key[t]) return GetSuc(rch[t], k);
105 Type tmp = GetSuc(lch[t], k);
106 if (tmp == k) return key[t];
107 return tmp;
108 }
109 Type GetKth(int t, int k) {
110 if (sz[lch[t]] >= k) return GetKth(lch[t], k);
111 if (sz[lch[t]] == k - 1) return key[t];
112 return GetKth(rch[t], k - sz[lch[t]] - 1);
113 }
114 int GetRank(int t, Type k) {
115 if (0 == t) return 0;
116 if (k < key[t]) return GetRank(lch[t], k);
117 return sz[lch[t]] + 1 + GetRank(rch[t], k);
118 }
119 int GetSmaller(int t, Type k) {
120 if (0 == t) return 0;
121 if (k <= key[t]) return GetSmaller(lch[t], k);
122 return sz[lch[t]] + 1 + GetSmaller(rch[t], k);
123 }
124 bool Find(int t, Type k) {
125 if (0 == t) return false;
126 else if (k < key[t]) return Find(lch[t], k);
127 else return (key[t] == k || Find(rch[t], k));
128 }
129 void Insert(int &t, Type k) {
130 if (0 == t) {
131 t = ++tot;
132 lch[t] = rch[t] = 0;
133 sz[t]= 1;
134 key[t] = k;
135 return ;
136 }
137 sz[t]++;
138 if (k < key[t]) Insert(lch[t], k);
139 else Insert(rch[t], k);
140 Maintain(t, k >= key[t]);
141 }
142 void DeleteSmaller(int &t , Type k) {
143 if (0 == t) return ;
144 if ( key[t] < k ) {
145 t = rch[t];
146 DeleteSmaller(t , key);
147 } else {
148 DeleteSmaller(lch[t] , k);
149 sz[t] = 1 + sz[lch[t]] + sz[rch[t]];
150 }
151 }
152 Type Delete(int &t, Type k) {
153 sz[t]--;
154 if ((key[t] == k) || (k < key[t] && 0 == lch[t]) || (k > key[t] && 0 == rch[t])) {
155 Type tmp = key[t];
156 if (0 == lch[t] || 0 == rch[t]) {
157 t = lch[t] + rch[t];
158 } else {
159 key[t] = Delete(lch[t], key[t] + 1);
160 }
161 return tmp;
162 } else {
163 if (k < key[t]) {
164 return Delete(lch[t], k);
165 } else {
166 return Delete(rch[t], k);
167 }
168 }
169 }
170 private:
171 int root;
172 };
173
174 SBT<int> sbt[MAX<<2];
175 inline int read()
176 {
177 int m=0;
178 char ch=getchar();
179 while(ch<'0'||ch>'9'){ch=getchar(); }
180 while(ch>='0'&&ch<='9'){m=m*10+ch-'0'; ch=getchar(); }
181 return m;
182 }
183 void build(int L,int R,int o) {
184 //sbt[o].Clear();
185 for(int i=L;i<=R;i++) {
186 sbt[o].InsertR(a[i]);
187 }
188 if(L==R) return;
189 int mid=(L+R)>>1;
190 build(L,mid,o<<1);
191 build(mid+1,R,o<<1|1);
192 }
193 void Update(int L,int R,int o,int pos,int val) {
194 sbt[o].Delete(a[pos]);
195 sbt[o].InsertR(val);
196 if(L==R) return ;
197 int mid=(L+R)>>1;
198 if(pos<=mid) Update(L,mid,o<<1,pos,val);
199 else Update(mid+1,R,o<<1|1,pos,val);
200 }
201 int Query(int L,int R,int o,int ls,int rs,int val) {
202 if(ls<=L&&rs>=R) {
203 int ans=sbt[o].GetRank(val)-sbt[o].GetRank(val-1);
204 return ans;
205 }
206 int mid=(L+R)>>1;
207 int res=0;
208 if(ls<=mid) res+=Query(L,mid,o<<1,ls,rs,val);
209 if(rs>mid) res+=Query(mid+1,R,o<<1|1,ls,rs,val);
210 return res;
211 }
212
213 int main() {
214 int n,m; char op[10];
215 int ls,rs,val;
216 while(scanf("%d %d",&n,&m)==2) {
217 for(int i=1;i<=n;i++) {
218 a[i]=read();
219 }
220
221 build(1,n,1);
222 for(int i=1;i<=m;i++) {
223 scanf("%s",op);
224 if(op[0]=='Q') {
225 ls=read(); rs=read(); val=read();
226 int ans=Query(1,n,1,ls,rs,val);
227 printf("%d ",ans);
228 }
229 else {
230 ls=read(); val=read();
231 Update(1,n,1,ls,val);
232 a[ls]=val;
233 }
234 }
235 }
236 return 0;
237 }
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <set>
6 using namespace std;
7 const int MAX = 100000+10;
8 multiset<int> hash[MAX<<2];
9 int a[MAX];
10 inline int read()
11 {
12 int m=0;
13 char ch=getchar();
14 while(ch<'0'||ch>'9'){ch=getchar(); }
15 while(ch>='0'&&ch<='9'){m=m*10+ch-'0'; ch=getchar(); }
16 return m;
17 }
18 void build(int L,int R,int o) {
19 hash[o].clear();
20 for(int i=L;i<=R;i++) {
21 hash[o].insert(a[i]);
22 }
23
24 if(L==R) return ;
25 int mid=(L+R)>>1;
26 build(L,mid,o<<1);
27 build(mid+1,R,o<<1|1);
28 }
29 void Update(int L,int R,int o,int pos,int val) {
30 hash[o].erase(hash[o].find(a[pos]));
31 hash[o].insert(val);
32 if(L==R) return ;
33 int mid=(L+R)>>1;
34 if(pos<=mid) Update(L,mid,o<<1,pos,val);
35 else Update(mid+1,R,o<<1|1,pos,val);
36 }
37 int Query(int L,int R,int o,int ls,int rs,int val) {
38 if(ls<=L&&rs>=R) {
39 return hash[o].count(val);
40 }
41 int mid=(L+R)>>1;
42 int res=0;
43 if(ls<=mid) res+=Query(L,mid,o<<1,ls,rs,val);
44 if(rs>mid) res+=Query(mid+1,R,o<<1|1,ls,rs,val);
45 return res;
46 }
47
48 int main() {
49 int n,m; char op[10];
50 int ls,rs,val;
51 scanf("%d %d",&n,&m);
52 for(int i=1;i<=n;i++) {
53 a[i]=read();
54 }
55
56 build(1,n,1);
57 for(int i=1;i<=m;i++) {
58 scanf("%s",op);
59 if(op[0]=='Q') {
60 ls=read(); rs=read(); val=read();
61 int ans=Query(1,n,1,ls,rs,val);
62 printf("%d ",ans);
63 }
64 else {
65 ls=read(); val=read();
66 Update(1,n,1,ls,val);
67 a[ls]=val;
68 }
69 }
70
71 return 0;
72 }
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <set>
6 using namespace std;
7 const int MAX = 100000+10;
8 multiset<int> hash[MAX<<2];
9 int a[MAX];
10 inline int read()
11 {
12 int m=0;
13 char ch=getchar();
14 while(ch<'0'||ch>'9'){ch=getchar(); }
15 while(ch>='0'&&ch<='9'){m=m*10+ch-'0'; ch=getchar(); }
16 return m;
17 }
18 void build(int L,int R,int o) {
19 hash[o].clear();
20 for(int i=L;i<=R;i++) {
21 hash[o].insert(a[i]);
22 }
23
24 if(L==R) return ;
25 int mid=(L+R)>>1;
26 build(L,mid,o<<1);
27 build(mid+1,R,o<<1|1);
28 }
29 void Update(int L,int R,int o,int pos,int val) {
30 hash[o].erase(hash[o].find(a[pos]));
31 hash[o].insert(val);
32 if(L==R) return ;
33 int mid=(L+R)>>1;
34 if(pos<=mid) Update(L,mid,o<<1,pos,val);
35 else Update(mid+1,R,o<<1|1,pos,val);
36 }
37 int Query(int L,int R,int o,int ls,int rs,int val) {
38 if(ls<=L&&rs>=R) {
39 return hash[o].count(val);
40 }
41 int mid=(L+R)>>1;
42 int res=0;
43 if(ls<=mid) res+=Query(L,mid,o<<1,ls,rs,val);
44 if(rs>mid) res+=Query(mid+1,R,o<<1|1,ls,rs,val);
45 return res;
46 }
47
48 int main() {
49 int n,m; char op[10];
50 int ls,rs,val;
51 scanf("%d %d",&n,&m);
52 for(int i=1;i<=n;i++) {
53 a[i]=read();
54 }
55
56 build(1,n,1);
57 for(int i=1;i<=m;i++) {
58 scanf("%s",op);
59 if(op[0]=='Q') {
60 ls=read(); rs=read(); val=read();
61 int ans=Query(1,n,1,ls,rs,val);
62 printf("%d ",ans);
63 }
64 else {
65 ls=read(); val=read();
66 Update(1,n,1,ls,val);
67 a[ls]=val;
68 }
69 }
70
71 return 0;
72 }