14:Challenge 7（map大法好）
总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求数列中某个值出现了多少次
输入第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的值修改为y；若该字符为'Q'，则表示一个询问操作，接下来一次整数x，表示求x这个值出现了多少次。输出对每一个询问操作单独输出一行，表示答案。样例输入
5 3
1 2 1 2 1
Q 2
M 1 2
Q 2样例输出
2
3提示1<=N<=10^5，1<=M<=10^5，输入保证合法，且所有整数可用带符号32位整型存储。简述一下本人看到此题的内心变化：第一眼：线段树！第二眼：带修改莫队！第三眼：刚刚眼瞎了，。。。。一波map带走，，，
1 int ans=0;
2 for (int a=1;a<=n;a++)
3 ans += a;
4
5 for (int a=1;a<=n;a+=2) {
6 ans += a;
7 ans += a+1;
8 }
9
10 int s=(int)sqrt(n);
11 for (int a=1;a<=n;a++)
12 belong[a]=(a-1)/s+1;
13 for (int a=1;a<=n;a++)
14 right[belong[a]]=a;
15 for (int a=n;a>=1;a--)
16 left[belong[a]]=a;
17 for (int a=1;a<=n;a++)
18 sum[belong[a]]+=z[a];
19
20 int query(int l,int r) {
21 int ans=0;
22 if (belong[l]==belong[r]) {
23 for (int a=l;a<=r;a++)
24 ans+=z[a]+col[belong[a]];
25 }
26 else {
27 for (int a=l;a<=right[belong[l]];a++)
28 ans+=z[a]+col[belong[a]];
29 for (int a=belong[l]+1;a<belong[r];a++)
30 ans+=sum[a];
31 for (int a=left[belong[r]];a<=r;a++)
32 ans+=z[a]+col[belong[a]];
33 }
34 return ans;
35 }
36
37 void modify(int l,int r,int v) {
38 if (belong[l]==belong[r]) {
39 for (int a=l;a<=r;a++) {
40 z[a]+=v;
41 sum[belong[a]]+=v;
42 }
43 }
44 else {
45 for (int a=l;a<=right[belong[l]];a++) {
46 z[a]+=v;
47 sum[belong[a]]+=v;
48 }
49 for (int a=belong[l]+1;a<belong[r];a++) {
50 col[a]+=v;
51 sum[a]+=(right[a]-left[a]+1)*v;
52 }
53 for (int a=left[belong[r]];a<=r;a++) {
54 z[a]+=v;
55 sum[belong[a]]+=v;
56 }
57 }
58 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读