洛谷P2709 小B的询问(莫队)
2021/8/2 6:06:15
本文主要是介绍洛谷P2709 小B的询问(莫队),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
小B 有一个长为 nn 的整数序列 aa,值域为 [1,k][1,k]。
他一共有 mm 个询问,每个询问给定一个区间 [l,r][l,r],求:
∑i=1kci2i=1∑kci2
其中 cic**i 表示数字 ii 在 [l,r][l,r] 中的出现次数。
小B请你帮助他回答询问。
输入格式
第一行三个整数 n,m,kn,m,k。
第二行 nn 个整数,表示 小B 的序列。
接下来的 mm 行,每行两个整数 l,rl,r。
输出格式
输出 mm 行,每行一个整数,对应一个询问的答案。
输入输出样例
输入 #1复制
6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6
输出 #1复制
6 9 5 2
莫队板题。一开始读错题了想了半天不知道怎么写2333
直接套P1972的模板即可。注意增加删除答案的时候不要忘记撤销操作。
#include <bits/stdc++.h> using namespace std; int n, a[100005], m, k, ans[100005], block; inline int read() { char x; while((x = getchar()) > '9' || x < '0') ; int u = x - '0'; while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0'; return u; } int buf[105]; inline void write(int i) { int p = 0; if(i == 0) p++; else while(i) { buf[p++] = i % 10; i /= 10; } for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]); } struct node { int l, r, id; } q[100005]; bool cmp(node a, node b) { return (a.l / block) ^ (b.l / block)? (a.l / block) < (b.l / block) : (a.l / block) & 1? a.r < b.r: a.r > b.r; } int Ans = 0, cnt[100001]; void add(int x) { Ans -= cnt[a[x]] * cnt[a[x]];//先减去现在的 cnt[a[x]]++; Ans += cnt[a[x]] * cnt[a[x]];//再加上多删去的 } void del(int x) { Ans -= cnt[a[x]] * cnt[a[x]]; cnt[a[x]]--; Ans += cnt[a[x]] * cnt[a[x]];//多减的要加回来(因为x^2不是线性函数) } int main() { n = read(); m = read(); k = read(); for (int i = 1; i <= n; i++) { a[i] = read(); } block = n / sqrt(m * 2 / 3); for (int i = 1; i <= m; i++) { q[i].l = read(); q[i].r = read(); q[i].id = i; } sort(q + 1, q + m + 1, cmp); int l = 0, r = 0; for(int i = 1; i <= m; i++) { int ql = q[i].l, qr = q[i].r; while(l < ql) del(l++); while(l > ql) add(--l); while(r < qr) add(++r); while(r > qr) del(r--); ans[q[i].id] = Ans - 1; } for(int i = 1; i <= m; i++) { write(ans[i]); putchar('\n'); } return 0; }
这篇关于洛谷P2709 小B的询问(莫队)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现