看到巨佬们在群里膜 CDQ，于是来学习 CDQ 分治…
要避免树状数组重复初始化，每次操作完之后要将树状数组恢复。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9;
struct Fenwick
{
struct BaseFenwick
{
vector<ll> v;
BaseFenwick(int n) : v(n) {}
void add(int x, ll w)
{
for (; x < v.size(); x += x & -x)
v[x] += w;
}
ll ask(int x)
{
ll ans = 0;
for (; x; x -= x & -x)
ans += v[x];
return ans;
}
};
pair<BaseFenwick, BaseFenwick> p;
Fenwick(int n) : p(n, n) {}
void add(int x, ll w) { p.first.add(x, w), p.second.add(x, x * w); }
void add(int l, int r, ll w) { add(l, w), add(r + 1, -w); }
ll ask(int x) { return (x + 1) * p.first.ask(x) - p.second.ask(x); }
ll ask(int l, int r) { return ask(r) - ask(l - 1); }
} t(N);
struct Query
{
int o, a, b, ans;
ll c;
} q[N];
void ask(int l, int r, const vector<int> &id)
{
if (l == r)
{
for (int i = 0; i < id.size(); ++i)
if (q[id[i]].o != 1)
q[id[i]].ans = l;
return;
}
ll m = l + r >> 1;
vector<int> t1, t2;
for (int i = 0; i < id.size(); ++i)
{
if (q[id[i]].o == 1)
{
if (q[id[i]].c <= m)
t1.push_back(id[i]);
else
t2.push_back(id[i]), t.add(q[id[i]].a, q[id[i]].b, 1);
}
else
{
ll sum = t.ask(q[id[i]].a, q[id[i]].b);
if (q[id[i]].c > sum)
t1.push_back(id[i]), q[id[i]].c -= sum;
else
t2.push_back(id[i]);
}
}
for (int i = 0; i < t2.size(); ++i)
if (q[t2[i]].o == 1)
t.add(q[t2[i]].a, q[t2[i]].b, -1);
ask(l, m, t1), ask(m + 1, r, t2);
}
int main()
{
int n, m;
vector<int> id;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
id.push_back(i);
scanf("%d%d%d%lld", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
}
ask(1, n, id);
for (int i = 0; i < m; ++i)
if (q[i].o != 1)
printf("%d\n", q[i].ans);
}
动态开点线段树自然也是行的，不过慢了六七倍（2400ms:15744ms）…
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9, NPOS = -1;
struct SegmentTree
{
struct Val
{
int l, r;
ll sum;
void upd(ll add) { sum += add * (r - l + 1); }
};
struct Node
{
Val v;
int lc, rc;
ll add;
};
vector<Node> v;
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r) { v.push_back({{l, r, 0}, NPOS, NPOS, 0}); }
Val up(const Val &lc, const Val &rc) { return {lc.l, rc.r, lc.sum + rc.sum}; }
void down(int rt)
{
int m = v[rt].v.l + v[rt].v.r >> 1;
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].v.l, m);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].v.r);
upd(v[v[rt].lc].v.l, v[v[rt].lc].v.r, v[rt].add, v[rt].lc);
upd(v[v[rt].rc].v.l, v[v[rt].rc].v.r, v[rt].add, v[rt].rc);
v[rt].add = 0;
}
void upd(int l, int r, ll add, int rt = 0)
{
if (l <= v[rt].v.l && v[rt].v.r <= r)
return v[rt].add += add, v[rt].v.upd(add);
down(rt);
if (r <= v[v[rt].lc].v.r)
upd(l, r, add, v[rt].lc);
else if (l >= v[v[rt].rc].v.l)
upd(l, r, add, v[rt].rc);
else
upd(l, v[v[rt].lc].v.r, add, v[rt].lc), upd(v[v[rt].rc].v.l, r, add, v[rt].rc);
v[rt].v = up(v[v[rt].lc].v, v[v[rt].rc].v);
}
Val ask(int l, int r, int rt = 0)
{
if (l <= v[rt].v.l && v[rt].v.r <= r)
return v[rt].v;
down(rt);
if (r <= v[v[rt].lc].v.r)
return ask(l, r, v[rt].lc);
if (l >= v[v[rt].rc].v.l)
return ask(l, r, v[rt].rc);
return up(ask(l, v[v[rt].lc].v.r, v[rt].lc), ask(v[v[rt].rc].v.l, r, v[rt].rc));
}
};
struct Query
{
int o, a, b, ans;
ll c;
} q[N];
int n, m;
void ask(int l, int r, const vector<int> &id)
{
if (l == r)
{
for (int i = 0; i < id.size(); ++i)
if (q[id[i]].o != 1)
q[id[i]].ans = l;
return;
}
ll m = l + r >> 1;
SegmentTree t(1, n);
vector<int> t1, t2;
for (int i = 0; i < id.size(); ++i)
{
if (q[id[i]].o == 1)
{
if (q[id[i]].c <= m)
t1.push_back(id[i]);
else
t2.push_back(id[i]), t.upd(q[id[i]].a, q[id[i]].b, 1);
}
else
{
ll sum = t.ask(q[id[i]].a, q[id[i]].b).sum;
if (q[id[i]].c > sum)
t1.push_back(id[i]), q[id[i]].c -= sum;
else
t2.push_back(id[i]);
}
}
ask(l, m, t1), ask(m + 1, r, t2);
}
int main()
{
vector<int> id;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
id.push_back(i);
scanf("%d%d%d%lld", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
}
ask(1, n, id);
for (int i = 0; i < m; ++i)
if (q[i].o != 1)
printf("%d\n", q[i].ans);
}
在线的做法是树套树。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9, M = 2e7 + 9;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
struct Query
{
int o, a, b, c;
} q[N];
struct Node
{
int lc, rc, add;
ll sum;
} t[M];
int n, m, tot, root[N << 2];
void upd(int u, int v, int &rt, int l, int r, ll add);
void down(int rt, int l, int r)
{
if (!t[rt].add)
return;
int m = l + r >> 1;
upd(l, m, t[rt].lc, l, m, t[rt].add);
upd(m + 1, r, t[rt].rc, m + 1, r, t[rt].add);
t[rt].add = 0;
}
void upd(int u, int v, int &rt, int l, int r, ll add)
{
if (!rt)
rt = ++tot;
if (u == l && v == r)
{
t[rt].add += add, t[rt].sum += (r - l + 1) * add;
return;
}
down(rt, l, r);
int m = l + r >> 1;
if (v <= m)
upd(u, v, t[rt].lc, l, m, add);
else if (u > m)
upd(u, v, t[rt].rc, m + 1, r, add);
else
upd(u, m, t[rt].lc, l, m, add), upd(m + 1, v, t[rt].rc, m + 1, r, add);
t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;
}
ll ask(int u, int v, int rt, int l, int r)
{
if (!rt)
return 0;
if (u == l && v == r)
return t[rt].sum;
down(rt, l, r);
int m = l + r >> 1;
if (v <= m)
return ask(u, v, t[rt].lc, l, m);
if (u > m)
return ask(u, v, t[rt].rc, m + 1, r);
return ask(u, m, t[rt].lc, l, m) + ask(m + 1, v, t[rt].rc, m + 1, r);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d%d", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
if (q[i].o == 1)
rk.push_back(q[i].c);
}
rk.init();
for (int i = 0; i < m; ++i)
{
if (q[i].o == 1)
for (int c = rk.size() - rk.ask(q[i].c), k = 1, l = 1, r = rk.size();;)
{
int m = l + r >> 1;
upd(q[i].a, q[i].b, root[k], 1, n, 1);
if (l == r)
break;
if (c <= m)
r = m, k <<= 1;
else
l = m + 1, k = k << 1 | 1;
}
else
{
int k = 1, l = 1, r = rk.size();
while (l < r)
{
ll m = l + r >> 1, sum = ask(q[i].a, q[i].b, root[k << 1], 1, n);
if (sum >= q[i].c)
r = m, k <<= 1;
else
l = m + 1,
k = k << 1 | 1, q[i].c -= sum;
}
printf("%d\n", rk[rk.size() - l]);
}
}
}