NOIP解题报告|NOIP模拟（11.07）T3 小店购物
小店购物
【NOIP解题报告|NOIP模拟（11.07）T3 小店购物】题目背景：
11.07 NOIP模拟T3
分析：线段树 + multiset
这道题让我发现了自己的智障······set是会去重的，然后我塞了一模一样的东西进去然后删了很多次，还没有判end，然后就开心的去删掉了end，然后T成傻逼······最后改成了multiset，考虑对于同种价值，有用的就只有价格最小的那一个，但是中间存在插删操作，那么我们直接对于每一种价值维护一个multiset就可以了，然后插入删除查询最小都变得异常简单，然后对于每一种价值的最小值我们再来建立一颗线段树，然后每一次询问就是找线段树上最右边（价值最大）第一个价格小于等于当前询问的k值的位置，这个就是说过很多次的线段树上二分，然后取出当前的价格然后统计可以得到的价值，然后k %= price，可以知道k最多被有效得mod logk次，那么直接暴力每次找一遍就好了，然后修改操作的时候改变了set内部的值，也要更新一下线段树上的最小值，那么现在修改操作就是一个常数略大的log n，查询操作就是常数较小的logn * logk，复杂度O(nlogn * logk)，然而看了标算发现set是不必要的，直接把二元组排序就可以了，价值为第一关键字，价值越大位置越靠前，然后价值相同价格越小位置越靠前。但是不管有没有multiset，都需要离散化一次，并且离散化必须将询问里面的值一起离散化才行，如果有multiset，那么直接离散化w就可以了，如果没有的话，要直接离散化二元组，相当于一个排名的过程。
Source:
/*
created by scarlyw
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include inline char read() {
static const int IN_LEN = 1024 * 1024;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}template
inline void R(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false;
!isdigit(c);
c = read()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0;
isdigit(c);
c = read())
x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}template
inline void W(T x) {
static int buf[30], cnt;
if (x == 0) write_char('0');
else {
if (x < 0) write_char('-'), x = -x;
for (cnt = 0;
x;
x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) write_char(buf[cnt--]);
}
}inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}const int MAXN = 150000 + 10;
const int INF = 2000000000;
int n, m, cnt, top;
int w[MAXN], p[MAXN], rk[MAXN << 1];
std::multisetprice[MAXN << 1];
std::multiset::iterator it;
struct query {
int x, w, p, k, type;
} q[MAXN];
struct data {
int num, ori, type;
data() {}
data(int num, int ori, int type) : num(num), ori(ori), type(type) {}
inline bool operator < (const data &a) const {
return num < a.num;
}
} a[MAXN << 1];
inline void read_in() {
R(n), R(m);
for (int i = 1;
i <= n;
++i) R(w[i]), R(p[i]), a[++cnt] = data(w[i], i, 0);
for (int i = 1;
i <= m;
++i) {
R(q[i].type);
if (q[i].type == 1) {
R(q[i].x), R(q[i].w), R(q[i].p), a[++cnt] = data(q[i].w, i, 1);
} else R(q[i].k);
}
}inline void apart() {
std::sort(a + 1, a + cnt + 1);
int i = 1;
while (i <= cnt) {
int j = i;
while (a[i].num == a[i + 1].num) {
if (i == cnt) break ;
++i;
}
++top, rk[top] = a[i].num;
for (int k = j;
k <= i;
++k)
a[k].type ? q[a[k].ori].w = top : w[a[k].ori] = top;
++i;
}
for (int i = 1;
i <= n;
++i) price[w[i]].insert(p[i]);
}int tree[MAXN << 3];
inline void update(int k) {
tree[k] = std::min(tree[k << 1], tree[k << 1 | 1]);
}inline void build(int k, int l, int r) {
if (l == r) {
tree[k] = (price[l].size() ? (*price[l].begin()) : INF);
return ;
}
int mid = l + r >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
update(k);
}inline void modify(int k, int l, int r, int pos) {
if (l == r) {
tree[k] = (price[pos].size() ? (*price[pos].begin()) : INF);
return ;
}
int mid = l + r >> 1;
if (pos <= mid) modify(k << 1, l, mid, pos);
else modify(k << 1 | 1, mid + 1, r, pos);
update(k);
}struct node {
int w, p;
node(int w = 0, int p = 0) : w(w), p(p) {}
} ;
inline node query(int k, int l, int r, int x) {
if (l == r) return node(l, tree[k]);
int mid = l + r >> 1;
if (tree[k << 1 | 1] <= x) return query(k << 1 | 1, mid + 1, r, x);
else return query(k << 1, l, mid, x);
}inline void solve() {
build(1, 1, top);
for (int i = 1;
i <= m;
++i) {
if (q[i].type == 1) {
int pos = q[i].x, x = q[i].w, y = q[i].p;
it = price[w[pos]].lower_bound(p[pos]);
price[w[pos]].erase(it);
modify(1, 1, top, w[pos]);
w[pos] = x, p[pos] = y, price[w[pos]].insert(p[pos]);
modify(1, 1, top, w[pos]);
} else {
int x = q[i].k;
long long ans = 0;
while (x != 0) {
if (tree[1] > x) break ;
node temp = query(1, 1, top, x);
ans += (long long)rk[temp.w] * (x / temp.p), x %= temp.p;
}
W(ans), write_char('\n');
}
}
}int main() {
// freopen("shopping.in", "r", stdin);
// freopen("shopping.out", "w", stdout);
read_in();
apart();
solve();
flush();
return 0;
} 推荐阅读
- Filecoin挖矿投资报告
- c#常用网址记录
- 【李海峰DISC人际关系训练营学习报告】紫檀东莞班毕业典礼
- 坚守与追求
- 叮咚～您有一份GitHub2020年度报告待查收
- PPT学习第二天之年度总结报告的设计思路
- 【JS 逆向百例】吾爱破解2022春节解题领红包之番外篇 Web 中级题解
- 网红端到端测试神器Cypress开箱试用报告
- 关于“张”姓的历史和现状研究报告
- 2018年读书、观影总结报告