【金色】种瓜得瓜，种豆得豆 Gym – 102072H (线段树)

题目链接：https://cn.vjudge.net/problem/Gym-102072H

题目大意：中文题目

具体思路：通过两棵线段树来维护，第一棵线段树来维护当前坐标的点的日增长速度（默认每一年的增长速度都是当前年份的增长速度），对于第一棵线段树，肯定会存在多算的情况，那么我们第二棵线段树就维护每一个点的多算的情况就可以了。

举个例子：当前的n只有1，初始值也是1， 三个操作，第一年加一个，第二年加一个，第三年加一个。然后问你第四年的当前的个数。在第二年的时候增长速度还是1，第三年的增加速度就是2，第四年的增长速度就是3。对于第四年的话，第一棵线段树的结果出来的是3，在乘上年份就是3*4=12，这个12指的是四年的产量按照每一年的增长速度都是3计算的，然后我们通过第二棵线段树减去不合法的情况，分别是第二年和第三年多算了，我们再通过12-3-2就能解出正确的答案了。

感谢qyn的讲解。

AC代码：

 #include<iostream>
 #include<stack>
 #include<stdio.h>
 #include<cmath>
 #include<algorithm>
 using namespace std;
 # define ll long long
 # define lson l,m,rt<<
 # define rson m+,r, rt<<|
 const int maxn = 2e5+;
 ll tree1[maxn<<],tree2[maxn<<];
 ll lazy1[maxn<<],lazy2[maxn<<];
 ll sto[maxn];
 void up(ll rt)
 {
     tree1[rt]=tree1[rt<<]+tree1[rt<<|];
     tree2[rt]=tree2[rt<<]+tree2[rt<<|];
 }
 void buildtree(ll l,ll r,ll rt)
 {
     tree1[rt]=tree2[rt]=;
     lazy1[rt]=lazy2[rt]=;
     if(l==r)
     {
         scanf("%lld",&tree1[rt]);
         return ;
     }
     ll m=(l+r)>>;
     buildtree(lson);
     buildtree(rson);
     up(rt);
 }
 void down(ll rt,ll l,ll r)
 {
     ll mid=(l+r)>>;
     lazy1[rt<<]+=lazy1[rt];
     lazy1[rt<<|]+=lazy1[rt];
     tree1[rt<<]+=lazy1[rt]*(mid-l+);
     tree1[rt<<|]+=lazy1[rt]*(r-mid);
     lazy1[rt]=;
     lazy2[rt<<]+=lazy2[rt];
     lazy2[rt<<|]+=lazy2[rt];     tree2[rt<<]+=lazy2[rt]*(mid-l+);
     tree2[rt<<|]+=lazy2[rt]*(r-mid);
        lazy2[rt]=;
 }
 void update(ll l,ll r,ll rt,ll L,ll R,ll year)
 {
     if(L<=l&&R>=r)
     {
         tree1[rt]+=(r-l+);
         lazy1[rt]+=;
         tree2[rt]+=(r-l+)*year;
         lazy2[rt]+=year;
         return ;
     }
     down(rt,l,r);
     ll m=(l+r)>>;
     if(L<=m)
         update(lson,L,R,year);
     if(R>m)
         update(rson,L,R,year);
     up(rt);
 }
 ll query(ll l,ll r,ll rt,ll L,ll R,ll year)
 {
     if(R<l||L>r)
         return ;
     if(L<=l&&R>=r)
     {
         return tree1[rt]*year-tree2[rt];
     }
     down(rt,l,r);
     ll m=(l+r)>>;
     return query(lson,L,R,year)+query(rson,L,R,year);
     up(rt);
 }
 int main()
 {
 //freopen("data1.out","r",stdin);
     ll n;
     while(~scanf("%lld",&n))
     {
         buildtree(,n,);
         ll year=;
         int m;
         char str[];
         ll st,ed,num=;
         scanf("%d",&m);
         while(m--)
         {
             scanf("%s %lld %lld",str,&st,&ed);
             year++;
             if(str[]=='Q')
             {
                 ll ans=query(,n,,st,ed,year);
                 sto[++num]=ans;
             }
             else
             {
                 update(,n,,st,ed,year);
             }
         }
         for(int i=; i<=num; i++)
         {
             if(i==)
                 printf("%lld",sto[i]);
             else
                 printf(" %lld",sto[i]);
         }
         printf("\n");
     }
     return ;
 }