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

Wei_Han · 2026-10-22 19:19:44 · 题解

考察选手是否做过 P4587。

考虑怎么快速回答询问，我们可以对区间排序，从小到大处理和，不妨记当前和是 S，每次只要 a_i \le S+1 就可以加入集合，并且 S \gets S + a_i。

考虑加速这个过程，我们从 S=0 开始，每次肯定都可以加入所有 \le S+1 的数，将他们直接加入集合，记新和是 S'，显然，如果还想继续操作的话，肯定需要存在 S+1 < x \le S'+1，那么显然只要存在这样一个 x，S 就会翻倍，所以这样暴力加和只会进行 \log V 轮，我们只需要区间在值域上的前缀和。

所以这样就可以做静态问题了，拿主席树维护值域，查询时两棵树作差，可以做到 O(n\log^2 n)。

但是有单点修改怎么办，不难发现这个询问其实是个 \text{2-side} 矩形查询，可以直接拿树套树维护，复杂度 O(n\log^3 n)。

但是这太难写了，注意到时限比较松，直接拿带修莫队加分块维护这个东西，每次查询前缀和即可，复杂度 O(n^{\frac{5}{3}} + n\sqrt n\log n)。

稍微卡一卡常数就跑进了 1s。

:::info[代码]

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar(10)
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define tri tuple<ll,ll,ll>
#define gt(k,x) (get<k>(x))
#define pdi pair<double,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(ll i = (a) ; i <= (b) ; ++ i )
#define Fo(a,i,b) for(ll i = (a) ; i >= (b) ; -- i )
#define pb push_back
#define reg register
#define eb emplace_back
#define bct __builtin_popcount 
#define mk make_pair
#define IT iterator
#define all(x) x.begin(),x.end()
#define lbd lower_bound
#define ubd upper_bound
#define lowbit(x) ((x)&(-(x)))
#define gb(x,i) (((x)>>i)&1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define deb(a...) [&](auto...b){char s[]=" , ,"#a;strtok(s,",");((cerr<<strtok(0,",")<<"="<<b<<"; "),...)<<endl;}(__LINE__,a)
// #pragma GCC optimize("O3")
using namespace std;
bool ST;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long long ull;
typedef __int128 i128;
typedef __uint128_t u128;
typedef double db;

typedef int ll;
// typedef long long ll;
// typedef __int128 ll;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

const ll mod=1e9+7;
template <class T> inline bool ckmn(T &a,T b){return a>b?a=b,1:0;}
template <class T> inline bool ckmx(T &a,T b){return a<b?a=b,1:0;}
template <class T> inline void _A(T &x,T y){x=(x+y>=mod?x+y-mod:x+y);}
template <class T> inline void _M(T &x,T y){x=1ll*x*y%mod;}
template <class T> inline T A_(T x,T y){return (x+y>=mod?x+y-mod:x+y);}
template <class T> inline T M_(T x,T y){return 1ll*x*y%mod;}
template <class T> inline void read(T &s)
{
   s=0;reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
   while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;
}
template <class T> inline void wr(T x)
{
   if(x<0)putchar('-'),x=-x;int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;
   if(!top)buf[++top]=0;while(top)putchar(buf[top--]^'0');return;
}
template <class T, class ...A> inline void read(T &x,A &...a){read(x);read(a...);}
template <class T, class ...A> inline bool ckmn(T &x,T y,A ...a){return ckmn(x,y)|ckmn(x,a...);}
template <class T, class ...A> inline bool ckmx(T &x,T y,A ...a){return ckmx(x,y)|ckmx(x,a...);}
template <class T, class ...A> inline void _A(T &x,T y,A ...a){_A(x,y),_A(x,a...);}
template <class T, class ...A> inline void _M(T &x,T y,A ...a){_M(x,y),_M(x,a...);}
template <class T, class ...A> inline T A_(T x,T y,A ...a){return A_(A_(x,y),a...);}
template <class T, class ...A> inline T M_(T x,T y,A ...a){return M_(M_(x,y),a...);}

