# TPR Spring 2022
{%hackmd @fishhh/style %}

###### tags: `競程題解`,`競程`

Timestamp：2023/01/06

[題目連結](https://codeforces.com/group/H0qY3QmnOW/contest/377730/problem/B)

心得：
其實這題之前有點進去看過了，那時候想不出來。
後來想到，只要控制每一個種類的前綴和就好了! 這樣我就可以知道一個區間內有幾本書ㄌ
但是這是有修改的，所以必須用BIT或線段樹。
於是就建好了!

那再加上一個倍增二分搜，去找最遠需要走的地方即可。

我這題的解法好毒ww
是說官解簡單多ㄌ 直接開STL

ps : 本題的測資有一點點弱?，我下面那個程式有一個bug XD
原本抱持著就傳傳看的心態 然後就AC了 哈哈

#include "iostream"
using namespace std;
int bit[200010][110]={},n;
int sta[200010]={};
int lowbit(int kn){
    return kn&-kn;
}
void update(int mk,int pos,int v){
    for(;pos<=n;pos+=lowbit(pos)){
        bit[pos][mk]+=v;
    }
    return ;
}
int query(int pos,int m){
    int ret=0;
    for(;pos;pos-=lowbit(pos)){
        ret+=bit[pos][m];
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>sta[i];
        update(sta[i],i,1);
    }
    int t;
    cin>>t;
    while(t--){
        int q,p,c;
        cin>>q;
        if(q==1){
            cin>>p>>c;
            update(sta[p],p,-1);
            sta[p]=c;
            update(c,p,1);
        }
        else{
            cin>>p>>c;
            int max_d=0;
            bool mi=0;
            while(c--){
                int st,cnt;
                cin>>st>>cnt;
                int pw=(1<<14);
                int now=p,base=query(p-1,st);
                if(cnt==1)
                while(pw){
                    if(now+pw>n){
                        pw>>=1;
                        continue;
                    }
                    int nxt=now+pw;
                    int test=query(nxt,st);
                    test=test-base;
                    
                    if(test<cnt){
                        now=nxt;
                    }
                    else{
                        pw>>=1;
                    }
                }
                // cout<<now<<" ";
                if(now==n){
                    if(query(n,st)-base<cnt)mi=1;
                }
                else max_d=max(max_d,now+1);
            }
            if(mi){
                cout<<"-1\n";
            }
            else{
                cout<<max_d<<"\n";
            }
        }
    }
}