首页 > 代码库 > CodeForces 13E 分块
CodeForces 13E 分块
题目链接：http://codeforces.com/problemset/problem/13/E
题意：给定n个弹簧和每个弹簧初始的弹力a[]。当球落在第i个位置。则球会被弹到i+a[i]的位置.
现在有2种操作：
1 a b:把第a个弹簧的弹力修改为b。
2 a:当球初始放入的位置为a时，需要弹几次才会弹出n。弹出前的最后一个位置是多少。 输出位置和次数。
思路：和BZOJ 2002一样。 然后记录一个最后弹出去的位置preidx。每次弹出当前块的时候记录当前的位置即可。然后最后再暴力模拟最后弹出去时所在的块的位置即可。
#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 = 100000 + 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>=1; 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); } }}void query(int pos, int &ans, int &preidx){ ans = 0; for (int i = pos; i <= n; i = to[i]){ ans += cnt[i]; preidx = i; //记录最后弹出去前的位置 } for (int i = preidx; i <= n; i = i + a[i]){//暴力模拟最后在哪个位置弹出去了 preidx = i; }}int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); while (~scanf("%d%d", &n, &q)){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } build(); int type, pos, v, ans, idx; for (int i = 1; i <= q; i++){ scanf("%d", &type); if (type == 0){ scanf("%d%d", &pos, &v); modify(pos, v); } else{ scanf("%d", &pos); query(pos, ans, idx); printf("%d %d\n", idx, ans); } } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}
CodeForces 13E 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。