*题解：P3586 [POI 2015 R2] 物流 Logistics

原题链接

解析

考虑能每次选 \(c\) 个正数进行 \(s\) 次 \(-1\) 操作的充要条件是什么。首先由于只进行 \(s\) 次操作，可以将 \(> s\) 的数视为 \(s\)。然后求和，如果和 \(< c \cdot s\)，那么必定无法操作，反之是否必定可以操作呢？我们尝试将这 \(n\) 个数合并成 \(c\) 个，如果都能合并出 \(s\) 就说明可以，一个朴素的想法是将每个数分解成其数值个元素，直接一个一个堆起来，就像这样：

c = 3,s = 5
5 4 2
5 4 2
3 5 1
3 5 4
3 5 4

由于我们已经将 \(> s\) 数视为 \(s\)，所以不可能出现同一层中的两个元素属于同一个数的情况。

于是问题就变为如何求 \(\le s\) 部分的和。考虑开两个权值树状数组，一个存数值和，一个存出现次数，要求的其实就是 \(sum + cnt \cdot s\)，其中 \(sum\) 是 \(\le s\) 的数的和，\(cnt\) 是 \(> s\) 的数的个数。

时间复杂度 \(O(m\log n)\)。

代码

#include <bits/stdc++.h>
#define ls(p) ((p) << 1)
#define rs(p) (((p) << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6 + 5,M = 5e5,mod = 998244353;
int a[N];
ll cnt[N];
ll sum[N];
struct Query{char op;int x,y;
}q[N];
void add(ll b[],int x,int k){for(;x < N;x += x & -x){b[x] += k;}
}
ll ask(ll b[],int x){ll res = 0;for(;x;x -= x & -x){res += b[x];}return res;
}
int read(){int a = 1,x = 0;char ch = getchar();while(ch > '9' || ch < '0'){if(ch == '-') a = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return a * x;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);vector<int> v;v.push_back(0);int n,m;n = read(),m = read();for(int i=1;i<=m;i++){q[i].op = getchar();q[i].x = read();q[i].y = read();v.push_back(q[i].y);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++){add(cnt,1,1);}for(int i=1;i<=m;i++){if(q[i].op == 'U'){int p = lower_bound(v.begin(),v.end(),a[q[i].x]) - v.begin() + 1;add(sum,p,-a[q[i].x]);add(cnt,p,-1);a[q[i].x] = q[i].y;p = lower_bound(v.begin(),v.end(),a[q[i].x]) - v.begin() + 1;add(sum,p,a[q[i].x]);add(cnt,p,1);}else{int p = lower_bound(v.begin(),v.end(),q[i].y) - v.begin() + 1;ll x = ask(sum,p) + (n - ask(cnt,p)) * q[i].y;if(x >= 1ll * q[i].x * q[i].y){cout<<"TAK\n";}else{cout<<"NIE\n";}}}return 0;
}