题目链接: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 ;
}