题目大意:中文题目
具体思路:通过两棵线段树来维护,第一棵线段树来维护当前坐标的点的日增长速度(默认每一年的增长速度都是当前年份的增长速度),对于第一棵线段树,肯定会存在多算的情况,那么我们第二棵线段树就维护每一个点的多算的情况就可以了。
举个例子:当前的n只有1,初始值也是1, 三个操作,第一年加一个,第二年加一个,第三年加一个。然后问你第四年的当前的个数。在第二年的时候增长速度还是1,第三年的增加速度就是2,第四年的增长速度就是3。对于第四年的话,第一棵线段树的结果出来的是3,在乘上年份就是3*4=12,这个12指的是四年的产量按照每一年的增长速度都是3计算的,然后我们通过第二棵线段树减去不合法的情况,分别是第二年和第三年多算了,我们再通过12-3-2就能解出正确的答案了。
单拿出一个来看的话
一个的单产量 : 1 1 1 2 2 2 2 3 3 3 3 3 4
会发现
CODE:
#include<iostream> #include<stack> #include<stdio.h> #include<cmath> #include<algorithm> using namespace std; # define ll long long # define lson l,m,rt<<1 # define rson m+1,r, rt<<1|1 const int maxn = 2e5+1000; ll tree1[maxn<<2],tree2[maxn<<2]; ll lazy1[maxn<<2],lazy2[maxn<<2]; ll sto[maxn]; void up(ll rt) { tree1[rt]=tree1[rt<<1]+tree1[rt<<1|1]; tree2[rt]=tree2[rt<<1]+tree2[rt<<1|1]; } void buildtree(ll l,ll r,ll rt) { tree1[rt]=tree2[rt]=0; lazy1[rt]=lazy2[rt]=0; if(l==r) { scanf("%lld",&tree1[rt]); return ; } ll m=(l+r)>>1; buildtree(lson); buildtree(rson); up(rt); } void down(ll rt,ll l,ll r) { ll mid=(l+r)>>1; lazy1[rt<<1]+=lazy1[rt]; lazy1[rt<<1|1]+=lazy1[rt]; tree1[rt<<1]+=lazy1[rt]*(mid-l+1); tree1[rt<<1|1]+=lazy1[rt]*(r-mid); lazy1[rt]=0; lazy2[rt<<1]+=lazy2[rt]; lazy2[rt<<1|1]+=lazy2[rt]; tree2[rt<<1]+=lazy2[rt]*(mid-l+1); tree2[rt<<1|1]+=lazy2[rt]*(r-mid); lazy2[rt]=0; } void update(ll l,ll r,ll rt,ll L,ll R,ll year) { if(L<=l&&R>=r) { tree1[rt]+=(r-l+1); lazy1[rt]+=1; tree2[rt]+=(r-l+1)*year; lazy2[rt]+=year; return ; } down(rt,l,r); ll m=(l+r)>>1; 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 0; if(L<=l&&R>=r) { return tree1[rt]*year-tree2[rt]; } down(rt,l,r); ll m=(l+r)>>1; 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(1,n,1); ll year=0; int m; char str[10]; ll st,ed,num=0; scanf("%d",&m); while(m--) { scanf("%s %lld %lld",str,&st,&ed); year++; if(str[0]=='Q') { ll ans=query(1,n,1,st,ed,year); sto[++num]=ans; } else { update(1,n,1,st,ed,year); } } for(int i=1; i<=num; i++) { if(i==1) printf("%lld",sto[i]); else printf(" %lld",sto[i]); } printf(" "); } return 0; }