本文主要是介绍codeforces 551E GukiZ and GukiZiana 分块，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一个数列，有两种操作，第一种操作将l～r区间加上val，第二种操作是询问整个序列，是否存在val，若存在，则找出相差最远的两个val下标的差值。
没有则输出-1。
思路：
分块。
人生的第一道分块题，其实分块的概念顶容易理解的。
就是把序列分为多个长度为sqrt（n）的块。每次更新的区间更新的时候，如果是完整覆盖某个块，则直接对记录数组进行更新。对于两端的不完全覆盖的块，直接暴力更新。
可以参考这篇文章 http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html
这题一开始是用的set来搞，各种优化各种搞才跑8s过了。后来改用vector来搞，2s就过了。
说下vector的做法：
首先把序列分为每块长度为sqrt（n）块，添加到vec数组中。然后根据值大小还有下标排序。
操作1：对rec数组（记录数组）进行更新。对于不完整的块，则直接暴力更新，再重建对应的vec数组。（注意l，r在同一个块的情况）
操作2：运用upper_bound找所要的位置。
code：
#include <bits/stdc++.h>
using namespace std;const int N = 5e5+5;
const int INF = 0x3f3f3f3f;
const int INT = 1e9;
//typedef long long LL;struct PP {int val;int id;bool operator < (const PP &cmp) const {if(val == cmp.val) return id < cmp.id;return val < cmp.val;}
};int n, q;
int a[N], rec[N];
vector <PP> vec[1000];int preDeal() {int cnt = -1;int len = (int)sqrt(n);for(int i = 0;i < n; i++) {if(i%len==0) cnt++;vec[cnt].push_back((PP){a[i], i});}for(int i = 0;i <= cnt; i++)sort(vec[i].begin(), vec[i].end());return cnt;
}int main() {scanf("%d%d", &n, &q);for(int i = 0;i < n; i++)scanf("%d" ,&a[i]);int len = (int)sqrt(n);int cnt = preDeal()+1;while(q--) {int op;scanf("%d", &op);if(op == 1) {int l, r, val;scanf("%d%d%d", &l, &r, &val);if(val == 0) continue;l--, r--;int bl = l/len, br = r/len;for(int i = bl+1;i < br; i++) {if(rec[i] > INT) continue;rec[i] += val;}//left && rightvec[bl].clear(), vec[br].clear();if(bl == br) {for(int i = l;i <= r; i++) {if(a[i] > INT) continue;a[i] += val;}for(int i = bl*len; i < (bl+1)*len; i++)vec[bl].push_back((PP){a[i], i});sort(vec[bl].begin(), vec[bl].end());}else {//for(int i = l;i < (bl+1)*len;i++) {if(a[i] > INT) continue;a[i] += val;}for(int i = br*len; i <= r; i++) {if(a[i] > INT) continue;a[i] += val;}for(int i = bl*len; i < (bl+1)*len; i++)vec[bl].push_back((PP){a[i], i});sort(vec[bl].begin(), vec[bl].end());for(int i = br*len;i < (br+1)*len; i++)vec[br].push_back((PP){a[i], i});sort(vec[br].begin(), vec[br].end());}}else {int val;scanf("%d", &val);//lint l=-1, r;for(int i = 0;i < cnt; i++) {int tmp = val-rec[i];int idx = upper_bound(vec[i].begin(), vec[i].end(), (PP){tmp, -1})-vec[i].begin();if(idx == vec[i].size()) continue;if(vec[i][idx].val == tmp) {l = vec[i][idx].id;break;}}if(l == -1) {puts("-1");continue;}for(int i = cnt-1;i >= 0; i--) {int tmp = val-rec[i];int idx = upper_bound(vec[i].begin(), vec[i].end(), (PP){tmp, INF})-vec[i].begin();if(idx != 0) idx--;if(vec[i][idx].val == tmp) {r = vec[i][idx].id;break;}}//cout<<"l = "<<l<<" r = "<<r<<endl;printf("%d\n", r-l);}}return 0;
}
这篇关于codeforces 551E GukiZ and GukiZiana 分块的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
