250130 以前 x 天
可以先用 bfs 求出能放置的点，那么判合法只需要把这些点全都放上然后看看是不是所有点都被覆盖了。记 \(d[u]\) 表示离 \(u\) 最近的能放置的点到 \(u\) 的距离，那么只需对待覆盖的点判断 \(d[u]\le lim\) 即可。
然后考虑树上贪心，问题在于有些点是不能放置的，这导致经典的树上贪心不能直接套用。考虑到我们只关心子树内深度最深的没有被覆盖的点，和深度最浅的可以放置的点；否则，如果后者和子树外的点都不能覆盖前者，那么前者应该在更深的子树内被处理。
这样，对于节点 \(u\)，设子树内最深的没被覆盖的节点的深度为 \(g[u][0]\)，如果 \(g[u][0]+d[fa[u]]+1>lim\) 就立刻把 \(d[u]\) 填上（因为无论如何都要填），否则一定可以拖到父亲处再处理。
首先正难则反，总共方案数可以用二项式定理简单计算。对于不能形成三角形的方案，容易设计一个 \(O(n^2)\) 的 dp 来处理方案数。问题是如何处理长度的贡献，只需在 dp 中同时记录方案数和子序列长度之和即可。
如果只有 \(b_i\in [0,a_i]\) 和 \(\bigoplus b_i=C\) 的限制，那么就是P3447 [POI 2006] KRY-Crystals。然后对图的限制进行容斥，钦定一些边相等，这样图会被相等关系划分为若干连通块。如果连通块的大小是奇数，那么其权值取决于 \(a_i\) 最小的一个点；如果是偶数，则直接产生 \(\min a_i\) 的贡献，权值为 \(0\)。
至于一个连通块的容斥系数之和，显然可以根据 exp 的组合意义用集合幂级数 ln 求出，但显然我们不会。于是对连通性简单容斥 \(O(3^n)\) 也是对的。
还有一个问题，\(n=15\) 的贝尔数非常爆炸。但注意到本质不同的权值序列其实不超过 \(2^n\) 种，因此考虑对每种权值序列求出贡献和。考虑将点按照 \(a_i\) 从小到大排序，然后依次考虑，这样做的好处就是 \(a_i\) 最小值总是在第一个位置。我们需要记录已经考虑的点中，哪些点是关键点；以及未被考虑的点中，哪些点被占用了。看起来状态数是 \(O(4^n)\) 的，但由于两部分总共只有 \(n\) 个点，因此是 \(O(2^n)\) 的。时间复杂度 \(O(3^n+n2^n+n2^n\log V)\)。
注意到多次换乘时 \(b_i\) 一定严格单调递减，因此转移不存在环，可以扫描线然后用点分树加凸包或李超树处理距离的贡献。
警报器
一个警报器会监视数组上的若干位置，如果这些位置的某种累计次数之和达到了某个阈值就产生报警。
通过抽屉原理可以将多个位置的总和用一只 \(\log\) 的代价拆成一些独立的小问题。具体的，如果有 \(k\) 个位置，总阈值为 \(v\)，那么为每个位置设置阈值 \(\lceil\frac{v}{k}\rceil\)，显然每次产生小报警都会导致 \(v\) 缩小到 \(\frac{k-1}{k}v\)，这样总次数就是 \(O(\log_{k/(k-1)}V)\) 了。
注意到 \(\omega(n)\le 6\)，可以暴力。我们对每个警报器涵盖的 \(k\le 6\) 个位置设置阈值 \(\lceil\frac{y}{k}\rceil\)，显然至少有一个位置突破阈值才有可能报警。给每个节点开一个堆维护所有阈值，每次达到阈值就 \(O(k)\) 重构（需要可删堆？），显然重构次数不超过 \(O(\log_{5/6}V)\)，每次重构是 \(O(k\log n)\) 的，因此总复杂度 \(O(nk\log n\log_{5/6}V)\)。
这里介绍一种更快的方法。我们可以对每组节点设置一个值 \(h\)，如果其中一个节点的次数经过了某个 \(2^h\) 的整数倍，就产生一次报警；如果在下一次报警之前总次数仍然不可能达到阈值，就不更新 \(h\)，这样处理单次报警的复杂度就被优化到 \(O(1)\)。注意到一个 \(h\) 最多只会报警 \(k\) 次，并且可以直接用线性表维护，所以不用带 \(\log\)。这样时间复杂度是 \(O(nk\log_2V)\)。
代码
| #include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int W = 6;
const int LOGV = 49;
int n, m, nq;
ll cnt[N], tar[N], cur[N]; int bg[N], p[N];
int hd[N][LOGV], nxt[N * W], pre[N * W], val[N * W], nn;
vector<int> buf;
vector<int> fac[N];
bool npri[N]; int pri[N], pcnt;
void erase(int id, int k) {
int x = p[id];
for(int i = bg[id]; i < bg[id] + fac[x].size(); i++) {
if(nxt[i]) pre[nxt[i]] = pre[i];
if(pre[i]) nxt[pre[i]] = nxt[i];
else hd[fac[x][i - bg[id]]][k] = nxt[i];
}
}
void insert(int id, int k) {
int x = p[id]; cur[id] = 0;
for(int i = bg[id]; i < bg[id] + fac[x].size(); i++) {
int y = fac[x][i - bg[id]];
cur[id] += (cnt[y] & ~((1ll << k) - 1)) + (1ll << k) - 1;
nxt[i] = hd[y][k];
pre[i] = 0; pre[hd[y][k]] = i;
hd[y][k] = i;
}
}
int main() {
for(int i = 2; i < N; i++) {
if(!npri[i]) pri[++pcnt] = i;
for(int j = 1; j <= pcnt; j++) {
if(i * pri[j] >= N) break;
npri[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
for(int i = 1; i <= pcnt; i++) {
for(int j = 1; pri[i] * j < N; j++) {
fac[pri[i] * j].push_back(pri[i]);
}
}
cin >> n >> m;
ll lstans = 0; vector<int> ans;
while(m--) {
int op, x; ll y; cin >> op >> x >> y; y ^= lstans;
if(op == 0) {
for(int i : fac[x]) {
ll tmp = cnt[i] + y;
for(int k = LOGV - 1; k >= 0; k--) {
ll t = (tmp & ~((1ll << k) - 1)) - (cnt[i] & ~((1ll << k) - 1)) >> k;
if(!t) continue;
buf.clear();
for(int j = hd[i][k]; j; j = nxt[j]) buf.push_back(val[j]);
for(int j : buf) {
if(cur[j] + t * (1ll << k) >= tar[j]) {
if(k == 0) {
ans.push_back(j);
erase(j, k);
} else {
erase(j, k);
insert(j, k - 1);
}
} else cur[j] += t * (1ll << k);
}
}
cnt[i] += y;
}
sort(ans.begin(), ans.end());
cout << (lstans = ans.size()) << ' ';
for(int i : ans) cout << i << ' '; cout << '\n';
ans.clear();
} else {
tar[++nq] = y; p[nq] = x;
if(y == 0) { ans.push_back(nq); continue; }
for(int i : fac[x]) tar[nq] += cnt[i];
int k;
for(k = LOGV - 1; k >= 0; k--) {
ll sum = 0;
for(int i : fac[x]) sum += (cnt[i] & ~((1ll << k) - 1)) + (1ll << k) - 1;
if(sum < tar[nq]) {
cur[nq] = sum;
break;
}
}
bg[nq] = nn + 1;
for(int i : fac[x]) {
val[++nn] = nq;
nxt[nn] = hd[i][k];
pre[hd[i][k]] = nn;
hd[i][k] = nn;
}
}
}
return 0;
}
|
用一个小根堆维护所有合法的边，每次取出最小的一个边，合并两个连通块。对每条边维护一个折半警报器，记 \(cur_i=sum[u]+sum[v]\)，那么为两个点设置阈值 \(sum[u]+\lceil\frac{w_i-cur_i}{2}\rceil\) 和 \(sum[v]+\lceil\frac{w_i-cur_i}{2}\rceil\)。达到阈值后更新阈值。显然每条边只会触发 \(O(\log V)\) 次。用堆+启发式合并维护，时间复杂度为 \(O(n\log n\log V)\)。由于两个警报不会被同时触发（那样就直接删除了），因此不用像上文一样用可删堆维护。
考虑如果一个点 \(p\) 被所有区间包含，那我们可以把区间沿着 \(p\) 拆成两半分别维护，用线段树维护警报器即可。正解考虑把上面的过程搬到猫树上，形成一个树套树，时间复杂度还是 \(O(n\log^2n)\)。
也可以考虑操作分块，注意到如果每个人的 \(k\) 不太大是可以暴力的，因为使用线段树容易将包含一个点的所有区间拿出来。我们可以把每个人 \(k\) 较大的那一部分快速做，如果 \(k\) 低于阈值 \(blen\) 就把它扔进线段树里暴力维护。这样每处理 \(blen\) 个操作就把还不在线段树里的人都 \(O(n)\) 扫一遍。取 \(blen=\sqrt n\)，时间复杂度 \(O(n\sqrt n)\)。
代码
| #include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N = 4e5 + 10;
struct ren {
int l, r, k;
} a[N];
int n, blen, cnt;
int vis[N];
int buf[N], top;
int s[N];
namespace SegT {
vector<int> tr[4 * N];
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
void insert(int p, int l, int r, int ql, int qr, int id) {
if(ql <= l && r <= qr) {
tr[p].push_back(id);
return;
}
int mid = (l + r) >> 1;
if(ql <= mid) insert(lc(p), l, mid, ql, qr, id);
if(mid < qr) insert(rc(p), mid + 1, r, ql, qr, id);
}
void add(int p, int l, int r, int q) {
static int tmp[N], tp; tp = 0;
for(int i : tr[p]) tmp[++tp] = i;
tr[p].clear();
for(int ii = 1; ii <= tp; ii++) {
int i = tmp[ii];
if(vis[i] == 2) continue;
else if(--a[i].k == 0) buf[++top] = i, vis[i] = 2;
else tr[p].push_back(i);
}
if(l == r) return;
int mid = (l + r) >> 1;
if(q <= mid) add(lc(p), l, mid, q);
else add(rc(p), mid + 1, r, q);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n; blen = max(2, (int)(1.2 * sqrt(n)));
for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r >> a[i].k;
for(int i = 1; i <= n; i++) {
if(a[i].k == 0) buf[++top] = i, vis[i] = 2;
else if(a[i].k <= blen) SegT::insert(1, 1, n, a[i].l, a[i].r, i), vis[i] = 1;
}
while(top) {
if(cnt % blen == 0) {
for(int i = 1; i <= n; i++) s[i] += s[i - 1];
for(int i = 1; i <= n; i++) {
if(vis[i] == 0) {
a[i].k -= s[a[i].r] - s[a[i].l - 1];
if(a[i].k <= blen) SegT::insert(1, 1, n, a[i].l, a[i].r, i), vis[i] = 1;
}
}
for(int i = 1; i <= n; i++) s[i] = 0;
}
int x = buf[top--]; s[x]++;
SegT::add(1, 1, n, x); ++cnt;
}
cout << cnt << '\n';
return 0;
}
|