首页 > 代码库 > HYSBZ 2002 分块
HYSBZ 2002 分块
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2002
题意：中文题面
思路：考虑分块，每个位置维护一个跳出该块需要的步数cnt[],和跳出该块后到达下一块的哪个位置to[]。
关于修改操作：直接修改所在块的左端点到修改的位置。 然后需要逆序修改。因为后面的位置的值会影响到前面位置的值。
关于询问操作：直接暴力计算即可。
#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h> #include<string.h> #include<cstring>#include<algorithm> #include<queue> #include<math.h> #include<time.h>#include<vector>#include<iostream>#include<map>using namespace std;typedef long long int LL;const int MAXN = 200000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, q;int a[MAXN], cnt[MAXN], to[MAXN];void build(){ block = (int)sqrt(n + 0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ L[i] = (i - 1)*block + 1; R[i] = i*block; } R[num] = n; for (int i = 1; i <= n; i++){ belong[i] = ((i - 1) / block) + 1; } for (int i = num; i>0; i--){ for (int j = R[i]; j >= L[i]; j--){ if (j + a[j]>R[i]){ cnt[j] = 1; to[j] = min(n+1,j + a[j]); } else{ cnt[j] = cnt[j + a[j]] + 1; to[j] = min(n+1,to[j + a[j]]); } } }}void modify(int pos, int val){ a[pos] = val; for (int i = pos; i >= L[belong[pos]]; i--){ if (i + a[i]>R[belong[pos]]){ cnt[i] = 1; to[i] = min(i + a[i], n + 1); } else{ cnt[i] = cnt[i + a[i]] + 1; to[i] = min(to[i + a[i]], n + 1); } }}int query(int pos){ int ans = 0; for (int i = pos; i <= n; i = to[i]){ ans += cnt[i]; } return ans;}int main(){ //#ifdef kirito // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); //#endif // int start = clock(); while (~scanf("%d", &n)){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } build(); scanf("%d", &q); int type, pos, v; for (int i = 1; i <= q; i++){ scanf("%d", &type); if (type == 1){ scanf("%d", &pos); pos++; printf("%d\n", query(pos)); } else{ scanf("%d%d", &pos, &v); pos++; modify(pos, v); } } } //#ifdef LOCAL_TIME // cout << "[Finished in " << clock() - start << " ms]" << endl; //#endif return 0;}
HYSBZ 2002 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。