Yuuki and a problem

先不管第一問(wèn)的修改操作，考慮如何達(dá)到第二問(wèn)的查詢操作，

題目要我們給出一個(gè)區(qū)間$[l,r]$中，不能通過(guò)權(quán)值$+$得到的最小的數(shù)字是什么，

假設(shè)我們已經(jīng)可以得到$[1,x]$之間的數(shù)了，且，我們?cè)儐?wèn)權(quán)值在$[1,x+1]$之間的和為$sum$，那么$[1,sum]$之間的數(shù)一定能通過(guò)$+$法得到，

我們分類(lèi)討論一下:

• $sum=su{m}_x$，顯然我們無(wú)法合成$x+1$了。
• $sum\ge su{m}_x$，為什么$[x+1,sum]$之間的數(shù)一定可以合成呢？$sum=su{m}_x+k(x+1)$，我們假定$k=1$，由于有前提條件$[1,x]$之間的數(shù)是可以合成的，在$x+1$的基礎(chǔ)上我們可以得到$[x+1,x+1+su{m}_x]$之間的數(shù)字。

以此每次遞增查詢，最多就是一個(gè)斐波那契數(shù)列的形式，所以最多查詢不到$30$次。

再考慮第一問(wèn)的修改操作，修改操作，跟區(qū)間查詢操作連到一起容易想到帶修主席樹(shù)（樹(shù)狀數(shù)組套主席樹(shù)），

整體復(fù)雜度$30\times m\log n\log n$。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 2e5 + 10, maxn = 200000;int a[N], n, m;int root[N], ls[N << 7], rs[N << 7], num;ll sum[N << 7];int A[N], B[N], cnt1, cnt2;inline int lowbit(int x) {return x & (-x); }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++num;}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }ll query(int l, int r, int L, int R) {if (l >= L && r <= R) {ll ans = 0;for (int i = 1; i <= cnt1; i++) {ans -= sum[A[i]];}for (int i = 1; i <= cnt2; i++) {ans += sum[B[i]];}return ans;}int mid = l + r >> 1;ll ans = 0;if (L <= mid) {int A1[30], B1[30];for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = ls[B[i]];}ans += query(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}if (R > mid) {int A1[30], B1[30];for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = rs[B[i]];}ans += query(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);for (int j = i; j <= n; j += lowbit(j)) {update(root[j], 1, maxn, a[i], a[i]);}}for (int i = 1; i <= m; i++) {int op, x, y;scanf("%d %d %d", &op, &x, &y);if (op & 1) {for (int j = x; j <= n; j += lowbit(j)) {update(root[j], 1, maxn, a[x], -a[x]);}a[x] = y;for (int j = x; j <= n; j += lowbit(j)) {update(root[j], 1, maxn, a[x], a[x]);}}else {cnt1 = cnt2 = 0;for (int j = x - 1; j; j -= lowbit(j)) {A[++cnt1] = root[j];}for (int j = y; j; j -= lowbit(j)) {B[++cnt2] = root[j];}ll cur = 0, sum = 0;do {cur = sum + 1;sum = query(1, maxn, 1, min(cur, 1ll * maxn));}while (sum >= cur);printf("%lld\n", sum + 1);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的ICPC 徐州 H Yuuki and a problem (树状数组套主席树)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。