中小企业网站建设行情/班级优化大师官方网站

建立两个线段树，一个存当前年份的产量，一个存每年多算了多少产量。

最后答案  ans=当前产量*年数-多算的产量

 

ps：对于多算的产量，每年只能在一段连续的区间里加1，也就是说对于每一个点来说如果当前年份+1，那么当前年份多算了当年年份的数量。

一个点 初始为1

产量 1  1  1  2  2  3

年份 1  2  3  4  5  6

多算             3      5

我们从第3年产量+1，所以对于前3年我们每年都多算了1 一共多算了3，第5年同理

　　

#include<bits/stdc++.h>using namespace std;#define int long long
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define ls now<<1
#define rs now<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rsconst int maxn=2e5+10;int tree[maxn*4],T[maxn*4];
int lazy[maxn*4],LL[maxn*4];void built(int l,int r,int now)
{int mid=(l+r)>>1;tree[now]=0;lazy[now]=0; T[now]=0;LL[now]=0;if(l==r){scanf("%lld",&tree[now]);return ;}built(lson);built(rson);tree[now]=tree[ls]+tree[rs];
}
void pushdown(int now,int l,int r)
{int mid=(l+r)>>1;if(lazy[now]){lazy[rs]+=lazy[now];lazy[ls]+=lazy[now];tree[ls]+=(mid-l+1)*lazy[now];tree[rs]+=(r-mid)*lazy[now];lazy[now]=0;}
}void updata(int l,int r,int now,int L,int R,int c)
{int mid=(l+r)>>1;if(L<=l&&r<=R){lazy[now]+=c;tree[now]+=c*(r-l+1);return ;}pushdown(now,l,r);if(L<=mid) updata(lson,L,R,c);if(R>mid)  updata(rson,L,R,c);tree[now]=tree[ls]+tree[rs];
}int query(int l,int r,int now,int L,int R)
{int mid=(l+r)>>1;if(L<=l&&r<=R){return tree[now];}pushdown(now,l,r);int ans=0;if(L<=mid) ans+=query(lson,L,R);if(R>mid) ans+=query(rson,L,R);tree[now]=tree[ls]+tree[rs];return ans;
}void PUSH(int now,int l,int r)
{int mid=(l+r)>>1;if(LL[now]){LL[rs]+=LL[now];LL[ls]+=LL[now];T[ls]+=(mid-l+1)*LL[now];T[rs]+=(r-mid)*LL[now];LL[now]=0;}
}void up(int l,int r,int now,int L,int R,int c)
{int mid=(l+r)>>1;if(L<=l&&r<=R){LL[now]+=c;T[now]+=c*(r-l+1);return ;}PUSH(now,l,r);if(L<=mid) up(lson,L,R,c);if(R>mid)  up(rson,L,R,c);T[now]=T[ls]+T[rs];
}int q(int l,int r,int now,int L,int R)
{int mid=(l+r)>>1;if(L<=l&&r<=R){return T[now];}PUSH(now,l,r);int ans=0;if(L<=mid) ans+=q(lson,L,R);if(R>mid) ans+=q(rson,L,R);T[now]=T[ls]+T[rs];return ans;
}#undef int
int main()
{
#define int long longint n;while(scanf("%lld",&n)!=EOF){built(1,n,1);int m,mub=0;scanf("%lld",&m);for(int i=1;i<=m;i++){char ch;int s,t;getchar();scanf("%c%lld%lld",&ch,&s,&t);if(ch=='Q'){if(mub) printf(" ");mub++;printf("%lld",query(1,n,1,s,t)*i-q(1,n,1,s,t));}else{updata(1,n,1,s,t,1);up(1,n,1,s,t,i);}}cout<<"\n";}return 0;
}