题解：P17738 [ICPC 2019 Xuzhou R] Yuuki and a problem

· · 题解

思维难度大概在黄，建议评黄。

提供两个做法其中有 3\log 和 2\log 做法。

3\log

一眼做法。

用 神秘数 的做法，考虑原题是两个 \log 但是这个题有修改，所以考虑树套树维护即可。

不过我没写这个东西，不知道能不能过，如果假了就算了。

2\log

假设我们现在已经能表示到 [0,x-1] 从小到大加入数字。

如果 a>x 则答案就是 x。

否则扩大到 [0,x+a-1] 即 x \leftarrow x+a。

有了上面那个做法考虑值域倍增分块。

直接按照 [2^{b},2^{b+1}-1] 分块。

于是我们每一个块只需要最小值，和总和。

由于我们加入最小值，有。

x \ge mn_{b} \ge 2^{b}

于是对于每一个块我们只需要加入最小值就可以将整个块加入。

更形式化的，加入这一个块的最小值后就有。

x'=x+mn_{b}\ge 2^{b+1}

容易做到 \log{V}\log{n} 的。

code

:::success[AC code]

//Author:kevinZ99
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define fst first
#define sed second
#define pref static inline
using namespace std;using hint=__int128;using uhint=unsigned __int128;
using us=unsigned short;using ui=unsigned int;using ll=long long;using ull=unsigned long long;
using db=double;using ldb=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;
using pil=pair<int,ll>;using pli=pair<ll,int>;using vi=vector<int>;using vl=vector<ll>;
using vpi=vector<pii>;using vpl=vector<pll>;using vpil=vector<pil>;using vpli=vector<pli>;
ostream& out128(ostream&,uhint,bool);ostream& operator<<(ostream&,hint);ostream& operator<<(ostream&,uhint);
namespace mystl{
    const int SI=1<<22,SO=1<<20;pref size_t fr(void*p,size_t n){
#ifdef __linux__
        return fread_unlocked(p,1,n,stdin);
#else
        return fread(p,1,n,stdin);
#endif
    }
    unsigned char mp[1<<16];struct Init{Init(){memset(mp,255,sizeof mp);for(unsigned i=0;i<10;++i)for(unsigned j=0;j<10;++j){unsigned char s[2]={static_cast<unsigned char>('0'+i),static_cast<unsigned char>('0'+j)};uint16_t x;memcpy(&x,s,2);mp[x]=static_cast<unsigned char>(i*10+j);}}}init;
    pref unsigned pv(const char*p){uint16_t x;memcpy(&x,p,2);return mp[x];}
    struct IB:streambuf{
        char b[SI];bool eofed=false;IB(){setg(b,b,b);}
        int_type underflow()override{if(gptr()<egptr())return traits_type::to_int_type(*gptr());size_t n=fr(b,SI);if(!n)return traits_type::eof();setg(b,b,b+n);return traits_type::to_int_type(*gptr());}
        inline void commit(char*p){gbump(static_cast<int>(p-gptr()));}
        inline bool refill(char*&p,char*&e){commit(p);if(traits_type::eq_int_type(underflow(),traits_type::eof())){eofed=true;return false;}p=gptr();e=egptr();return true;}
        inline bool head(char*&p,char*&e,bool&neg){eofed=false;for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}neg=false;if(*p=='-'||*p=='+'){neg=*p=='-';++p;if(p==e&&!refill(p,e))return false;}return true;}
        template<class T,class U>inline bool slow(T&x,bool neg,char*&p,char*&e){U y=0;bool ok=false;for(;;){while(p<e){unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c>9){commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}ok=true;y=static_cast<U>(y*10+c);++p;}if(!refill(p,e)){if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}}}
        template<class T,class U,int K>inline bool num(T&x){x=0;char*p=gptr(),*e=egptr();bool neg;if(!head(p,e,neg))return false;if(e-p<2*K+1)return slow<T,U>(x,neg,p,e);U y=0;bool ok=false;for(int i=0;i<K;++i){unsigned v=pv(p);if(v>=255)break;ok=true;y=static_cast<U>(y*100+static_cast<U>(v));p+=2;}unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c<=9){ok=true;y=static_cast<U>(y*10+c);++p;}commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}
        inline bool read(short&x){return num<short,unsigned short,5>(x);}inline bool read(us&x){return num<us,us,5>(x);}inline bool read(int&x){return num<int,unsigned,5>(x);}inline bool read(unsigned&x){return num<unsigned,unsigned,5>(x);}inline bool read(long&x){return sizeof(long)<=4?num<long,unsigned long,5>(x):num<long,unsigned long,10>(x);}inline bool read(unsigned long&x){return sizeof(unsigned long)<=4?num<unsigned long,unsigned long,5>(x):num<unsigned long,unsigned long,10>(x);}inline bool read(ll&x){return num<ll,ull,10>(x);}inline bool read(ull&x){return num<ull,ull,10>(x);}inline bool read(hint&x){return num<hint,uhint,20>(x);}inline bool read(uhint&x){return num<uhint,uhint,20>(x);}
        inline bool read(char&x){x=0;eofed=false;char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e){x=*p++;commit(p);return true;}if(!refill(p,e))return false;}}
        inline bool read(string&x){eofed=false;x.clear();char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}for(;;){char*q=p;while(q<e&&static_cast<unsigned char>(*q)>32)++q;x.append(p,static_cast<size_t>(q-p));p=q;if(p<e){commit(p);return true;}if(!refill(p,e))return true;}}
        template<class T>inline bool fp(T&x){x=0;string s;if(!read(s))return false;return cv(s.c_str(),x);}static inline bool cv(const char*s,float&x){char*e=nullptr;x=strtof(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,double&x){char*e=nullptr;x=strtod(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,long double&x){char*e=nullptr;x=strtold(s,&e);return e!=s&&*e==0;}
    }ib;
    struct OB:streambuf{
        char b[SO];OB(){setp(b,b+SO);}~OB(){sync();}
        int sync()override{size_t n=static_cast<size_t>(pptr()-pbase());if(n&&fwrite(b,1,n,stdout)!=n)return -1;setp(b,b+SO);return 0;}
        int_type overflow(int_type c=traits_type::eof())override{if(sync())return traits_type::eof();if(!traits_type::eq_int_type(c,traits_type::eof()))*pptr()=traits_type::to_char_type(c),pbump(1);return traits_type::not_eof(c);}
        inline void pc(char c){if(pptr()==epptr()&&traits_type::eq_int_type(overflow(),traits_type::eof()))return;*pptr()=c;pbump(1);}inline void ps(const char*s,size_t n){while(n){size_t k=static_cast<size_t>(epptr()-pptr());if(!k){if(traits_type::eq_int_type(overflow(),traits_type::eof()))return;k=static_cast<size_t>(epptr()-pptr());}k=min(k,n);memcpy(pptr(),s,k);pbump(static_cast<int>(k));s+=k;n-=k;}}
    }ob;
    struct FastIn:istream{
        FastIn():istream(&ib){}using istream::operator>>;template<class T>inline FastIn&go(T&x){if(!ib.read(x))setstate(ib.eofed?ios::eofbit|ios::failbit:ios::failbit);else if(ib.eofed)setstate(ios::eofbit);return *this;}inline FastIn&operator>>(short&x){return go(x);}inline FastIn&operator>>(us&x){return go(x);}inline FastIn&operator>>(int&x){return go(x);}inline FastIn&operator>>(unsigned&x){return go(x);}inline FastIn&operator>>(long&x){return go(x);}inline FastIn&operator>>(unsigned long&x){return go(x);}inline FastIn&operator>>(ll&x){return go(x);}inline FastIn&operator>>(ull&x){return go(x);}inline FastIn&operator>>(hint&x){return go(x);}inline FastIn&operator>>(uhint&x){return go(x);}inline FastIn&operator>>(char&x){return go(x);}inline FastIn&operator>>(string&x){return go(x);}inline FastIn&operator>>(float&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(long double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(bool&x){int y=0;go(y);x=y!=0;return *this;}
    }fin;
    struct FastOut:ostream{
        FastOut():ostream(&ob){}using ostream::operator<<;template<class U>inline FastOut&uo(U x){char s[64];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);while(n)ob.pc(s[--n]);return *this;}template<class T>inline FastOut&so(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}typedef typename make_unsigned<T>::type U;U y;if(x<0){ob.pc('-');y=U(0)-static_cast<U>(x);}else y=static_cast<U>(x);return uo(y);}template<class T>inline FastOut&un(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}
        inline FastOut&operator<<(short x){return so(x);}inline FastOut&operator<<(us x){return un(x);}inline FastOut&operator<<(int x){return so(x);}inline FastOut&operator<<(unsigned x){return un(x);}inline FastOut&operator<<(long x){return so(x);}inline FastOut&operator<<(unsigned long x){return un(x);}inline FastOut&operator<<(ll x){return so(x);}inline FastOut&operator<<(ull x){return un(x);}inline FastOut&operator<<(bool x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}ob.pc(x?'1':'0');return *this;}inline FastOut&operator<<(char c){if(width()!=0){static_cast<ostream&>(*this)<<c;return *this;}ob.pc(c);return *this;}inline FastOut&operator<<(const char*s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s,strlen(s));return *this;}inline FastOut&operator<<(const string&s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s.data(),s.size());return *this;}inline FastOut&operator<<(float x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(double x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(long double x){static_cast<ostream&>(*this)<<x;return *this;}
        inline FastOut&operator<<(hint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}uhint y;if(x<0){ob.pc('-');y=uhint(0)-static_cast<uhint>(x);}else y=static_cast<uhint>(x);return uo(y);}inline FastOut&operator<<(uhint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}FastOut&operator<<(ios_base&(*f)(ios_base&)){f(*this);return *this;}FastOut&operator<<(ostream&(*f)(ostream&)){f(*this);return *this;}FastOut&operator<<(ios&(*f)(ios&)){f(*this);return *this;}
    }fout;
}
ostream& out128(ostream&out,uhint x,bool neg){char s[48];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);streamsize w=out.width(0),k=max<streamsize>(0,w-n-neg);char f=out.fill();ios::fmtflags a=out.flags()&ios::adjustfield;if(a==ios::left){if(neg)out.put('-');while(n)out.put(s[--n]);while(k--)out.put(f);}else if(a==ios::internal&&neg){out.put('-');while(k--)out.put(f);while(n)out.put(s[--n]);}else{while(k--)out.put(f);if(neg)out.put('-');while(n)out.put(s[--n]);}return out;}
ostream& operator<<(ostream&out,hint x){bool neg=x<0;return out128(out,neg?uhint(0)-static_cast<uhint>(x):static_cast<uhint>(x),neg);}ostream& operator<<(ostream&out,uhint x){return out128(out,x,false);}
#define cin mystl::fin
#define cout mystl::fout
namespace my{
    const int N=2e5+5,B=18,M=1<<19,inf=1000000000;template<typename T>pref T Min(T x,T y){return x<y?x:y;}template<typename T>pref T Max(T x,T y){return x>y?x:y;}template<typename T>pref T Abs(T x){return x<0?-x:x;}
    int n,q,base=1,tot=0,a[N],mn[B][M];
    ll sum[B][M];
    pref int bucket(int x){
        return 31-__builtin_clz(x);
    }
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    pref void modify(int b,int p,int x){
        p+=base-1;
        sum[b][p]=x,mn[b][p]=x?x:inf;
        for(p>>=1;p;p>>=1){
            sum[b][p]=sum[b][ls(p)]+sum[b][rs(p)];
            mn[b][p]=Min(mn[b][ls(p)],mn[b][rs(p)]);
        }
    }
    pref ll query(int l,int r){
        int L=l+base-1,R=r+base;
        ll ans=1;
        up(b,0,B-1){
            ll s=0;
            int v=inf;
            l=L,r=R;
            for(;l<r;l>>=1,r>>=1){
                if(l&1){
                    s+=sum[b][l],v=Min(v,mn[b][l]);
                    l++;
                }if(r&1){
                    r--;
                    s+=sum[b][r],v=Min(v,mn[b][r]);
                }
            }
            if(!s)continue;
            if(v>ans)break;
            ans+=s;
        }return ans;
    }
    pref void SOLVE(){
        cin>>n>>q;
        while(base<n)base<<=1;
        up(b,0,B-1)fill(mn[b],mn[b]+(base<<1),inf);
        up(i,1,n){
            cin>>a[i];
            int b=bucket(a[i]),p=base+i-1;
            sum[b][p]=mn[b][p]=a[i];
        }
        up(b,0,B-1)dn(p,base-1,1)
            sum[b][p]=sum[b][ls(p)]+sum[b][rs(p)],
            mn[b][p]=Min(mn[b][ls(p)],mn[b][rs(p)]);
        while(q--){
            int op,x,y;
            cin>>op>>x>>y;
            if(op==1){
                if(a[x]==y)continue;
                int b=bucket(a[x]),c=bucket(y);
                if(b!=c)modify(b,x,0);
                modify(c,x,y),a[x]=y;
            }else cout<<query(x,y)<<'\n';
        }
    }
}
int main(){my::SOLVE();return 0;}
/*
3log ez

考虑值域倍增，是不是对的。感觉是 nlogVlogn 

注意到巨大常数需要zkw 
*/

:::