【整体二分】AcWing268
传送门
其实整体二分就是在二分答案的同时把询问也二分了。排除询问不可能的值域。
树状数组可以区间更新单点查询,不要傻傻地去写区间更新区间查询的树桩上数组。。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
int o[maxn], b[maxn], lb[maxn], rb[maxn];
vector<int> pos[maxn];
ll p[maxn];
int ans[maxn];
int n, m, k;
struct rec{
int l, r; ll v;
}a[maxn];
ll c[2][maxn];
void add(int t, int x, ll v)
{
for(; x <= m; x += x & -x) c[t][x] += v;
}
ll ask(int t, int x)
{
ll res = 0;
for(; x; x -= x & -x) res += c[t][x];
return res;
}
void update(int l, int r, ll v)
{
// cout << l << "+" << r << endl;
if(l <= r)
{
add(0, l, v);
add(0, r + 1, -v);
//add(1, l, l * v);
//add(1, r + 1, -(r + 1) * v);
}
else
{
int ll = r, rr = l;
l = 1, r = ll;
add(0, l, v);
add(0, r + 1, -v);
//add(1, l, l * v);
//add(1, r + 1, -(r + 1) * v);
l = rr, r = m;
add(0, l, v);
add(0, r + 1, -v);
//add(1, l, l * v);
//add(1, r + 1, -(r + 1) * v);
}
}
ll query(int l, int r)
{
// cout << l << ' ' << r << endl;
if(l <= r)
{
ll res = (ll)(r + 1) * ask(0, r) - ask(1, r);
res -= (ll)l * ask(0, l - 1) - ask(1, l - 1);
return res;
}
else
{
ll res = 0;
ll ll = r, rr = l;
l = 1, r = ll;
res += (r + 1) * ask(0, r) - ask(1, r);
res -= l * ask(0, l - 1) - ask(1, l - 1);
l = rr, r = m;
res += (r + 1) * ask(0, r) - ask(1, r);
res -= l * ask(0, l - 1) - ask(1, l - 1);
return res;
}
}
ll now[maxn];
void solve(int lv, int rv, int st, int ed)
{
if(st > ed) return;
if(lv == rv)
{
for(int i = st; i <= ed; i++) ans[b[i]] = lv;
return;
}
int mid = (lv + rv) >> 1;
int lt = 0, rt = 0;
for(int i = lv; i <= mid; i++) update(a[i].l, a[i].r, a[i].v);
//cout << query(1, 5) << "?" << endl;
for(int i = st; i <= ed; i++)
{
ll cnt = 0;
for(int j = 0; j < pos[b[i]].size(); j++)
{
//cnt += query(pos[b[i]][j], pos[b[i]][j]);
cnt += ask(0, pos[b[i]][j]);
if(cnt >= p[b[i]]) break;
}
now[b[i]] = cnt;
}
for(int i = st; i <= ed; i++)
{
if(now[b[i]] >= p[b[i]]) lb[++lt] = b[i];
else p[b[i]] -= now[b[i]], rb[++rt] = b[i];
}
for(int i = lv; i <= mid; i++) update(a[i].l, a[i].r, -a[i].v);
for(int i = 1; i <= lt; i++) b[i + st - 1] = lb[i];
for(int i = 1; i <= rt; i++) b[i + lt + st - 1] = rb[i];
solve(lv, mid, st, st + lt - 1);
solve(mid + 1, rv, st + lt, ed);
}
int main()
{
memset(ans, -1, sizeof ans);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) scanf("%d", &o[i]), pos[o[i]].push_back(i);
for(int i = 1; i <= n; i++) scanf("%lld", &p[i]), b[i] = i;
scanf("%d", &k);
for(int i = 1; i <= k; i++) scanf("%d%d%lld", &a[i].l, &a[i].r, &a[i].v);
a[++k] = {1, m, 0};
solve(1, k, 1, n);
for(int i = 1; i <= n; i++)
if(ans[i] != k) printf("%d\n", ans[i]);
else printf("NIE\n");
}
发表评论