const ll _N=1e6+5;ll Pre[_N],Inv[_N];
inline ll qpow(ll a,ll b){return !b?1ll:M_(1ll*qpow(M_(a,a),b>>1ll),((b&1ll)?a:1ll));}
inline ll C(ll n,ll m){return (n<m||n<0||m<0)?0ll:M_(Pre[n],Inv[m],Inv[n-m]);}
inline void InitC(ll n){Pre[0]=1;fo(1,i,n) Pre[i]=M_(Pre[i-1],i);Inv[n]=qpow(Pre[n],mod-2);Fo(n-1,i,1) Inv[i]=M_(Inv[i+1],(i+1));Inv[0]=1;}

const ll N=1e6+5,M=1e5+5;
ll n,q,op,l,r,a[N],L[N],R[N],bel[N];i64 res[N],resb[N],ans[N],cur;array<ll,2> _upd[N];vector<array<ll,3>> Q;
inline void upd(ll x,ll op){
    if(op>0) res[x]+=x,resb[bel[x]]+=x,cur+=x;
    else     res[x]-=x,resb[bel[x]]-=x,cur-=x;
}
inline i64 pqry(ll k)
{
    i64 ans=0;ll b=bel[k];
    fo(1,i,b-1) ans+=resb[i];
    fo(L[b],i,k) ans+=res[i];
    return ans;
}
bool ED;
signed main(){
    read(n,q);
    ll m=0;fo(1,i,n) read(a[i]),ckmx(m,(ll)a[i]);
    fo(1,i,q) read(op,l,r),
        op==1?(_upd[i]={l,r},ckmx(m,(ll)r)):(Q.pb({l,r,i}),1);
    ll _len=max(1,(ll)pow(n,2.0/3.0)),len=max(1,(ll)sqrt(m)),cnt=(m-1)/len+1;
    fo(1,i,cnt) L[i]=R[i-1]+1,R[i]=L[i]+len-1;
    ckmn(R[cnt],m);
    fo(1,i,m) bel[i]=(i-1)/len+1;
    sort(all(Q),[&](auto x,auto y)
        {
            return x[0]/_len==y[0]/_len?(x[1]/_len==y[1]/_len?x[2]<y[2]:x[1]/_len<y[1]/_len):x[0]/_len<y[0]/_len;
        });
    mem(ans,-1);ll _l=1,_r=0,_t=0;for(auto [l,r,id]:Q)
    {
        while(_r<r) upd(a[++_r],1);
        while(_l>l) upd(a[--_l],1);
        while(_r>r) upd(a[_r--],-1);
        while(_l<l) upd(a[_l++],-1);
        while(_t<id)
        {
            ++_t;if(!_upd[_t][0]) continue;
            if(_upd[_t][0]>=_l&&_upd[_t][0]<=_r)
                upd(a[_upd[_t][0]],-1);
            swap(a[_upd[_t][0]],_upd[_t][1]);
            if(_upd[_t][0]>=_l&&_upd[_t][0]<=_r)
                upd(a[_upd[_t][0]],1);
        }
        while(_t>id)
        {
            if(!_upd[_t][0]){--_t;continue;}
            if(_upd[_t][0]>=_l&&_upd[_t][0]<=_r)
                upd(a[_upd[_t][0]],-1);
            swap(a[_upd[_t][0]],_upd[_t][1]);
            if(_upd[_t][0]>=_l&&_upd[_t][0]<=_r)
                upd(a[_upd[_t][0]],1);
            --_t;
        }
        i64 nw=0;while(nw<cur){ll k=nw+1>m?m:(ll)(nw+1);i64 s=pqry(k);if(s==nw) break;nw=s;}
        ans[id]=nw+1;
    }fo(1,i,q) if(_upd[i][0]==0) wr(ans[i]),pr;

    cerr << "Time: " << (double)clock()/CLOCKS_PER_SEC << "s\n";
    cerr << "Memory: " << abs(&ST - &ED) / 1024.0 / 1024.0 << " MB\n";
    return 0;
}

:::