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

· · 题解

很暴力的解法。为啥我想了这么久（我不到啊讨论区里说 3log 能过我就来了。）

查询操作里，维护这个 yuuki 数，设其为 ans。有一个很显然的，就是所有面值不大于 ans 的数 x 都可以合并，此时 ans 变为 ans+x。

这里发现，x 要满足不会在上一次被合并，简单注意力一下，想要卡满必须满足区间内的数是斐波那契数列。

所以 ans 的增长下界严格上是 1.618 的。

最后的话。要维护单点修改和二维数点。直接暴力二维树状数组即可。时间复杂度 O(N\log^2 N+Q\log^2N\log V)。但是这里离散化了，并且 \log V 这块可能特别小，所以完全完全跑不满。

https://www.luogu.com.cn/record/304963053

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
template <typename _Tp> inline void read(_Tp&x){
    char ch;
    bool f=0;
    x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-')f=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(f) x=-x;
}
template <typename _Tp> inline void print(_Tp x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
#define ll long long
const int N=200010;
int n,m,a[N],q1[N],q2[N],q3[N];
vector<int> val[N];
vector<ll> tr[N];
inline void add(int x,int v,int f){
    for(;x<=n;x+=x&-x){
        int j=lower_bound(val[x].begin(),val[x].end(),v)-val[x].begin()+1;
        for(;j<tr[x].size();j+=j&-j) tr[x][j]+=1ll*v*f;
    }
}
inline ll query(int x,ll y){
    ll s=0;
    for(;x;x-=x&-x){
        int j=upper_bound(val[x].begin(),val[x].end(),y)-val[x].begin();
        for(;j;j-=j&-j) s+=tr[x][j];
    }
    return s;
}
signed main(){
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++){
        read(q1[i]),read(q2[i]),read(q3[i]);
        if(q1[i]==1){for(int j=q2[i];j<=n;j+=j&-j) val[j].push_back(q3[i]);}
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=j&-j) val[j].push_back(a[i]);
        sort(val[i].begin(),val[i].end());
        val[i].erase(unique(val[i].begin(),val[i].end()),val[i].end());
        tr[i].assign(val[i].size()+1,0);
    }
    for(int i=1;i<=n;i++) add(i,a[i],1);
    for(int i=1;i<=m;i++){
        if(q1[i]==1) add(q2[i],a[q2[i]],-1),a[q2[i]]=q3[i],add(q2[i],q3[i],1);
        else{
            ll ans=1,s=query(q3[i],1)-query(q2[i]-1,1);
            while(s>=ans) ans=s+1,s=query(q3[i],ans)-query(q2[i]-1,ans);
            print(ans),putchar('\n');
        }
    }
    return 0;
}

::::