首页 > 代码库 > CodeForces 551E 分块
CodeForces 551E 分块
题目链接：http://codeforces.com/problemset/problem/551/E
题意：给定一个长度为N的序列。 有2个操作 1 l r v:序列第l项到第r项加v(区间加)， 2 v：求整个序列中值为v的数的位置的差值最大是多少。不存在输出-1.
思路：分块。 每块维护该块序列排序后的序列。 对于区间修改，我们定义一个lazy标记。对于整块的修改我们只修改lazy, 其他情况暴力修改。然后情况该块后重新加入修改后的块然后排序。 对于查询操作。查询每块时v应该减去该块的lazy值。 然后2分查即可。
#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 = 5*100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, q;LL val[MAXN], lazy[MAXN];struct Node{ LL v; int id; Node(LL _v, int _id) :v(_v), id(_id){}; bool operator < (const Node &a)const{ return v==a.v?id<a.id:v<a.v; }};vector<Node>Bval[MAXN];void build(){ block = (int)sqrt(n+0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ lazy[i] = 0; Bval[i].clear(); 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 = 1; i <= num; i++){ for (int k = L[i]; k <= R[i]; k++){ Bval[i].push_back(Node(val[k],k)); } sort(Bval[i].begin(), Bval[i].end()); }}void modify(int st,int ed, LL v){ if (belong[st] == belong[ed]){ for (int i = st; i <= ed; i++){ val[i] += v; } Bval[belong[st]].clear(); for (int i = L[belong[st]]; i <= R[belong[st]]; i++){ Bval[belong[st]].push_back(Node(val[i], i)); } sort(Bval[belong[st]].begin(), Bval[belong[st]].end()); return; } for (int i = st; i <= R[belong[st]]; i++){ val[i] += v; } Bval[belong[st]].clear(); for (int i = L[belong[st]]; i <= R[belong[st]]; i++){ Bval[belong[st]].push_back(Node(val[i], i)); } sort(Bval[belong[st]].begin(), Bval[belong[st]].end()); for (int i = belong[st] + 1; i < belong[ed]; i++){ lazy[i] += v; } for (int i = L[belong[ed]]; i <= ed; i++){ val[i] += v; } Bval[belong[ed]].clear(); for (int i = L[belong[ed]]; i <= R[belong[ed]]; i++){ Bval[belong[ed]].push_back(Node(val[i], i)); } sort(Bval[belong[ed]].begin(), Bval[belong[ed]].end());}int query(LL v){ int L = -1, R = -1; for (int i = 1; i <= num; i++){ LL _v = v-lazy[i]; int pos = lower_bound(Bval[i].begin(), Bval[i].end(), Node(_v,0)) - Bval[i].begin(); if (pos >= 0 && pos < Bval[i].size() && Bval[i][pos].v == _v){ L = Bval[i][pos].id; break; } } if (L == -1){ return -1; } for (int i = num; i > 0; i--){ LL _v = v - lazy[i]; int pos = (lower_bound(Bval[i].begin(), Bval[i].end(), Node( _v + 1,0)) - Bval[i].begin())-1; if (pos >= 0 && pos < Bval[i].size() && Bval[i][pos].v == _v){ R = Bval[i][pos].id; break; } } return R - L;}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("%lld", &val[i]); } build(); for (int i = 1; i <= q; i++){ int type, l, r, v; scanf("%d", &type); if (type == 1){ scanf("%d%d%lld", &l, &r, &v); modify(l, r, v); } else{ scanf("%lld", &v); printf("%d\n", query(v)); } } } //#ifdef LOCAL_TIME // cout << "[Finished in " << clock() - start << " ms]" << endl; //#endif return 0;}
CodeForces 551E 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。