DataStructureProblem

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers n and m , which are the length of the two sequences and the number of operations. The second line contains n integers $a_1, a_2, \ldots, a_n$ . The third line contains n integers $b_1, b_2, \ldots, b_n$ . Each of the last m lines contains a query.

* $1 \leq n, m \leq 2 \times 10^5$
* $-10^9 \leq a_i, b_i, y \leq 10^9$
* $1 \leq x \leq n$
* The sum of n and the sum of m do not exceed $2 \times 10^6$ .

C++(clang++11) 解法, 执行用时: 1345ms, 内存消耗: 15416K, 提交时间: 2020-11-03 15:22:10

#include<bits/stdc++.h>
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
#define ll long long
using namespace std;
const int nx=2e5+5;
int a[nx],b[nx];
ll mx[nx<<2],s[nx<<2],suf,ans;
inline void wk(int p){
	mx[p]=max(mx[p<<1]+s[p<<1|1],mx[p<<1|1]);
	s[p]=s[p<<1]+s[p<<1|1];
}
void build(int p,int l,int r){
	if(l==r){
		mx[p]=a[l],s[p]=b[l];
		return;
	}int mid=l+r>>1;
	build(ls),build(rs);
	wk(p);
} 
void up(int p,int l,int r,int x,int y){
	if(l==r){
		mx[p]=a[l],s[p]=b[l];
		return;
	}int mid=l+r>>1;
	if(x<=mid)up(ls,x,y);
	else up(rs,x,y);
	wk(p);
}
void get(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		ans=max(ans,mx[p]+suf),suf+=s[p];
		return;
	}int mid=l+r>>1;
	if(mid<y)get(rs,x,y);
	if(x<=mid)get(ls,x,y);
}
int main(){
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;++i)scanf("%d",a+i);
		for(int i=1;i<=n;++i)scanf("%d",b+i);
		build(1,0,n);
		int op,x,y;
		for(int i=1;i<=m;++i){
			scanf("%d%d",&op,&x);
			if(op==1)scanf("%d",&y),a[x]=y,up(1,0,n,x,y);
			else if(op==2)scanf("%d",&y),b[x]=y,up(1,0,n,x,y);
			else ans=-1e18,suf=0,get(1,0,n,0,x),printf("%lld\n",ans);
		}			
	}
}

详情