专栏首页数据结构与算法14:Challenge 7(map大法好)

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LOJ#6279. 数列分块入门 3

    内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论 1 测试数据 ...

    attack
  • LOJ#6278. 数列分块入门 2

    内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

    attack
  • LOJ#6280. 数列分块入门 4

    内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

    attack
  • LOJ#6279. 数列分块入门 3

    内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论 1 测试数据 ...

    attack
  • LOJ#6278. 数列分块入门 2

    内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

    attack
  • Codeforces Round #535 (Div. 3) E1. Array and Segments (Easy version)(思维+暴力)

    题目链接:http://codeforces.com/contest/1108/problem/E1

    Ch_Zaqdt
  • leetcode 周赛155 | 项目管理之拓扑排序算法

    今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理...

    ACM算法日常
  • 【Java学习笔记之十一】Java中常用的8大排序算法详解总结

    分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

    Angel_Kitty
  • 【HDU 5833】Zhu and 772002(异或方程组高斯消元)

    比如12=2^2*3,对应的奇偶值为01(2的个数是偶数为0,3的个数是奇数为1),3的对应奇偶值为01,于是12*3是完全平方数。

    饶文津
  • hdu------1281 棋盘游戏(最小覆盖点)

    棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

    Gxjun

扫码关注云+社区

领取腾讯云代金券