计蒜客 1460.Ryuji doesn't want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)

H.Ryuji doesn't want to study

  • 27.34%
  • 1000ms
  • 262144K
 

Ryuji is not a good student, and he doesn't want to study. But there are n books he should learn, each book has its knowledge a[i]a[i].

Unfortunately, the longer he learns, the fewer he gets.

That means, if he reads books from ll to rr, he will get a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r] (LL is the length of [ ll, rr ] that equals to r - l + 1r−l+1).

Now Ryuji has qq questions, you should answer him:

11. If the question type is 11, you should answer how much knowledge he will get after he reads books [ ll, rr ].

22. If the question type is 22, Ryuji will change the ith book's knowledge to a new value.

Input

First line contains two integers nn and qq (nn, q \le 100000q≤100000).

The next line contains n integers represent a[i]( a[i] \le 1e9)a[i](a[i]≤1e9) .

Then in next qq line each line contains three integers aa, bb, cc, if a = 1a=1, it means question type is 11, and bb, ccrepresents [ ll , rr ]. if a = 2a=2 , it means question type is 22 , and bb, cc means Ryuji changes the bth book' knowledge to cc

Output

For each question, output one line with one integer represent the answer.

样例输入复制

5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5

样例输出复制

10
8

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

题意很好理解,我有两种方法来写这道题目。

第一种就是树状数组,倒的梯形面积。其实并不是严格意义上的三角形,应该是梯形的面积,但是抽象一下,就是三角形,好理解。

计蒜客 1460.Ryuji doesn't want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)

因为下标是从1开始的,所以r+1。横坐标上面的是a数组,下面的是b数组。

代码:

 //H-树状数组
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=1e3+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll a[maxn],b[maxn],n,q; int lowbit(int x)
{
return x&(-x);
} void add(ll a[],int x,ll val)
{
for(int i=x;i<=n;i+=lowbit(i))
a[i]+=val;
} ll query(ll a[],int x)
{
ll ans=;
for(int i=x;i>;i-=lowbit(i))
ans+=a[i];
return ans;
} int main()
{
cin>>n>>q;
for(int i=;i<=n;i++){
ll val;
cin>>val;
add(a,i,val);//单纯的保存,类似前缀和
add(b,i,i*val);//这样保存,减去的时候正好满足条件,*L,*(L-1)。。。
}
while(q--){
ll op,l,r;
cin>>op>>l>>r;
if(op==){
ll cnt=query(a,l)-query(a,l-);//单点更新
add(a,l,r-cnt);
ll ret=query(b,l)-query(b,l-);//同上
add(b,l,l*r-ret);
}
else{
ll cnt=(r+)*(query(a,r)-query(a,l-));//先算出横坐标的和,然后*(r+1)就是一个大矩形的面积
ll ret=query(b,r)-query(b,l-);//倒着的梯形面积,(因为从1开始的,所以是梯形不是三角形)
cout<<cnt-ret<<endl;
}
}
}

还有一种线段树的方法,线段树的就是左儿子+右儿子+两者包围的矩形的面积。

为了好理解,画成三角形,其实严格意义上是梯形,因为最后一个数是×1,但是为了好理解,画成三角形。

计蒜客 1460.Ryuji doesn't want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)

某种意义上是一个个小矩形。

计蒜客 1460.Ryuji doesn't want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)

首先我求每一个小的三角形(矩形)就是ans[rt]+sum[rt]*(tmp-len[rt]);

举个例子,只有一个长度的。

计蒜客 1460.Ryuji doesn't want to study-树状数组 or 线段树 (ACM-ICPC 2018 徐州赛区网络预赛 H)

sum为单点的值,tmp为总的区间查询长度,len[rt]为当前的区间长度。

怎么求粉色三角形的面积呢?就是我一开始线段树存的大的梯形的面积-紫色平行四边形的面积。

tmp就是总长度为小圈1+小圈2的长度,小圈1的长度就是tmp-len[rt],OK了。

ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R){
int tmp=Len;
Len-=len[rt];
return ans[rt]+sum[rt]*(tmp-len[rt]);
} int m=(l+r)>>;
ll ret=;
if(L<=m) ret+=query(L,R,lson);
if(R >m) ret+=query(L,R,rson);
return ret;
}

