卿学姐种美丽的花

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 125535/65535KB (Java/Others)

Submit Status

众所周知，在喵哈哈村，有一个温柔善良的卿学姐。

卿学姐喜欢和她一样美丽的花。所以卿学姐家的后院有很多的花坛。

卿学姐有nn个花坛，一开始第ii个花坛里有A[i]A[i]朵花。每过一段时间，卿学姐都会在花坛里种上新的花。

作为一个聪明的学姐，卿学姐的种花方式也是与众不同 , 每一次，卿学姐会在第xx个花坛种上yy朵花，然后在第x+1x+1个花坛上种上y−1y−1朵花，再在第x+2x+2个花坛上种上y−2y−2朵花......以此类推，直到种到最后一个花坛，或者不需要种花为止。

喵哈哈的村民们都喜欢去卿学姐的后院赏花，沈宝宝也不例外。然而沈宝宝可不是省油的灯，怎么可能会老老实实地赏花呢。每次沈宝宝来时，都会随机询问卿学姐在第ii个花坛有多少朵花。

花坛的花实在太多了，卿学姐实在是数不过来。于是现在她向你求助，希望你能帮她数出花坛里多少朵花。

Input

第一行输入两个整数，花坛个数NN和操作次数QQ。

第二行NN个整数A[1],A[2],A[3].....A[N]A[1],A[2],A[3].....A[N]。 ( 1≤A[i]≤2311≤A[i]≤231 )

接下来QQ行，每行一个操作。

1 x y 表示卿学姐会在xx号花坛种yy朵花，并按相应的规律在后面的花坛上种花。
2 x 表示沈宝宝问卿学姐第xx个花坛有多少朵花。

数据保证:

1≤N≤1061≤N≤106
1≤Q≤2∗1061≤Q≤2∗106
对于操作 11 , 1≤x≤N1≤x≤N，1≤y≤1091≤y≤109
对于操作 22 , 1≤x≤N1≤x≤N

Output

对于每个询问操作，按顺序输出答案对772002+233772002+233取模的值。

Sample input and output

6 3

1 2 3 2 1 2

1 2 3

2 3

2 6

5

2

思路：

这题之前做过，，所以一看到就去卿学姐的代码搞一发（因为我发现之前提交的代码看不到了，所以就用的卿学姐的）

后来听说会查重，就只好重写了。。

思路：用线段树处理，每个节点记录要加的值，并记录加的次数，然后查询的时候加上原来的数值就好了，不过这题会爆int，重写的时候居然又错了一次，，，，，惨

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #include <vector>

 #include <cstdlib>

 #include <string>

 #include <bitset>

 #define PI acos((double)-1)

 #define E exp(double(1))

 #define K 1000000

 using namespace std;

 struct node

 {

     int left,right;

     long long cnt,x;

 };

 struct node tree[*K+];

 int a[K+];

 void build(int id,int l,int r)

 {

     tree[id].left=l;tree[id].right=r;

     if(l==r)

     {

         tree[id].x=tree[id].cnt=;

     }

     else

     {

         build(*id,l,(l+r)/);

         build(*id+,(l+r)/+,r);

     }

 }

 void update(int id,int l,int r,int v)

 {

     if(tree[id].left ==l &&  tree[id].right==r)

     {

         tree[id].x+=v;tree[id].cnt++;

     }

     else

     {

         int mid=(tree[id].left+tree[id].right)/;

         if (r<=mid) update(id*,l,r,v);

         else if(l>mid)  update(id*+,l,r,v);

         else update(id*,l,mid,v),update(id*+,mid+,r,v-(mid+-l));

     }

 }

 long long query(int id,int x)

 {

     if(tree[id].left==tree[id].right)

         return tree[id].x;

     long long sum=;

     sum+=tree[id].x-(x-tree[id].left)*tree[id].cnt;

     int mid=(tree[id].left+tree[id].right)/;

     if (x<=mid)  return sum+query(id*,x);

     else  return sum+query(id*+,x);

 }

 int main(void)

 {

     int n,m;

     cin>>n>>m;

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     build(,,n);

     while(m--)

     {

         int op;

         scanf("%d",&op);

         if(op==)

         {

             long long x,v,y;

             scanf("%lld%lld",&x,&v);

             y=v+x-;

             if(y>n)y=n;

             update(,x,y,v);

         }

         else

         {

             int x;

             scanf("%d",&x);

             printf("%d\n",(a[x]+query(,x))%( + ));

         }

     }

 }

学姐

cdoj1344卿学姐种美丽的花

卿学姐种美丽的花

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 125535/65535KB (Java/Others)

Input

Output

Sample input and output