博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 961E - Tufurama
阅读量:6775 次
发布时间:2019-06-26

本文共 2520 字,大约阅读时间需要 8 分钟。

思路:

线段树或者分块

遍历 1 - n - 1,求 区间[i + 1, min(a[i], n)]大于等于 i 的个数,累加起来

线段树:

#include
using namespace std;#define LL long long #define pb push_back#define ls rt << 1, l, m#define rs rt << 1 | 1, m + 1, r #define mem(a, b) memset(a, b, sizeof(a))const int N = 2e5 + 5;vector
vc[N<<2];int a[N];void build(int rt, int l, int r) { if (l == r) { vc[rt].pb(a[l]); return ; } for (int i = l; i <= r; i++) vc[rt].pb(a[i]); sort(vc[rt].begin(), vc[rt].end()); int m = l + r >> 1; build(ls); build(rs);} int query(int L, int R, int rt, int l, int r) { if (L > R) return 0; if (L <= l && r <= R) { return vc[rt].size()-(lower_bound(vc[rt].begin(), vc[rt].end(), L - 1) - vc[rt].begin()); } int ans = 0; int m = l + r >> 1; if (L <= m) ans += query(L, R, ls); if (R > m) ans += query(L, R, rs); return ans;} int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); LL ans = 0; for (int i = 1; i < n; i++) { ans += query(i + 1, min(a[i], n), 1, 1, n); } printf("%lld\n",ans); return 0;}

分块:

#include
using namespace std;#define LL long long #define pb push_back#define mem(a, b) memset(a, b, sizeof(a))const int N = 2e5 + 5;int a[N], block[1005], belong[N];int blo;vector
vc[1005];int query(int L, int R){ if (R < L) return 0; int ans = 0; if (belong[L] == belong[R]) { for (int i = L; i <= R; i++) { if (a[i] >= L - 1) ans++; } return ans; } for (int i = L; i <= belong[L] * blo; i++){ if (a[i] >= L - 1) ans++; } for (int i = belong[L] + 1; i <= belong[R] - 1; i++) { ans += vc[i].size() - (lower_bound(vc[i].begin(), vc[i].end(), L - 1) - vc[i].begin()); } for (int i = (belong[R] - 1) * blo + 1; i <= R; i++) { if (a[i] >= L - 1) ans++; } return ans;}int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); blo = sqrt(n); for (int i = 1; i <= n; i++) { belong[i] = (i - 1) / blo + 1; } for (int i = 1; i <= n; i++) { vc[belong[i]].pb(a[i]); } for (int i = 1; i <= belong[n]; i++) { sort(vc[i].begin(), vc[i].end()); } LL ans = 0; for (int i = 1; i <= n - 1; i++) { ans += query(i + 1, min(n, a[i])); //cout << ans << endl; } printf("%lld\n", ans); return 0;}

 

转载于:https://www.cnblogs.com/widsom/p/8749296.html

你可能感兴趣的文章
云适配推出浏览器即服务 打造客户端的云计算服务
查看>>
助力优化服务水平 惠普推出可快速部署的存储方案
查看>>
大数据时代的“小数据”
查看>>
5G商用关键设备开发完成:准备大规模普及
查看>>
如何在Linux中将文件编码转换为UTF-8
查看>>
一步一步搭建一个图片上传网站(后台服务器用nodejs)
查看>>
是时候实现 SOC 2.0 了
查看>>
YARN:下一代 Hadoop计算平台
查看>>
如何在Linux下编译安装OpenCV
查看>>
浅谈清洁光纤及光纤配件的主要方式
查看>>
9月7日云栖精选夜读:ApsaraDB for HBase性能/延时全面领先社区版本
查看>>
如何成为一名数据科学家?
查看>>
通威股份拟收购光伏资产 立体渔业+光伏链条待考
查看>>
美国教师收获世界上最大的南瓜 重达783千克
查看>>
美国哪些公司实习生工资高?Facebook每月给5万5
查看>>
《MySQL技术内幕:InnoDB存储引擎第2版》——1.3 MySQL存储引擎
查看>>
Spark VS Hadoop 解读两大大数据分析系统
查看>>
远程监控与分析使变电站管理变样
查看>>
智能家居市场迎爆发:规模预计将达1300亿元
查看>>
《认知设计:提升学习体验的艺术》——例子
查看>>