POI #Year2011 #整体二分
整体二分板子,用树状数组维护即可
// Author: xiaruize
const int N = 1e6 + 10;
int n, m, t;
vector<int> vec[N];
struct node
{
int l, r, x;
} s[N];
pii a[N];
struct BIT
{
int tr[N];
void add(int x, int v)
{
while (x <= m * 2)
{
tr[x] += v;
x += x & -x;
}
}
int sum(int x)
{
int res = 0;
while (x)
{
res += tr[x];
x -= x & -x;
}
return res;
}
} tr;
int res[N];
void solve(int l, int r, int x, int y)
{
if (x > y)
return;
if (l == r)
{
debug(l, r, x, y);
rep(i, x, y)
{
res[a[i].second] = l;
debug(a[i].second);
}
return;
}
int mid = l + r >> 1;
rep(i, l, mid)
{
tr.add(s[i].l, s[i].x);
tr.add(s[i].r + 1, -s[i].x);
}
vector<pii> lv, rv;
rep(i, x, y)
{
int tmp = 0;
for (auto v : vec[a[i].second])
{
tmp += tr.sum(v) + tr.sum(v + m);
if (tmp >= a[i].first)
break;
}
debug(l, r, a[i].second, tmp);
if (tmp >= a[i].first)
lv.push_back(a[i]);
else
{
a[i].first -= tmp;
rv.push_back(a[i]);
}
}
rep(i, l, mid)
{
tr.add(s[i].l, -s[i].x);
tr.add(s[i].r + 1, s[i].x);
}
int tot = x;
for (auto v : lv)
a[tot++] = v;
for (auto v : rv)
a[tot++] = v;
debug(lv, rv);
solve(l, mid, x, x + lv.size() - 1);
solve(mid + 1, r, x + lv.size(), y);
}
void solve()
{
mms(res, -1);
cin >> n >> m;
rep(i, 1, m)
{
int x;
cin >> x;
vec[x].push_back(i);
}
rep(i, 1, n)
{
cin >> a[i].first;
a[i].second = i;
}
cin >> t;
rep(i, 1, t)
{
cin >> s[i].l >> s[i].r >> s[i].x;
if (s[i].r < s[i].l)
s[i].r += m;
}
s[++t] = {1, 2 * m, INF};
solve(1, t, 1, n);
rep(i, 1, n)
{
// debug(res[i]);
if (res[i] > t - 1 || res[i] == -1)
cout << "NIE\n";
else
cout << res[i] << '\n';
}
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:tmp,POI2011MET,int,rep,tr,lv,second,Meteors
From: https://www.cnblogs.com/xiaruize/p/18147874