Codeforces - Nastya and King-Shamans_青烟绕指柔!的博客-程序员秘密

题目链接：Codeforces - Nastya and King-Shamans

显然，每次 * 2倍增最多进行log次，所以我们在线段树上二分，找到第一个 2 * a[i] 的位置即可。

然后线段树维护前缀和的max

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,q,a[N],mx[N<<2],lazy[N<<2];
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){
    
    int x=0,f=1; char ch=gc();
    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=gc();}
    return x*f;
}
#define mid (l+r>>1)
inline void push_down(int p){
    
	mx[p<<1]+=lazy[p],mx[p<<1|1]+=lazy[p];
	lazy[p<<1]+=lazy[p],lazy[p<<1|1]+=lazy[p];
	lazy[p]=0; 
}
void change(int p,int l,int r,int ql,int qr,int v){
    
	if(l==ql&&r==qr){
    mx[p]+=v,lazy[p]+=v; return ;}
	push_down(p);
	if(qr<=mid)	change(p<<1,l,mid,ql,qr,v);
	else if(ql>mid)	change(p<<1|1,mid+1,r,ql,qr,v);
	else change(p<<1,l,mid,ql,mid,v),change(p<<1|1,mid+1,r,mid+1,qr,v);
	mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int ask(int p,int l,int r,int x){
    
	if(l==r)	return mx[p];
	push_down(p);
	if(x<=mid)	return ask(p<<1,l,mid,x);
	else	return ask(p<<1|1,mid+1,r,x);
}
int rk(int p,int l,int r,int v){
    
	if(l==r)	return l;
	push_down(p);
	if(mx[p<<1]>=v)	return rk(p<<1,l,mid,v);
	else	return rk(p<<1|1,mid+1,r,v);
}
signed main(){
    
	n=read(),q=read();
	for(int i=1;i<=n;i++)	a[i]=read(),change(1,1,n,i,n,a[i]);
	for(int i=1,x,y,pos,ok;i<=q;i++){
    
		x=read(),y=read(); change(1,1,n,x,n,y-a[x]); a[x]=y; pos=1; ok=-1;
		if(a[1]==0)	ok=1;
		while(pos<n&&ok==-1){
    
			int tmp=ask(1,1,n,pos);
			int v=rk(1,1,n,2*tmp);
			if(a[v]==ask(1,1,n,v-1))	ok=v;
			pos=v;
		}
		printf("%lld\n",ok);
	}
	return 0;
}

本文链接：https://blog.csdn.net/weixin_43826249/article/details/106898235

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【Android功能测试如何定位bug】_王海杰969的博客-程序员秘密

话不多说，直接上定位1.4XX 客户端问题，比如发生了401，那么要看下是否带了正确的身份验证信息；发生了403则要看下是否有权限访问；404则要看下对应的URL是否真实存在；真实场景（直接提bug给前端开发，管他4几几，哈哈） 2.5xx服务端出现问题（配合服务器log进行定位，发生了502错误则可能是服务器挂了导致的问题、发生503 错误可能是由于网络过载导致的问题、发生504错误则可能是程序执行时间过长导致超时）；真实场景（直接提bug给后端开发，管他5几几，哈哈）3.android功能测

curl -I 说明_weixin_30279315的博客-程序员秘密

curl -I 查看header头信息转载于:https://www.cnblogs.com/djwhome/p/9564611.html

程序设计小游戏java_JavaGUI编程之贪吃蛇小游戏原码_AkaCMD的博客-程序员秘密

直接放原码./src/statics 下图标文件,注意命名规范body.pngdown.pngfood.pngleft.pngright.pngup.pngheader.png./src/com 下三个代码文件Data.javapackage com;import javax.swing.*;import java.net.URL;// 数据中心public class Data {// 相对路径...

使用java读取csv文件并保存_小王很nice的博客-程序员秘密

C:/Users/DELL/Desktop/graduation/iris/iris.csvjava编码实现package pers.wym.em;import java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;public class emIrisClassi

SSA（static single assignment)（静态单赋值）_ssa 静态单赋值_音程的博客-程序员秘密

SSA属于控制流分析，所以有些相关的概念如控制流图，控制树，n控制m，直接控制和真控制需要参考如下文章：控制流分析引入例如：SSA一个问题：这是肯定的，有了SSA，做出上面的判断不难。上面都是一些简单的SSA改写，下面有分支，则更加麻烦，需要一些程序化的方法（后面介绍）。如下：这个时候经过分支之后，对x引用，我们很难知道到底引用了哪一个x,所以我们引入了一个非常重要的PHINode也就是ϕ\phiϕ节点，从而将这个SSA的初衷完成。初衷前面已经说了，现在啰嗦一遍，即：这样，我们

swift中利用系统线程实现异步加载数据同步更新UI_weixin_33905756的博客-程序员秘密

swift中的使用案例样式// Mark: -数据源更新 typealias AddDataBlock = () ->Void var updataBlock:AddDataBlock?func loadLiveData(){ let grpup = DispatchGroup() grpup.enter() ...