hdu 4638 树状数组

发布时间:2017-3-27 20:45:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4638 树状数组",主要涉及到hdu 4638 树状数组方面的内容,对于hdu 4638 树状数组感兴趣的同学可以参考一下。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100010; int n, m; bool vis[maxn]; int c[maxn], a[maxn], pos[maxn]; struct Query { int l, r, id; bool operator <(const Query &t) const { return l < t.l; } } q[maxn]; int ans[maxn]; inline int sum(int x) { int s = 0; while (x > 0) { s += c[x]; x -= x & -x; } return s; } inline void add(int x, int v) { while (x <= n) { c[x] += v; x += x & -x; } } int main() { int i, j, cas, l, r; scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) { vis[i] = 0; scanf("%d", &a[i]); pos[a[i]] = i; c[i] = 0; } for (i = 0; i < m; i++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } l = 1; for(i = 1; i <= n; i++) { add(i, 1 - vis[a[i] - 1] - vis[a[i] + 1]); vis[a[i]] = 1; } sort(q, q + m); for (i = 0; i < m; i++) { while (l < q[i].l) { add(l, -1); vis[a[l]] = 0; if (vis[a[l] - 1]) add(pos[a[l] - 1], 1); if (vis[a[l] + 1]) add(pos[a[l] + 1], 1); l++; } ans[q[i].id] = sum(q[i].r); } for (i = 0; i < m; i++) printf("%d\n", ans[i]); } return 0; } /* */

上一篇:fzu 1894 志愿者选拔(单调队列)
下一篇:java基础 IO/线程/GUI,装饰模式

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款