农夫乐事分块应用D
农夫乐事传送门，洛谷传送门
首先离线，离散化掉每张牌的得分，则只用对于每个得分记录它对应的数量，如果没有出现，视作
接下来维护方式比较多（比如线段树二分），因为这是分块应用，所以使用分块。
如果有得分大的没有取完是不会取得分比他少的，所以按得分从大到小排序，分块记录每块内的答案、总数量，每次只要从前往后扫每一块，如果可以这块全取，就加这块的答案，如果不行，则最后一个取的一定在这块里面，扫一遍即可。这样一次询问最劣是
当
// @author fkxr(luogu uid = 995934)
// https://hydro.ac/d/Fkxr/p/IO
// CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0/
#define luogu
#ifndef luogu
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#else
#include <bits/stdc++.h>
#endif
#ifndef db
#define db 0
#endif
#define endl cerr<<"------------------I Love the Olympiad in Informatics------------------\n";
#define int long long
#define _CRT_SECURE_NO_WARNINGS 1
#define _4x _4x
#define all(x) x.begin(),x.end()
//#define BIT BIT
//#define ST ST
//#define dsu dsu
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#define __int128 __int128_t
#endif
#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace fastIO {//吾常于「oi-wiki」习，自悟「快读快写」之术。
template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
struct FIstream {
inline FIstream operator>>(int& a) { r(a); return{}; }
inline FIstream operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
inline FIstream operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
template<typename T>inline FIstream operator<<(T& a) { r(a); return{}; }
inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
}in;
struct FOstream {
inline FOstream operator<<(const int a) { w(a); return{}; }
inline FOstream operator<<(const char ch) { pc(ch); return{}; }
inline FOstream operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
template<typename T>inline FOstream operator>>(const T a) { w(a); return{}; }
}out;
}using fastIO::in; using fastIO::out;
#undef ds
#define eout cerr
namespace Maths {//吾常赴「MO」之赛，自悟「数学」之术。
const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 };
inline bool IP1(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) * (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) * (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }
#define times(a,b,m) (c=(unsigned long long)a*b-(unsigned long long)((long double)a/m*b+0.5L)*m,c<m?c:m+c)
inline int power(int a, int b, const int mod = -1) { unsigned long long c; int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = times(ans, a, mod); b >>= 1; a = times(a, a, mod); }return ans; }
const int Suk[] = { 2,325,9375,28178,450775,9780504,1795265022 };
inline bool chk(const int n, int a, int b, int x) { if (x >= n) return 1; unsigned long long c; int v = power(x, a, n); if (v == 1)return 1; int j = 1; while (j <= b) { if (v == n - 1)break; v = times(v, v, n); j++; }if (j > b)return 0; return 1; }
inline bool IP(int n) { if (n < 3 || n % 2 == 0)return n == 2; if (n <= 1e6) { return IP1(n); } else { int a = n - 1, b = 0; while (a % 2 == 0)a >>= 1, b++; for (int k : Suk)if (!chk(n, a, b, k))return 0; return 1; } }
#undef times
} using Maths::power;
using Maths::IP;
namespace exs {
#ifdef _4x
int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
#else
int dx[] = { 1,0,-1,-1,1,1,0,-1 }, dy[] = { 1,1,1,0,0,-1,-1,-1 };
#endif
template<typename T, typename T1, typename T2>inline bool bt(T l, T2 x, T1 r) { return l <= x && x <= r; }
inline bool emc(const int& a, const int& b) { return a > b; }
#define popcti(val) ((int)__builtin_popcount(val))
#define popct(val) ((int)__builtin_popcountll(val))
#ifndef _MSC_VER
void Freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
#endif
#ifdef BIT//吾常读「《算法竞赛进阶指南》」之书，自悟「树状数组」之术。
struct bit {
vector<int> c0, c1; int n;
inline void Add(vector<int>& c, int p, int v) { for (; p <= n; p += p & -p) c[p] += v; }
inline int Sum(const vector<int>& c, int p) { int t = 0; for (; p; p -= p & -p) t += c[p]; return t; }
inline int sum(int l, int r) { assert(n != 0); return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
inline void add(int l, int r, int v) { assert(n != 0); Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
inline void init(const vector<int>& c) { n = c.size() - 1; c0.resize(n + 2); c1.resize(n + 2); int last = 0; for (int i = 1; i <= n; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
};
#endif
#ifdef ST//吾常读「《算法竞赛进阶指南》」之书，自悟「ST表」之术。
struct st {
vector<int> lg; vector<vector<int>> f;
inline void init(const vector<int>& c) { int len = c.size() - 1; lg.resize(len + 2); for (int i = 2; i <= len; i++) lg[i] = lg[i >> 1] + 1; f.resize(18, vector<int>(len + 2)); for (int i = 1; i <= len; i++) f[0][i] = c[i]; for (int j = 1; (1 << j) <= len; j++) for (int i = 1; i + (1 << j) - 1 <= len; i++) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]); }
inline int q(int l, int r) { int j = lg[r - l + 1]; return max(f[j][l], f[j][r - (1 << j) + 1]); }
};
#endif
#ifdef dsu//0x 吾常读「《算法竞赛进阶指南》」之书，自悟「并查集」之术。
struct dsu {
vector<int>fa;
dsu(int n):fa(n){iota(all(fa),0);}
inline int find(int x){return fa[x]==x?x:fa[x]=fa[fa[x]]=fa[fa[fa[x]]]=find(fa[fa[fa[x]]]);}
inline void unite(int x,int y){fa[find(x)]=find(y);}
//x->y
};
#endif
}using namespace exs;
vector<int>e;
struct node{
int opt,x,y;
}q[400005];
int a[400005],b[400005];
int id[400005];
int sum[400005],z[400005];
int cnt[400005];
void Main() {
int n;in>>n;e.push_back(0);
for(int i=1;i<=n;i++){
in>>a[i]>>b[i];
e.push_back(-a[i]);
}
int m;in>>m;
for(int i=1;i<=m;i++){
in>>q[i].opt>>q[i].x;
if(q[i].opt^3){
in>>q[i].y;
if(q[i].opt==1)e.push_back(-q[i].y);
}
}
sort(all(e));e.erase(unique(all(e)),e.end());
int len=sqrt(n);
for(int i=1;i<=e.size();i++)id[i]=i/len;
for(int i=1;i<=n;i++){
int t=lower_bound(all(e),-a[i])-e.begin()+1;
z[t]+=b[i],sum[id[t]]+=b[i]*a[i],cnt[id[t]]+=b[i];
}
for(int _=1;_<=m;_++){
int opt=q[_].opt,x=q[_].x,y=q[_].y;
if(opt==1){
int t=lower_bound(all(e),-a[x])-e.begin()+1;
z[t]-=b[x],sum[id[t]]-=b[x]*a[x],cnt[id[t]]-=b[x];
a[x]=y;
t=lower_bound(all(e),-a[x])-e.begin()+1;
z[t]+=b[x],sum[id[t]]+=b[x]*a[x],cnt[id[t]]+=b[x];
}else if(opt==2){
int t=lower_bound(all(e),-a[x])-e.begin()+1;
z[t]+=y-b[x],sum[id[t]]+=(y-b[x])*a[x],cnt[id[t]]+=y-b[x];
b[x]=y;
}else{
int ans=0;y=x;
for(int i=0;i<=id[e.size()];i++){
if(y==0)break;
//out<<y<<" "<<ans<<" "<<i<<"\n";
if(y>=cnt[i])y-=cnt[i],ans+=sum[i];
else
for(int j=max(i*len,(int)1);id[j]==i;j++)
if(y>z[j])ans-=z[j]*e[j-1],y-=z[j];
else{
ans-=y*e[j-1],y=0;
break;
}
}
if(y)out<<"-1\n";
else out<<ans<<"\n";
}
}
}
signed main() {
Main();
return 0;
}::::
AT 提交记录，农夫乐事提交记录