Ý tưởng chính của bài toán này là thay vì ta tăng giá trị của các ô có màu khác ~col~, ta sẽ tăng giá trị cho tất cả ô một lượng ~x~ rồi giảm các ô có màu ~col~ một lượng ~x~.

Gọi ~sum~ là tổng giá trị được tăng cho tất cả ô khi xét đến thời điểm hiện tại. ~f_i~ là tổng giá trị cần phải giảm của các ô có màu ~i~.

• Với mỗi truy vấn thuộc loại 1, tăng ~sum~, ~f_{col}~ lên một lượng ~x~.

• Với mỗi truy vấn thuộc loại 2, gọi ~p_i~ là tổng giá trị của ~i~ ô đầu tiên có màu ~col~, như vậy, với mỗi số nguyên ~l~, ta có tổng của ~l~ ô đầu tiên có màu ~col~ là ~p_l+l \cdot (sum-f_{col})~, ta có thể tìm kiếm nhị phân từng độ dài ~l~ để tìm đáp án. Độ phức tạp: ~O(q \cdot log_2n)~.

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<ll> col[100001];
vector<ll> pref[100001];
ll diff[100001];
ll n,add,q;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    for(int i=1;i<=1e5;i++) col[i].push_back(0);
    for(int i=1;i<=n;i++){
        ll a,c;
        cin>>a>>c;
        col[c].push_back(a);
    }
    for(int i=1;i<=1e5;i++){
        pref[i].resize(col[i].size(),0);
        for(int j=1;j<col[i].size();j++){
            pref[i][j]=pref[i][j-1]+col[i][j];
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll t,color,x;
        cin>>t>>color>>x;
        if(t==1){
            add+=x;
            diff[color]+=x;
        }
        else{
            ll lo=1,hi=col[color].size()-1,ans=0;
            while(lo<=hi){
                ll mid=(lo+hi)/2;
                if(pref[color][mid]+mid*(add-diff[color])<=x){
                    ans=mid;
                    lo=mid+1;
                }
                else{
                    hi=mid-1;
                }
            }
            cout<<ans<<ntr;
        }
    }
}