和麻衣学姐一起工作
有 \(n\) 个人，每个人有一个能力值 \(v_i\)，他只愿意和能力值不低于 \(l_i\) 且不高于 \(r_i\) 的人一起合作帮助麻衣学姐。麻衣学姐想知道最多可以选出多少人一起帮她。
\(n\) (\(1 \le n \le 10^5\))
\(l_i\), \(v_i\), \(r_i\) (\(1 \le l_i \le v_i \le r_i \le 3 \cdot 10^{5}\))
题解：线段树 + 扫描线
- 对于选出的人所形成的集合\(S\)，一定满足
\[ maxl_i \leq minv_i\leq maxv_i \leq minr_i \]
那么对于\(maxl_i \leq minv_i\)来说
我们可以抽象成：在一维上，给定了一些线段\([l_i,v_i]\)，让你求哪个区间覆盖的线段最多
那么对于这个问题，我们显然可以利用线段树区间加和区间最大值来解决
但是我们同时又要满足\(maxv_i \leq minr_i\)
所以我们不妨考虑将问题抽象到二维平面上
假设每个人就是一个左下角坐标为\((l_i,v_i)\)，右上角坐标为\((v_i,r_i)\)的矩阵
那么满足上述两个限制条件的体现在平面上就是每个矩阵的交
那么我们可以将问题转化为：在二维平面上，给定一些矩阵，让你找到一个点被尽可能多的矩形覆盖
那么实际上这就是一个矩形面积并的弱化版
我们只需要在线段树上维护最大值即可
题目要求输出方案，我们考虑在最多矩形交的区域中找一个点，然后遍历所有人，检查该点是否在这个人的矩形中即可，找点可以线段树上二分或者在线段树上再维护一下最大值出现的位置即可
const int N = 3e5 + 10, M = 4e5 + 10;
int n;
int l[N], v[N], r[N];
vector<array<int, 5>> eve;
struct info
{
int mx;
};
struct SEG
{
int lazy;
info val;
} seg[N << 2];
info operator+(const info &a, const info &b)
{
info c;
c.mx = max(a.mx, b.mx);
return c;
}
void settag(int id, int tag)
{
seg[id].val.mx += tag;
seg[id].lazy += tag;
}
void up(int id)
{
seg[id].val = seg[lson].val + seg[rson].val;
}
void down(int id)
{
if (seg[id].lazy == 0)
return;
settag(lson, seg[id].lazy);
settag(rson, seg[id].lazy);
seg[id].lazy = 0;
}
void build(int id, int l, int r)
{
if (l == r)
{
seg[id].lazy = 0;
seg[id].val.mx = 0;
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
up(id);
}
void modify(int id, int l, int r, int ql, int qr, int val)
{
if (ql <= l && r <= qr)
{
settag(id, val);
return;
}
down(id);
int mid = l + r >> 1;
if (qr <= mid)
modify(lson, l, mid, ql, qr, val);
else if (ql > mid)
modify(rson, mid + 1, r, ql, qr, val);
else
{
modify(lson, l, mid, ql, qr, val);
modify(rson, mid + 1, r, ql, qr, val);
}
up(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return seg[id].val;
}
down(id);
int mid = l + r >> 1;
if (qr >= mid)
return query(lson, l, mid, ql, qr);
else if (ql > mid)
return query(rson, mid + 1, r, ql, qr);
else
return query(lson, l, mid, ql, qr) + query(rson, mid + 1, r, ql, qr);
}
int query_max(int id, int l, int r, int val)
{
if (l == r)
{
return l;
}
down(id);
int mid = l + r >> 1;
int mx = seg[lson].val.mx;
if (mx == val)
return query_max(lson, l, mid, val);
else
return query_max(rson, mid + 1, r, val);
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> l[i] >> v[i] >> r[i];
eve.push_back({v[i], -1, 1, l[i], v[i]});
eve.push_back({r[i], 1, -1, l[i], v[i]});
}
// 从y轴升序进行扫描
sort(all(eve));
int m = 3e5 + 10;
build(1, 1, m);
int ans = -INF;
int qx = 0, qy = 0;
int qxx = INF;
for (auto &[y, typ, val, ql, qr] : eve)
{
modify(1, 1, m, ql, qr, val);
int mx = query(1, 1, m, 1, m).mx;
// cout << "Y = " << y << " , max = " << mx << ", qr = " << qr << endl;
if (mx > ans)
{
ans = mx;
qx = query_max(1, 1, m, ans);
qy = y;
}
}
// cout << qx << " " << qy << endl;
vector<int> res;
for (int i = 1; i <= n; ++i)
{
if (l[i] <= qx && qx <= v[i] && v[i] <= qy && qy <= r[i] || l[i] <= qxx && qxx <= v[i] && v[i] <= qy && qy <= r[i])
res.push_back(i);
}
cout << ans << endl;
for (auto x : res)
cout << x << " ";
cout << endl;
}
E. 帮麻衣学姐分类
麻衣学姐手上突然有了 \(n\) 个不同的数字: \(p_1,p_2,\cdots,p_n\). 她想把这些数字分成两个集合 \(A\) 和 \(B\)。但是你必须满足下面的条件： - 如果 \(x\) 在集合 \(A\), 数字 \(a-x\) 也必须在集合 \(A\). - 如果 \(x\) 在集合 \(B\), 数字 \(b-x\) 也必须在集合 \(B\). 请你帮帮麻衣学姐，或者说明这是不可能的。
\(n,a,b\) \((1\leq n\leq 10^5;~1\leq a,b\leq 10^9)\)
\(p_1,p_2,\cdots,p_n~(1\leq p_i\leq 10^9)\)
题解：2-SAT
- 我们定义\(i\)代表\(a_i\)在集合A，\(i + n\)代表\(a_i\)在集合B
- 如果对于\(x\)来说，没有\(a - x\)和\(b - x\)存在，输出
NO- 如果对于\(x\)来说，只有\(a - x\)存在，说明\(x\)和\(a - x\)一定在集合A，两者是与关系
- 如果对于\(x\)来说，只有\(b - x\)存在，说明\(x\)和\(b - x\)一定在集合B，两者是与关系
- 如果对于\(x\)来说，\(a - x\)和\(b - x\)同时存在：
- 如果\(x\)在集合A，那么\(a-x\)和\(b-x\)一定也在集合A
- 如果\(x\)在集合B，那么\(a-x\)和\(b-x\)一定也在集合B
- 明确逻辑关系后之间建图后跑2-SAT即可
- 最后对于任意一个数字，该数字一定在\(scc\)编号小的集合中
const int N = 2e5 + 10, M = 4e5 + 10;
int n, a, b;
map<int, int> mp;
vector<int> g[N];
int idx, sccnt, dfn[N], low[N], scc[N];
int stk[N], top;
int p[N], ans[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
stk[++top] = u;
for (auto v : g[u])
{
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (!scc[v])
low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u])
{
sccnt++;
while (stk[top] != u)
{
scc[stk[top]] = sccnt;
top--;
}
scc[stk[top]] = sccnt;
top--;
}
}
void solve()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i)
{
cin >> p[i];
mp[p[i]] = i;
}
for (int i = 1; i <= n; ++i)
{
if (!mp[a - p[i]] && !mp[b - p[i]])
{
cout << "NO" << endl;
return;
}
else if (mp[a - p[i]] && !mp[b - p[i]])
{
g[i + n].push_back(i);
g[mp[a - p[i]] + n].push_back(mp[a - p[i]]);
}
else if (!mp[a - p[i]] && mp[b - p[i]])
{
g[i].push_back(i + n);
g[mp[b - p[i]]].push_back(mp[b - p[i]] + n);
}
else
{
g[i].push_back(mp[a - p[i]]);
g[i].push_back(mp[b - p[i]]);
g[i + n].push_back(mp[a - p[i]] + n);
g[i + n].push_back(mp[b - p[i]] + n);
}
}
for (int i = 1; i <= 2 * n; ++i)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; ++i)
{
if (scc[i] == scc[i + n])
{
cout << "NO" << endl;
return;
}
else if (scc[i] > scc[i + n])
ans[i] = ans[mp[a - p[i]]] = 1;
else
ans[i] = ans[mp[b - p[i]]] = 0;
}
cout << "YES" << endl;
for (int i = 1; i <= n; ++i)
cout << ans[i] << "\n "[i < n];
}
J. 和三玖一起填格子
三玖是一个热爱研究网格的女孩，她家里最多的东西就是网格纸。她有一个幸运数字 \(k\) ，有一天她心血来潮，决定将一些数字填到一张 \(n \times n\) 的网格纸中，使得每个格子都有一个数，并且还要满足如下要求： - 所有数字要在 \([1,k]\) 的范围内. - 第 \(i\) 行的最小值为 \(1\) (\(1 \le i \le n\)). - 第 \(j\) 列的最小值为 \(1\) (\(1 \le j \le n\)). 现在，她想知道有多少种方案可以填好网格纸。你可以告诉她吗？由于答案可能很大，请输出对 \((10^{9} + 7)\) 取模的结果
\(n\) 和 \(k\) (\(1 \le n \le 250\), \(1 \le k \le 10^{9}\))
题解：容斥 + 组合计数
考虑容斥
我们从反面考虑，总方案数减去不合法的方案数就是合法的方案数
因为存在行合法以及列合法两种情况，我们不妨钦定行合法，然后对不合法的列进行容斥
首先，一行所有数合法的方案数为\(k^n - (k - 1)^n\)
然后我们枚举至少有\(i\)列不合法，那么每一行合法的方案数为\((k - 1)^i\times k^{n - i} - (k - 1)^n\)
所以\(n\)行都合法的方案数为\(C_n^i((k - 1)^i\times k^{n - i} - (k - 1)^n)^n\)
那么答案为:
\[\sum_{i = 0}^{n}(-1)^iC_n^i((k - 1)^i\times k^{n - i} - (k - 1)^n)^n \]
const int N = 5e2 + 10, M = 4e5 + 10;
int n, k;
int qpow(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res % p;
}
int fac[N], inv[N];
void init()
{
fac[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[N - 1] = qpow(fac[N - 1], mod - 2, mod);
for (int i = N - 2; i >= 0; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int a, int b)
{
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
void solve()
{
init();
cin >> n >> k;
int ans = 0;
for (int i = 0; i <= n; ++i)
{
int t1 = qpow(k - 1, i, mod);
int t2 = qpow(k, n - i, mod);
int t3 = qpow(k - 1, n, mod);
int sum = (t1 * t2 % mod - t3) % mod;
if (i & 1)
{
ans = (ans % mod - C(n, i) * qpow(sum, n, mod) % mod) % mod;
if (ans < 0)
ans += mod;
}
else
ans = (ans % mod + C(n, i) * qpow(sum, n, mod) % mod) % mod;
}
cout << ans << endl;
}
L. 和水原千鹤一起数串串Ⅰ
水原千鹤超级喜欢回文串，她手上有一个下标从 \(0\) 开始的长度为 \(N\) 的字符串。字符串由 26 个小写英语字母组成。水原千鹤的朋友们会给她 \(Q\) 次询问，分为两种类型：
- \(1\ x\ y\) 代表把下标为 \(x\) 的字符改成 \(y\)
- \(2\ l\ r\) 代表询问区间为 \([l,r]\) 的子串可以重排出多少个不同的回文串
题解：树状数组 + 组合计数
- 开\(26\)个树状数组维护每个字母出现的次数
- 一段区间中只能有一个字母出现的次数为奇数，其余全部是偶数次
- 重排的方案数就是简单组合计数
- 注意修改的时候同时需要修改原数组
const int N = 2e5 + 10, M = 4e5 + 10;
int n, q;
int fac[N], inv[N];
int qpow(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res % p;
}
struct BIT
{
int c[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
while (x < N)
{
c[x] += val;
x += lowbit(x);
}
}
int get_sum(int x)
{
int res = 0;
while (x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
int query(int l, int r)
{
return get_sum(r) - get_sum(l - 1);
}
} bit[26];
void init()
{
fac[0] = inv[0] = 1;
for (int i = 1; i < N; ++i)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = inv[i - 1] * qpow(i, mod - 2, mod) % mod;
}
}
void solve()
{
cin >> n >> q;
init();
string s;
cin >> s;
s = " " + s;
for (int i = 1; i <= n; ++i)
{
bit[s[i] - 'a'].add(i, 1);
}
while (q--)
{
int op, x, l, r;
char ch;
cin >> op;
if (op == 1)
{
cin >> x >> ch;
x++;
bit[s[x] - 'a'].add(x, -1);
bit[ch - 'a'].add(x, 1);
s[x] = ch;
}
else
{
cin >> l >> r;
l++, r++;
int num = 0;
int sum1 = 0, sum2 = 1;
for (int i = 0; i < 26; ++i)
{
int cnt = bit[i].query(l, r);
sum1 += cnt / 2;
sum2 = (sum2 % mod * inv[cnt / 2] % mod) % mod;
if (cnt & 1)
num++;
}
if (num > 1)
{
cout << 0 << endl;
continue;
}
cout << fac[sum1] * sum2 % mod << endl;
}
}
}