原理

#include #define fire(a) input.reset(new InputFile(a".in")),output.reset(new OutputFile(a".out")) #define text() input.reset(new InputFile()),output.reset(new OutputFile()) #define online() input.reset(new InputFile(stdin,false)),output.reset(new OutputFile()) using namespace std; templatestruct is_iterator{template::value,int>::type=0>constexpr static auto has_indirection(int)->decltype(*declval(),bool()){return true;}templateconstexpr static bool has_indirection(long){return false;}constexpr static bool value=has_indirection(0);};using uint=unsigned int;const uint BUFFER_SIZE=1<<12;const uint MAX_LENGTH=1<<7;namespace Detail{struct Width{uint value;};struct Fill{char value;};struct Base{uint value;};struct Precision{uint value;};struct Delimiter{const char*value;};}Detail::Width setWidth(uint value=0){return{value};}Detail::Fill setFill(char value=' '){return{value};}Detail::Base setBase(uint value=10){assert(2<=value&&value<=36);return{value};}Detail::Precision setPrecision(uint value=9){assert(value=tail,false))fillInput();return*head++;}templateint readUnsignedIntGeneral(I&arg,char c){I value=0;int length=0;for(;;++length,c=nextChar()){if(isDigit(c))c-='0';else if(isUpper(c))c-='A'-10;else if(isLower(c))c-='a'-10;else c=base;if(c>=base)break;value=base*value+c;}arg=value;return--head,length;}templateinline int readUnsignedInt(I&arg,char c){if(__builtin_expect(base>10,false))return readUnsignedIntGeneral(arg,c);I value=0;int length=0;for(;static_cast(c-'0')<>inline bool readSignedInt(I&arg,char c){bool negative=c=='-';if(negative)c=nextChar();typename make_unsigned::type unsignedArg;if(readUnsignedInt(unsignedArg,c)==0)return false;arg=negative?~static_cast(unsignedArg-1):static_cast(unsignedArg);return true;}templatebool readFloatingPoint(F&arg,char c){bool negative=c=='-';if(negative)c=nextChar();unsigned long long integerPart;if(readUnsignedInt(integerPart,c)==0)return false;arg=static_cast(integerPart);if(nextChar()=='.'){unsigned long long fractionalPart=0;int fractionalLength=readUnsignedInt(fractionalPart,nextChar());if(fractionalLength>0){unsigned long long basePower=1;for(;fractionalLength;--fractionalLength)basePower*=base;arg+=static_cast(fractionalPart)/basePower;}}else--head;if(negative)arg=-arg;return true;}public:uint base;InputDevice(InputDevice const&)=delete;InputDevice&operator=(InputDevice const&)=delete;static inline bool isSpace(char c){return static_cast(c-'\t')<5||c==' ';}static inline bool isDigit(char c){return static_cast(c-'0')<10;}static inline bool isUpper(char c){return static_cast(c-'A')<26;}static inline bool isLower(char c){return static_cast(c-'a')<26;}static inline bool isOneOf(char c,const char*str){return strchr(str,c)!=nullptr;}void putBack(){--head;}inline bool readChar(char&arg){if(__builtin_expect(head>=tail,false)){fillInput();if(__builtin_expect(head>=tail,false))return arg='\0',false;}return arg=*head++,true;}templateinline char skipCharacters(UnaryPredicate isSkipped){char c;do{c=nextChar();}while(isSkipped(c));return c;}inline char skipCharacters(){return skipCharacters(isSpace);}templateinline int readString(char*arg,int limit,UnaryPredicate isTerminator){skipCharacters(isTerminator);int charsRead=0;for(--head,--limit;headinline typename enable_if<>::value&&is_unsigned::value,bool>::type read(I&arg){return readUnsignedInt(arg,skipCharacters())>0;}templateinline typename enable_if<>::value&&is_signed::value,bool>::type read(I&arg){return readSignedInt(arg,skipCharacters());}templateinline typename enable_if<>::value,bool>::type read(F&arg){return readFloatingPoint(arg,skipCharacters());}inline bool read(const char&arg){skipCharacters([arg](char c){return arg!=c;});return true;}inline bool read(const char*arg){if(*arg)skipCharacters([arg](char c){return InputDevice::isOneOf(c,arg);});else skipCharacters();return putBack(),true;}inline bool read(bool(*isSkipped)(char)){skipCharacters(isSkipped);putBack();return true;}templateinline typename enable_if<>::value,bool>::type read(char*arg,I limit,Terminator terminator,Ts&&...args){readString(arg,static_cast(limit),terminator);return read(forward(args)...);}templateinline typename enable_if<>::value,bool>::type read(char*arg,I limit){return read(arg,limit,"");}templateinline bool read(char*first,char*last,Ts&&...args){return read(first,static_cast(last-first),forward(args)...);}templateinline bool read(char(&arg)[N],Ts&&...args){return read(static_cast(arg),N,forward(args)...);}templateinline bool read(string&arg,Terminator terminator,Ts&&...args){for(int length=16,last=0;;last+=length,length<<=1){arg.resize(last+length);int charsRead=readString(&arg[last],length+1,terminator);if(charsRead(args)...);}}}inline bool read(string&arg){return read(arg,"");}templateinline bool read(pair&arg){return read(arg.first,arg.second);}templateinline bool read(complex&arg){T real,imag;if(!read(real,imag))return false;arg.real(real),arg.imag(imag);return true;}templateinline bool read(vector&arg){uint n;if(!read(n))return false;arg.resize(n);return read(arg.begin(),arg.end());}templateinline typename enable_if<>::value,bool>::type read(Iterator first,Iterator last,Ts&&...args){for(;first!=last;++first)if(!read(*first))return false;return read(forward(args)...);}templateinline typename enable_if<>::value&&is_integral::value,bool>::type read(Iterator first,I count,Ts&&...args){return read(first,first+count,forward(args)...);}templateinline auto read(T&arg)->decltype(arg.read(*this)){return arg.read(*this);}templateinline typename enable_if::value&&!is_convertible::value,bool>::type read(T0&&arg0,T1&&arg1,Ts&&...args){return read(forward(arg0))&&read(forward(arg1),forward(args)...);}};class InputFile:public InputDevice{FILE*file;bool lineBuffered;bool owner;char buffer[BUFFER_SIZE];void fillInput()override{head=buffer;*buffer='\0';if(__builtin_expect(!lineBuffered,true)){tail=head+fread(buffer,1,BUFFER_SIZE,file);}else{tail=head;if(fgets(buffer,BUFFER_SIZE,file))while(*tail)++tail;}}public:InputFile(FILE*file=stdin,bool lineBuffered=true,bool takeOwnership=false):InputDevice(buffer,buffer),file(file),lineBuffered(lineBuffered),owner(takeOwnership){}InputFile(const char*fileName):InputFile(fopen(fileName,"r"),false,true){}~InputFile(){if(owner)fclose(file);}};class InputString:public InputDevice{void fillInput()override{while(*tail)++tail;}public:InputString(const string&s):InputDevice(s.data(),s.data()+s.size()){}InputString(const char*s):InputDevice(s,s+strlen(s)){}};class OutputDevice{protected:char buffer[BUFFER_SIZE+MAX_LENGTH];char*output;char*end;bool separate;OutputDevice():output(buffer),end(buffer+BUFFER_SIZE+MAX_LENGTH),separate(false),width(setWidth().value),fill(setFill().value),base(setBase().value),precision(setPrecision().value),delimiter(setDelimiter().value){computeBasePower();}virtual void writeToDevice(uint count)=0;inline void flushMaybe(){if(__builtin_expect(output>=buffer+BUFFER_SIZE,false)){writeToDevice(BUFFER_SIZE);output=copy(buffer+BUFFER_SIZE,output,buffer);}}void computeBasePower(){basePower=1;for(uint i=0;i<>inline char*writeUnsignedInt(I arg,char*last){if(__builtin_expect(arg==0,false))*--last='0';if(__builtin_expect(base==10,true)){for(;arg;arg/=10)*--last='0'+arg%10;}else for(;arg;arg/=base){I digit=arg%base;*--last=digit<10?'0'+digit:'A'-10+digit;}return last;}templateinline char*writeSignedInt(I arg,char*last){auto unsignedArg=static_cast::type>(arg);if(arg<0){last=writeUnsignedInt(~unsignedArg+1,last);*--last='-';return last;}return writeUnsignedInt(unsignedArg,last);}templatechar*writeFloatingPoint(F arg,char*last){bool negative=signbit(arg);if(negative)arg=-arg;if(isnan(arg))for(int i=0;i<3;++i)*--last=i["NaN"];else if(isinf(arg))for(int i=0;i<3;++i)*--last=i["fnI"];else{auto integerPart=static_cast(arg);auto fractionalPart=static_cast((arg-integerPart)*basePower+F(0.5));if(fractionalPart>=basePower)++integerPart,fractionalPart=0;char*point=last-precision;if(precision>0){::fill(point,writeUnsignedInt(fractionalPart,last),'0');*--point='.';}last=writeUnsignedInt(integerPart,point);}if(negative)*--last='-';return last;}inline int writeT(char*first){int delimiterLenght=separate?writeDelimiter():0;separate=true;uint charsWritten=static_cast(end-first);if(__builtin_expect(charsWritten(charsWritten);}inline int writeFill(uint count){int charsWritten=static_cast(count);if(__builtin_expect(output+count+MAX_LENGTH(buffer+BUFFER_SIZE-output);;chunkSize=BUFFER_SIZE){if(chunkSize>count)chunkSize=count;output=fill_n(output,chunkSize,fill);flushMaybe();if((count-=chunkSize)==0)break;}return charsWritten;}public:uint width;char fill;uint base;uint precision;unsigned long long basePower;string delimiter;OutputDevice(OutputDevice const&)=delete;OutputDevice&operator=(OutputDevice const&)=delete;virtual~OutputDevice(){};inline int writeChar(char arg){separate=false;*output++=arg;flushMaybe();return 1;}inline int writeString(const char*arg,size_t length,bool checkWidth=true){separate=false;uint count=static_cast(length);int charsWritten=static_cast(count)+(checkWidth&&count<>(buffer+BUFFER_SIZE-output);;chunkSize=BUFFER_SIZE){if(chunkSize>count)chunkSize=count;output=copy_n(arg,chunkSize,output);flushMaybe();if((count-=chunkSize)==0)break;arg+=chunkSize;}return charsWritten;}inline int writeDelimiter(){return writeString(delimiter.c_str(),delimiter.size(),false);}inline void flush(){writeToDevice(static_cast(output-buffer));output=buffer;}inline int write(Detail::Width newWidth){width=newWidth.value;return 0;}inline int write(Detail::Fill newFill){fill=newFill.value;return 0;}inline int write(Detail::Base newBase){base=newBase.value;computeBasePower();return 0;}inline int write(Detail::Precision newPrecision){precision=newPrecision.value;computeBasePower();return 0;}inline int write(Detail::Delimiter newDelimiter){delimiter=newDelimiter.value;return 0;}inline int write(){return 0;}inline int write(char arg){return writeChar(arg);}templateinline typename enable_if<>::value&&is_unsigned::value,int>::type write(I arg){return writeT(writeUnsignedInt(arg,end));}templateinline typename enable_if<>::value&&is_signed::value,int>::type write(I arg){return writeT(writeSignedInt(arg,end));}templateinline typename enable_if<>::value,int>::type write(F arg){return writeT(writeFloatingPoint(arg,end));}inline int write(const char*arg){return writeString(arg,strlen(arg));}templateinline int write(char(&arg)[N]){return writeString(arg,strlen(arg));}inline int write(const string&arg){return writeString(arg.c_str(),arg.size());}templateinline int write(const pair&arg){int charsWritten=write(arg.first);charsWritten+=writeDelimiter();return charsWritten+write(arg.second);}templateinline int write(const complex&arg){return write(real(arg),imag(arg));}templateinline typename enable_if<>::value,int>::type write(Iterator first,Iterator last,Ts&&...args){int charsWritten=0;for(;first!=last;charsWritten+=++first==last?0:writeDelimiter())charsWritten+=write(*first);return charsWritten+write(forward(args)...);}templateinline typename enable_if<>::value&&is_integral::value,int>::type write(Iterator first,I count,Ts&&...args){return write(first,first+count,forward(args)...);}templateinline auto write(const T&arg)->decltype(arg.write(*this)){return arg.write(*this);}templateinline typename enable_if::value,int>::type write(T0&&arg0,T1&&arg1,Ts&&...args){int charsWritten=write(forward(arg0));return charsWritten+write(forward(arg1),forward(args)...);}};class OutputFile:public OutputDevice{FILE*file;bool owner;void writeToDevice(uint count)override{fwrite(buffer,1,count,file);fflush(file);}public:OutputFile(FILE*file=stdout,bool takeOwnership=false):file(file),owner(takeOwnership){}OutputFile(const char*fileName):OutputFile(fopen(fileName,"w"),true){}~OutputFile()override{flush();if(owner)fclose(file);}};class OutputString:public OutputDevice{string&str;void writeToDevice(uint count)override{str.append(buffer,count);}public:OutputString(string&str):OutputDevice(),str(str){}~OutputString()override{flush();}};unique_ptrinput;unique_ptroutput;templateinline bool read(Ts&&...args){return input->read(forward(args)...);}templateinline int write(Ts&&...args){return output->write(forward(args)...);}templateinline int writeln(Ts&&...args){return write(forward(args)...,'\n');}void flush(){output->flush();} #define ull unsigned long long #define int long long #define INF (0x66ccff0712ll) #define inf LLONG_MAX #define M (0x6cf) #define N (0x66ccff) #define MAXN (int)(1e6+5) #define MAXM (int)(1e5+5) #define re register #define it map::iterator #define endl "\n" #define PII pair #define for_(a,b,c) for(int a=b;a<=c;a++) #define _for(a,b,c) for(int a=b;a>=c;a--) #define lc(q) (son[q][0]) #define rc(q) (son[q][1]) #define mid(l,r) ((l+r)>>1) namespace solve{ int a[70005],Log[140005],n,len=1,dep=0,q; int loc[70005],sum[18][70005],ans[18][70005]; namespace CatTree{ inline void build(int n,int d){ for_(i,1,n) loc[i]=i+n-1; for(int len=2,q=d-1;len<=n;len<<=1,q--){ for(int l=1;l<=n;l+=len){ int r=l+len-1; sum[q][mid(l,r)]=a[mid(l,r)]; sum[q][mid(l,r)+1]=a[mid(l,r)+1]; _for(i,mid(l,r)-1,l) sum[q][i]=sum[q][i+1]+a[i]; for_(i,mid(l,r)+2,r) sum[q][i]=sum[q][i-1]+a[i]; _for(i,mid(l,r)-1,l) sum[q][i]=max(sum[q][i],sum[q][i+1]); for_(i,mid(l,r)+2,r) sum[q][i]=max(sum[q][i],sum[q][i-1]); ans[q][mid(l,r)]=a[mid(l,r)],ans[q][mid(l,r)+1]=a[mid(l,r)+1]; _for(i,mid(l,r)-1,l) ans[q][i]=max(ans[q][i+1],0ll)+a[i]; for_(i,mid(l,r)+2,r) ans[q][i]=max(ans[q][i-1],0ll)+a[i]; _for(i,mid(l,r)-1,l) ans[q][i]=max(ans[q][i+1],ans[q][i]); for_(i,mid(l,r)+2,r) ans[q][i]=max(ans[q][i-1],ans[q][i]); } } } int ask(int l,int r){ if(l==r) return a[l]; int q=Log[loc[l]]-Log[loc[l]^loc[r]]-1; return max({ans[q][l],ans[q][r],sum[q][l]+sum[q][r]}); } }; using namespace CatTree; inline void In(){ read(n); while(len>1]+1; build(len,dep); read(q); for_(i,1,q){ int l,r; read(l,r); writeln(ask(l,r)); } } } using namespace solve; signed main(){ fire("data"); In(); }