然后就是总的面积,就是左儿子+右儿子+左儿子的区间和*右儿子的区间长。

代码睡醒上完课再贴,想睡觉了,头发要紧,哈哈哈哈哈。

直接代码了。

 //H-线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=1e3+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 ll sum[maxn<<],ans[maxn<<],len[maxn<<];
//sum为单点的价值(横坐标),ans为总价值,len为区间长度
int Len; void pushup(int rt)
{
ans[rt]= ans[rt<<]+ans[rt<<|]+sum[rt<<]*len[rt<<|];//总价值为左儿子+右儿子+左儿子区间和*右儿子区间长
len[rt]=len[rt<<]+len[rt<<|];
sum[rt]=sum[rt<<]+sum[rt<<|];
} void build(int l,int r,int rt)
{
if(l==r){
scanf("%lld",&sum[rt]);
len[rt]=;
ans[rt]=sum[rt];
return;
} int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
} ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R){
int tmp=Len;
Len-=len[rt];
return ans[rt]+sum[rt]*(tmp-len[rt]);//求小三角形的面积就是大的梯形-平行四边形
} int m=(l+r)>>;
ll ret=;
if(L<=m) ret+=query(L,R,lson);
if(R >m) ret+=query(L,R,rson);
return ret;
} void update(int p,ll val,int l,int r,int rt)//单点更新
{
if(l==r){
sum[rt]=val;
ans[rt]=val;
return;
} int m=(l+r)>>;
if(p<=m) update(p,val,lson);
else update(p,val,rson);
pushup(rt);
} int main()
{
int n, m;
while(~scanf("%d%d",&n,&m)){
build(,n,);
while(m--){
int op;
scanf("%d",&op);
if(op==){
int l,r;
scanf("%d%d",&l,&r);
Len=r-l+;
printf("%lld\n",query(l,r,,n,));
}
else{
int pos;
ll val;
scanf("%d%lld",&pos,&val);
update(pos,val,,n,);
}
}
}
return ;
}

还有一份学长过的(啊啊啊啊,好厉害,羞涩,哈哈哈)

 #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <utility>
#include <stack>
#include <list>
using namespace std;
typedef long long LL;
const int N = 1e5+,M = 1e3+,inf = 0x3f3f3f3f;
const LL mod = 1e9+;
const double epx = 1e-;
const double PI = acos(-1.0); #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); LL a[N],sum[M],block[M],pos[N];
int k;
void init(int n)
{
k=sqrt(n);
memset(sum,,sizeof(sum));
memset(block,,sizeof(block));
for(int i=;i<=n;i++)
pos[i]=(i-)/k+;
for(int i=;i<=n/k;i++)
{
int L=(i-)*k+;
int R=i*k;
for(int j=L,t=k;j<=R;j++,t--)
{
sum[i]+=a[j];
block[i]+=a[j]*(1LL*t);
}
}
}
void change(int b,int c)
{
int i=pos[b];
a[b]=c;
int L=(i-)*k+;
int R=i*k;
sum[i]=;
block[i]=;
for(int j=L,t=k;j<=R;j++,t--)
{
sum[i]+=a[j];
block[i]+=a[j]*(1LL*t);
}
}
LL query(int L,int R)
{
LL ans=;
if(pos[L]==pos[R])
{
for(int i=L,len=(R-L+);i<=R;i++,len--)
{
ans+=1LL*a[i]*len;
}
return ans;
}
int len=(R-L+);
for(int i=L;i<=pos[L]*k;i++)
{
ans+=1LL*a[i]*len;len--;
}
for(int i=pos[L]+;i<pos[R];i++)
{
ans+=block[i];
ans+=1LL*sum[i]*(len-k);
len-=k;
}
for(int i=(pos[R]-)*k+;i<=R;i++)
{
ans+=1LL*a[i]*len;len--;
}
return ans;
}
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
init(n);
while(q--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==)
{
printf("%lld\n",query(b,c));
}
else if(a==)
{
change(b,c);
}
}
}
return ;
}

就先这样,溜了。

上一篇:ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (思维,贪心)


下一篇:设计模式——备忘录模式(C++实现)