The Trip On Abandoned Railway(线段树+树状数组)

本文主要是介绍The Trip On Abandoned Railway(线段树+树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/problem/13891
来源：牛客网

题目描述
There are many ghosts at the abandoned station on unknown railway.

We mark the abandoned stations as 1,2…n according to the order. There are ai ghosts at the ith station.Yakumo Yukari often opens a black hole and makes a train appearing at a certain station. For example, the train appears at the x station, and k ghosts get off at the station. Then there would be k+d ghosts at the x+1 station to get off,k+2×d at x+2 station and so on…There would be k+y∗d ghosts at the x+y station to get off (0≤y,x+y≤n). In others words, the numbers getting off at x,x+1,x+2…n station form a tolerance of d arithmetic progression.(you can consider ghosts getting off at the same time.)Onozuka Komachi would comes a certain station to take away the ghosts.(The number of ghosts at the station would become 0)You have the records of trains appearing and Komachi coming. You should tell Komachi how much ghosts at a certain station when she come to there.
输入描述:
The first line contains an positive integer T(1≤T≤10), represents there are T test cases.
For each test case:
The first line contains three positive integers n,m,d(1≤n≤105,1≤m≤105,1≤d≤1000) - the number of station,the number of records,and the tolerance of the arithmetic progress.

The second line contains n integers a1,a2…an(1≤ai≤1000). Then m lines followed. Each line contains a records and there are two types. 1 x y,indicating train appearing at x station and y ghosts geting off. 2 x y,indicating Komachi coming to the x station. (1≤x≤n,0≤y≤1000)
输出描述:
For each second records(2 x), output an integer in one line, representing the number of ghosts at the station.Since the ans may be too large, out put tme ans mod 109+7.
示例1
输入
复制
2
6 6 1
1 2 3 3 2 1
1 1 1
2 1
2 2
2 3
2 4
2 5
5 3 2
1 2 3 4 5
1 3 0
2 4
2 4
输出
复制
2
4
6
7
7
6
0
说明
There lists the number of ghosts changing at these station.
case1：
1 2 3 3 2 1
2 4 6 7 7 7
0 4 6 7 7 7
0 0 6 7 7 7
0 0 0 7 7 7
0 0 0 0 7 7
0 0 0 0 0 7
case2：
1 2 3 4 5
1 2 3 6 9
1 2 3 0 9
1 2 3 0 9
题意：题目大意：给你一个长度为n的数列和一个公差d，然后m个操作，操作分为两种，第一种操作有一个x和y，代表从x开始的每个数按照等差数列开始加，x这个位置加上y，x+1这个位置加上y+d，x+2这个位置加上y+2*d，依次递推；第二种操作有一个x，代表把这个位置的数模1e9+7后输出，并且这个位置变成零。
思路：挺巧妙的一种思路。
对于1操作来说，x~n都会加上y，我们可以用树状数组或者线段树对x ~n加上y。对于加上的d，跟位置有关系。那么我们在另一棵线段树上对[x+1,n]都加上1，然后在求的时候，求[1,x]上1的个数，就相当于加上了多少个d。这个题目有个坑点，就是只对答案取模就可以，不用对其余的取模。
线段树+树状数组

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;const int maxx=1e5+100;
struct node{int l;int r;ll sum;ll lazy1;
}p[maxx<<2];
ll a[maxx];
ll c[maxx];
int n,m;ll d;
/*-----------树状数组------------*/
inline int lowbit(int x){return x & -x;}
inline void add(int cur,ll v)
{while(cur<maxx){c[cur]=(c[cur]+v)%mod;cur+=lowbit(cur);}
}
inline ll Query(int cur)
{ll ans=0;while(cur>0){ans=(ans+c[cur])%mod;cur-=lowbit(cur);}return ans;
}
/*------------线段树-------------*/
inline void pushup(int cur)
{p[cur].sum=(p[cur<<1].sum+p[cur<<1|1].sum);
}
inline void pushdown(int cur)
{if(p[cur].lazy1){p[cur<<1].lazy1=(p[cur<<1].lazy1+p[cur].lazy1);p[cur<<1|1].lazy1=(p[cur<<1|1].lazy1+p[cur].lazy1);p[cur<<1].sum=(p[cur<<1].sum+(p[cur<<1].r-p[cur<<1].l+1)*1ll*p[cur].lazy1);p[cur<<1|1].sum=(p[cur<<1|1].sum+(p[cur<<1|1].r-p[cur<<1|1].l+1)*1ll*p[cur].lazy1);p[cur].lazy1=0;}
}
inline void build(int l,int r,int cur)
{p[cur].l=l;p[cur].r=r;p[cur].lazy1=p[cur].sum=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);
}
inline void update(int l,int r,ll v,int cur)
{int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r){p[cur].lazy1=(p[cur].lazy1+v);p[cur].sum=(p[cur].sum+(R-L+1)*v);return ;}int mid=L+R>>1;pushdown(cur);if(r<=mid) update(l,r,v,cur<<1);else if(l>mid) update(l,r,v,cur<<1|1);else update(l,mid,v,cur<<1),update(mid+1,r,v,cur<<1|1);pushup(cur);
}
inline ll query(int l,int r,int cur)
{int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].sum;pushdown(cur);int mid=L+R>>1;ll ans;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return (query(l,mid,cur<<1)+query(mid+1,r,cur<<1|1));return ans;
}
int main()
{int t,op,x;ll y;scanf("%d",&t);while(t--){memset(c,0,sizeof(c));scanf("%d%d%lld",&n,&m,&d);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,n,1);while(m--){scanf("%d",&op);if(op==1){scanf("%d%lld",&x,&y);add(x,y);update(x+1,n,1,1);}else{scanf("%d",&x);ll ans=(Query(x)+query(1,x,1)*d*1ll+a[x]);printf("%lld\n",ans%mod);a[x]-=ans;}}}return 0;
}