1030F - Putting Boxes Together - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXSIZE=30000020;

int bufpos;

char buf[MAXSIZE];

#define NEG 1

void init(){

	#ifdef LOCAL

		freopen("1053C.txt","r",stdin);

	#endif

	buf[fread(buf,1,MAXSIZE,stdin)]='\0';

	bufpos=0;

}

#if NEG

int readint(){

	bool isneg;

	int val=0;

	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);

	bufpos+=(isneg=buf[bufpos]=='-');

	for(;isdigit(buf[bufpos]);bufpos++)

		val=val*10+buf[bufpos]-'0';

	return isneg?-val:val;

}

#else

int readint(){

	int val=0;

	for(;!isdigit(buf[bufpos]);bufpos++);

	for(;isdigit(buf[bufpos]);bufpos++)

		val=val*10+buf[bufpos]-'0';

	return val;

}

#endif

char readchar(){

	for(;isspace(buf[bufpos]);bufpos++);

	return buf[bufpos++];

}

int readstr(char* s){

	int cur=0;

	for(;isspace(buf[bufpos]);bufpos++);

	for(;!isspace(buf[bufpos]);bufpos++)

		s[cur++]=buf[bufpos];

	s[cur]='\0';

	return cur;

}

const int maxn=200002;

const int mod=1000000007;

struct bit{

	int n;

	ll a[maxn];

	void add(int p,ll v){

		for(;p<=n;p+=p&-p)

			a[p]+=v;

	}

	ll query(int p){

		ll ans=0;

		for(;p;p-=p&-p)

			ans+=a[p];

		return ans;

	}

}b1,b2;

ll a[maxn],w[maxn];

int main(){

	init();

	int n=readint(),q=readint();

	for(int i=1;i<=n;i++)

		a[i]=readint()-i;

	b1.n=b2.n=n;

	for(int i=1;i<=n;i++){

		w[i]=readint();

		b1.add(i,w[i]);

		b2.add(i,w[i]*a[i]%mod);

	}

	while(q--){

		int x=readint(),y=readint();

		if (x<0){

			x=-x;

			b1.add(x,y-w[x]);

			b2.add(x,y*a[x]%mod-w[x]*a[x]%mod);

			w[x]=y;

			continue;

		}

		ll o=b1.query(x-1),t=b1.query(y);

		int l=x,r=y;

		while(l<r){ //first delta>0

			int mid=(l+r)/2; //on a[mid]

			if (2*b1.query(mid)-o-t>0)

				r=mid;

			else l=mid+1;

		}

		ll ans=(b1.query(l)-o)%mod*a[l]-b2.query(l)+b2.query(x-1)+b2.query(y)-b2.query(l)-(t-b1.query(l))%mod*a[l];

		printf("%lld\n",(ans%mod+mod)%mod);

	}

}