众所周知，在喵哈哈村，有一个温柔善良的卿学姐。
卿学姐喜欢和她一样美丽的花。所以卿学姐家的后院有很多的花坛。
卿学姐有n
个花坛，一开始第 i个花坛里有 A[i]朵花。每过一段时间，卿学姐都会在花坛里种上新的花。
作为一个聪明的学姐，卿学姐的种花方式也是与众不同 , 每一次，卿学姐会在第x
个花坛种上 y朵花，然后在第 x+1个花坛上种上 y−1朵花，再在第 x+2个花坛上种上 y−2朵花......以此类推，直到种到最后一个花坛，或者不需要种花为止。
喵哈哈的村民们都喜欢去卿学姐的后院赏花，沈宝宝也不例外。然而沈宝宝可不是省油的灯，怎么可能会老老实实地赏花呢。每次沈宝宝来时，都会随机询问卿学姐在第i
个花坛有多少朵花。
花坛的花实在太多了，卿学姐实在是数不过来。于是现在她向你求助，希望你能帮她数出花坛里多少朵花。
Input
第一行输入两个整数，花坛个数N
。
第二行N
个整数 A[1],A[2],A[3].....A[N]。 ( 1≤A[i]≤231)
接下来Q
行，每行一个操作。
-
1 x y表示卿学姐会在x
朵花，并按相应的规律在后面的花坛上种花。
2 x 表示沈宝宝问卿学姐第x
-
个花坛有多少朵花。
数据保证:
-
1≤N≤104
1≤Q≤2∗106
∑x≤108
， x代表操作 2的询问下标
对于操作 1
, 1≤x≤N， 1≤y≤109对于操作 2
, 1≤x≤NOutput
对于每个询问操作，按顺序输出答案对772002+233
取模的值。
Sample input and output
| Sample Input | Sample Output |
|---|---|
6 3 1 2 3 2 1 2 1 2 3 2 3 2 6 | 5 2 |
Hint
第一次种花会在第2
号花坛种3朵，第3号花坛种2朵，第4号花坛种1朵，由于在第5号花坛不用种花，所以就不再继续种花了，最终每个花坛花的数量分别为1,5,5,3,1。
【来自CDOJ 每周一题 div2 题解】
最简单的方法，O(N)去更新，然后O(1)去查询就好了，但是显然这样子会TLE的
然后我们注意，我们发现这道保证查询操作的sigmax<=1e8
所以我们把这个变成O(1)更新，O(N)查询就好了，这个东西打个延时标记就好了。
比如1 x y
我只需要使得lazy[x]+=y，表示x这个位置需要往下更新的大小增加y
ed[x+y]++，表示某一个更新会在x+y这个位置停止。
num[x]++，表示x这个位置多了一个更新。
然后我们查询2 x的时候
我们只需要从1这个位置，一直for到x这个位置就好了，然后处理我们刚才打上去的延迟标记。
add表示现在累计了多少的值,Num表示现在我有多少个更新。
add+=lazy[i],
Num+=num[i],Num-=ed[i]。
a[i] = (a[i]+add)%mod;
add-=Num。显然走一步，就会减少Num
然后就完了~
然后有人会深入去思考，假设没有那个 sigma x<=1e8怎么办？
其实查询和更新均摊一下就好了：
有两种，
1.分块，这个方法可以把查询和更新操作都均摊到O(sqrt(n))，直接暴力更新这个值在这个块内的数据，然后再暴力更新其他大块就好了
2.线段树，直接暴力去怼线段树就好了
【代码君1 暴力】
【复杂度】O(1e8)
//
//Created by just_sort 2016/10/2 20:29
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4+5;
const int mod = 772002+233;
long long a[maxn],lazy[maxn],num[maxn],ed[maxn];
int n,q;
void update(int x,long long y)
{
lazy[x] += y;
num[x]++;
ed[min(1LL*n+1,1ll*x+y)]++;
}
long long query(int x)
{
long long add = 0;
long long Num = 0;
for(int i = 1; i <= x; i++)
{
add += lazy[i];
Num += num[i];
Num -= ed[i];
lazy[i] = num[i] = ed[i] = 0;
a[i] = (a[i] + add)%mod;
add -= Num;
}
lazy[x+1] += add;
num[x+1] += Num;
return a[x];
}
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++) scanf("%lld",&a[i]),a[i]%=mod;
for(int i = 1; i <= q; i++){
int op,x;
long long y;
scanf("%d",&op);
if(op == 1){
scanf("%d%lld",&x,&y);
update(x,y);
}
else{
scanf("%d",&x);
printf("%lld\n",query(x));
}
}
return 0;
}
【代码君2 分块】
【复杂度】O(qsqrt(n))
//
//Created by just_sort 2016/10/2 20:29
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4+5;
const int mod = 772002+233;
int num,block,belong[maxn];
int l[maxn],r[maxn];
long long a[maxn];
long long lazy[maxn],number[maxn],ed[maxn];
int n,q;
void build()
{
block = sqrt(n);
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;
}
}
void update(int x,long long y)
{
for(int i = x; i <= r[belong[x]]; i++){
a[i] = (a[i] + y)%mod;
y--;
if(y == 0) return ;
}
for(int i = belong[x] + 1; i <= num; i++){
lazy[l[i]] += y;
number[l[i]]++;
if(y < (r[i]-l[i]+1)){
ed[l[i]+y]++;
break;
}
y -= (r[i]-l[i]+1);
}
}
long long query(int x)
{
long long add = 0;
long long Num = 0;
for(int i = l[belong[x]]; i <= r[belong[x]]; i++){
add += lazy[i];
Num += number[i];
Num -= ed[i];
lazy[i] = number[i] = ed[i] = 0;
a[i] = (a[i] + add)%mod;
add -= Num;
}
return a[x]%mod;
}
int main()
{
scanf("%d%d",&n,&q);
build();
for(int i = 1; i <= n; i++){
scanf("%lld",&a[i]);
a[i]%=mod;
}
for(int i = 1; i <= q; i++){
int op,x;
long long y;
scanf("%d",&op);
if(op == 1){
scanf("%d%lld",&x,&y);
update(x,y);
}
else{
scanf("%d",&x);
printf("%lld\n",query(x));
}
}
return 0;
}
【代码君3 线段树】
【复杂度】O(QlogN)
//
//Created by just_sort 2016/10/2 20:29
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4+5;
const int mod = 772002+233;
struct node{
int l,r;
long long time,cnt;
}Tree[maxn*4];
long long a[maxn];
void Build(int l,int r,int rt)
{
Tree[rt].l = l,Tree[rt].r = r;
if(l == r){
Tree[rt].time = Tree[rt].cnt = 0;
return ;
}
int mid = (l+r)/2;
Build(l,mid,rt*2);
Build(mid+1,r,rt*2+1);
}
void update(int L,int R,long long v,int rt)
{
if(L > R) return ;
if(L == Tree[rt].l && R == Tree[rt].r)
{
Tree[rt].time++;
Tree[rt].cnt += v;
return ;
}
int mid = (Tree[rt].l + Tree[rt].r)/2;
update(L,min(mid,R),v,rt*2);
update(max(L,mid+1),R,v-max(0,mid+1-L),rt*2+1);
}
long long query(int pos,int rt)
{
if(Tree[rt].l > pos || Tree[rt].r < pos) return 0;
long long res = Tree[rt].cnt - (1LL*(pos - Tree[rt].l)*Tree[rt].time);
if(Tree[rt].l != Tree[rt].r)
{
res += query(pos,rt*2) + query(pos,rt*2+1);
}
return res;
}
int main()
{
int n,q,l,r;
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
Build(1,n,1);
for(int i = 1; i <= q; i++){
int op,x;
long long y;
scanf("%d",&op);
if(op == 1){
scanf("%d%lld",&x,&y);
l = x, r = x+(int)y-1;
if(r >= n) r = n;
update(l,r,y,1);
}
else{
scanf("%d",&x);
printf("%lld\n",(a[x] + query(x,1))%mod);
}
}
return 0;
}
京公网安备 11010502036488号