Codeforces - 220B Little Elephant and Array(莫队模板题)
2024-10-18 23:21:58
题意:
m次查询。每次查询范围[L,R]中出现次数等于该数字的数字个数。
题解:
由于分块,在每次询问中,同一块时l至多移动根号n,从一块到另一块也是最多2倍根号n。对于r,每个块中因为同一块是按y排序,所以最多移动根号n;一共根号n个块。注意l和r要分开考虑。
要注意的是这道题需要离散一下数据。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5+;
int n, m;
int l, r;
int a[maxn], b[maxn], d[maxn];
int blk;
int blg[maxn];
int ans;
int sum[maxn];
int out[maxn];
struct node {
int x, y, id;
}c[maxn];
bool cmp(node u, node v) {
return (blg[u.x]==blg[v.x])?u.y<v.y:u.x<v.x;
}
void update(int x, int t) {
sum[d[x]] += t;
if(sum[d[x]] == a[x])
ans++;
else if(sum[d[x]] == a[x]+t)
ans--; }
int main() {
while(~scanf("%d%d", &n, &m)) {
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+, b+n+);
int num = unique(b+, b+n+)-b;
for(int i = ; i <= n; i++) d[i] = lower_bound(b+, b+num+, a[i])-b;
blk = sqrt(n);
for(int i = ; i <= n; i++) blg[i] = (i-)/blk+;
for(int i = ; i <= m; i++) {
scanf("%d%d", &c[i].x, &c[i].y);
c[i].id = i;
}
sort(c+, c+m+, cmp);
l = ; r = ;
ans = ;
memset(sum, , sizeof(sum));
for(int i = ; i <= m; i++) {
while(l < c[i].x) update(l++, -);
while(l > c[i].x) update(--l, );
while(r < c[i].y) update(++r, );
while(r > c[i].y) update(r--, -);
out[c[i].id] = ans;
}
for(int i = ; i <= m; i++) printf("%d\n", out[i]);
}
return ;
}
最新文章
- LLVM 笔记(四)—— three-phase 设计的收益
- Xcode7建立自己的自定义工程和类模板
- Python入门练习
- oracle,mybatis主键自增长
- 【 D3.js 入门系列 --- 3 】 做一个简单的图表!
- FFTW库在VS 2010中的使用方法
- WPF学习系列之七 (样式与行为)
- oc 一些通用函数
- Mysql存储引擎__笔记
- js获取某个标签中的信息
- Promise原理 &;&; 简单实现
- java读取TXT文件的方法
- Maven依赖的是本地工程还是仓库jar包?
- 电脑中dll文件丢失怎么恢复?
- [LeetCode] Delete and Earn 删除与赚取
- CSS_细节总结
- 【转载】网站遭遇DDoS攻击怎么办
- Jquery_如何扩展方法
- LeetCode——4. Median of Two Sorted Arrays
- Quartz动态添加,修改,删除任务(暂停,任务状态,恢复,最近触发时间)