语言系统紊乱了 QAQ
这道题感觉不是很难鸭 qwq。
先只考虑一个国家,怎么做?很显然,就直接二分一下就行了。判定答案可以维护一个差分数组,然后最后对它做一个前缀和,再求一下这个国家的流行数量就好了 qwq。
二分是 \(O(\log_k)\) 的,差分最坏要做 \(O(k)\) 的,前缀和是 \(O(m)\) 的,所以总共时间复杂度是 \(O((k + m)\log_2 k)\)。
诶?\(m\) 为什么会出现在这个复杂度里?许昊然巨佬在他的论文里写到了,我们的这个复杂度每次只能和待处理的操作长度有关,而不能和总序列长度有关。
这怎么办?我们不能用 \(O(m)\) 直接做一遍前缀和,那我们就用一个树状数组维护这个前缀和。
套上整体二分的板子就没了趴
#include <iostream>
#include <vector>
#define MAXN 500000
#define QWQ cout << "qwq" << endl;
using namespace std;
int n, m, k;
vector <int> vec[MAXN + 10];
int Q[MAXN + 10], ta[MAXN + 10], tb[MAXN + 10], ans[MAXN + 10];
int L[MAXN + 10], R[MAXN + 10], val[MAXN + 10];
int tr[MAXN + 10], aim[MAXN + 10];
int lowbit(int x){return x & (-x);}
void add(int pos, int val) {
for(; pos <= m; pos += lowbit(pos))
tr[pos] += val;
}
int query(int pos) {
int rest = 0;
while(pos) {
rest += tr[pos];
pos -= lowbit(pos);
}
return rest;
}
void solve(int l, int r, int s, int t) {
if(s == t) {
for(int p = l; p <= r; p++)
ans[Q[p]] = s;
return ;
}
int mid = (s + t) >> 1;
for(int p = s; p <= mid; p++)
if(L[p] <= R[p])
add(L[p], val[p]), add(R[p] + 1, -val[p]);
else {
add(L[p], val[p]), add(m + 1, -val[p]);
add(1, val[p]), add(R[p] + 1, -val[p]);
}
int t1 = 0, t2 = 0;
for(int p = l; p <= r; p++) {
int tal = 0;
for(int i = 0; i < vec[Q[p]].size(); i++) {
tal += query(vec[Q[p]][i]);
if(tal >= aim[Q[p]]) break;
}
if(tal >= aim[Q[p]]) ta[++t1] = Q[p];
else aim[Q[p]] -= tal, tb[++t2] = Q[p];
}
for(int p = s; p <= mid; p++)
if(L[p] <= R[p])
add(L[p], -val[p]), add(R[p] + 1, val[p]);
else {
add(L[p], -val[p]), add(m + 1, val[p]);
add(1, -val[p]), add(R[p] + 1, val[p]);
}
for(int p = l, i = 1; i <= t1; p++, i++) Q[p] = ta[i];
for(int p = l + t1, i = 1; i <= t2; p++, i++) Q[p] = tb[i];
solve(l, l + t1 - 1, s, mid);
solve(l + t1, r, mid + 1, t);
}
int main() {
cin >> n >> m;
for(int p = 1, x; p <= m; p++) {
cin >> x;
vec[x].push_back(p);
}
for(int p = 1; p <= n; p++)
cin >> aim[p], Q[p] = p;
cin >> k;
int tot = 0;
for(int p = 1; p <= k; p++) {
int a, b, c;
cin >> L[p] >> R[p] >> val[p];
}
solve(1, n, 1, k + 1);
for(int p = 1; p <= n; p++) {
if(ans[p] == k + 1) cout << "NIE" << endl;
else cout << ans[p] << endl;
}
}