题目链接：http://www.ifrog.cc/acm/problem/1129
1129 - 喵哈哈村的战斗魔法师丶坏坏い月Time Limit：3s Memory Limit：256MByte
Submissions：452Solved：97
DESCRIPTION坏坏い月是月大叔的ID，他是一个掌握者772002种魔法的物理系战士，最擅长的技能就是搞事。今天他又要开始搞事了。
给你nn个数，你需要实现一下操作：
l r v ,在[l,r]区间内找到第一个大于等于v的数,输出这个数的下标,如果找不到的话，请输出-1噢
l r v，让[l,r]区间所有数增加v
INPUT 输入第一行包含一个正整数 t(1≤t≤100)t(1≤t≤100) ,表示有t组数据对于每组数据：第一行包含两个整数 n(1≤n≤100000)n(1≤n≤100000), q(1≤q≤100000)q(1≤q≤100000),表示数的个数，以及询问的个数。第二行包含 nn个整数 ai(1≤ai≤1000000000)ai(1≤ai≤1000000000)接下来q行，每行四个整数 opt(1≤opt≤2),l,r(1≤l≤r≤n),v(1≤v≤1000000000)opt(1≤opt≤2),l,r(1≤l≤r≤n),v(1≤v≤1000000000) OUTPUT 对于每个询问，输出一行表示答案. SAMPLE INPUT 1 5 3 1 2 3 4 5 1 1 2 3 2 1 2 3 1 1 2 3 SAMPLE OUTPUT -1 1 SOLUTION “玲珑杯”ACM比赛 Round #15 Submit summary Discuss
解析：
常见的数据结构中，我们选择使用分块来处理这道题。 我们将n个数，分成sqrt(n)块，每块里面的元素最多有sqrt(n)个元素。对于每一个块，我们维护Upd[i]表示这个块整个增加了多少，Max[i]表示这个块内的最大值是多少。 对于查询和更新，如果完全囊括了块的话，我们就只对Upd[i]和Max[i]进行更新，否则的话，我们就暴力更新这个块的元素即可。 总体复杂度O(n*根号n)
借鉴博客：http://blog.csdn.net/qq_33183401/article/details/72820077
分块代码：
#include<bits/stdc++.h> #define N 100009 using namespace std; typedef long long LL; LL a[N], add[N], L[N], R[N], belong[N], mx[N]; inline void q_read(LL &num) { LL f = 1ll; char ch; while(1) { ch = getchar(); if(ch == '-') f = -1; if(isdigit(ch)) { num = ch - '0'; break; } } while(ch=getchar(), isdigit(ch)) num = num * 10ll + ch - '0'; num *= f; } void init(int n) { int block = sqrt(n); int Size = n / block + ((n%block==0)?1:0); memset(add, 0, sizeof(add)); for(int i = 1; i <= Size; i++) { L[i] = (i-1)*block + 1; R[i] = i * block; } R[Size] = n; for(int i = 1; i <= n; i++) belong[i] = (i - 1)/block + 1; for(int i = 1; i <= Size; i++) { int m = -1; for(int j = L[i]; j <= R[i]; j++) { if(m==-1||a[j] > a[m]) m = j; } mx[i] = a[m]; } } int query(int l, int r, LL k) { int lq = belong[l]; int rq = belong[r]; if(lq == rq) { for(int i = l ;i <= r; i++) { if(a[i] + add[lq] >= k) return i; } return -1; } for(int i = l; i <= R[lq]; i++) { if(a[i] + add[lq] >= k) return i; } if(rq - lq > 1) { for(int i = lq + 1; i < rq; i++) { if(mx[i] >= k) { for(int j = L[i]; j <= R[i]; j++) { if(a[j] + add[i] >= k) return j; } } } } for(int i = L[rq]; i <= r; i++) { if(a[i] + add[rq] >= k) return i; } return -1; } void updata(int l, int r, LL k) { int lq = belong[l]; int rq = belong[r]; if(lq == rq) { for(int i = l ;i <= r; i++) { a[i] += k; if(a[i] + add[lq] > mx[lq]) mx[lq] = a[i] + add[lq]; } return ; } for(int i = l; i <= R[lq]; i++) { a[i] += k; if(a[i] + add[lq] > mx[lq]) mx[lq] = a[i] + add[lq]; } if(rq - lq > 1) { for(int i = lq + 1; i < rq; i++) { add[i] += k; mx[i] += k; } } for(int i = L[rq]; i <= r; i++) { a[i] += k; if(a[i] + add[rq] > mx[rq]) mx[rq] = a[i] + add[rq]; } } int main() { int t, n, q; int op, l, r; LL k; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) q_read(a[i]); init(n); while(q--) { scanf("%d%d%d%lld", &op, &l, &r, &k); if(op&1) printf("%d\n", query(l, r, k)); else updata(l, r, k); } } return 0; }
