博客
关于我
强烈建议你试试无所不能的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

你可能感兴趣的文章
【转】解决javascript中replace只能替换第一个
查看>>
统计文件或文件夹大小
查看>>
nodejs通过request请求远程url的文件并下载到本地
查看>>
心跳加速的职场面试模拟
查看>>
5.3 批改字
查看>>
使用命令行高效地进行文本编辑
查看>>
Sybase字符串函数-数学函数-系统函数
查看>>
微服务、分布式、云架构构建电子商务平台
查看>>
jquery ajax 超时设置
查看>>
一、数据库入门及表的创建
查看>>
POJ3259 Wormholes(最短路径)
查看>>
第三课:sea.js模块加载原理
查看>>
<<The C Programming Language>>自編習題答案
查看>>
日本語の接続詞
查看>>
如何用java实现数据脱敏
查看>>
laya的UI编辑器
查看>>
ORA-12516错误解决
查看>>
网页设计美工过程留心的标题
查看>>
hdu4223(dp)
查看>>
MVC view操作(Razor语法)
查看>>