[UOJ 50][UR #3]链式反应

给你一个集合\(S\)(保证其中元素都为小于\(n\)的自然数),定义一棵合法的树为一棵编号满足堆的性质,且非叶子节点都一定有两个可能非叶子的儿子,同时有\(c(c\in S)\)个一定为叶子的儿子。对于所有\(i = 1\ldots n\),求有多少大小为\(i\)的形态不同的合法的树。

\(n\leq 200000\)。

继续阅读

[LibreOJ 6268]分拆数

定义分拆数\(f(x)\)表示将\(x\)拆为若干正整数的本质不同方案数。对于\(i = 1\ldots n\),输出\(f(i)\)。

\(1\leq n\leq 10^5\)。

继续阅读

[CF 438E]The Child and Binary Tree

给你一个大小为\(n\)的集合\({c_1, c_2,\ldots ,c_n}\),规定合法的二叉树为带点权且点权都属于给定集合中的点的数。对于任意整数$i\in [1, m]$,求出有多少不同的点权和为\(i\)的二叉树并输出之。

\(1\leq n, m, c_i\leq 10^5\)。

继续阅读

[CF 1000F]One Occurrence

好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io然后因为我回学校了所以接下来很长时间可能会继续用这个博客?

我谔谔,还是说这题……

对于询问\([l, r]\),考虑所有数在其中第一次出现的位置,如果说这个数在整个区间里只出现了一次,那么这个数下一次出现的位置一定大于\(r\)。

因此我们用扫描线搞一下就好啦……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
  maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
  if(L == R) {
    maxv[o] = std::make_pair(-1, -1);
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, const int &p, const pii &v) {
  if(L == R) {
    maxv[o] = v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o);
  }
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
  if(ql <= L && R <= qr) {
    return maxv[o];
  } else {
    int M = (L + R) / 2;
    pii ret = std::make_pair(-100, -100);
    if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
    if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
    return ret;
  }
}

int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
  int n; scanf("%d", &n);
  std::fill(rec, rec + maxn, n + 1);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = n; i >= 1; i --) {
    next[i] = rec[A[i]];
    rec[A[i]] = i;
  }
  int q; scanf("%d", &q);
  for(int i = 1; i <= q; i ++) {
    int l, r; scanf("%d%d", &l, &r);
    que[l].push_back({r, i});
  }
  build_tree(1, 1, n);
  for(int i = 1; i <= 500000; i ++) {
    if(rec[i] <= n) {
      modify(1, 1, n, rec[i], {next[rec[i]], i});
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(const pii &g : que[i]) {
      int r = g.first, id = g.second;
      pii tmp = query(1, 1, n, i, r);
      if(tmp.first <= r) {
        ans[id] = 0;
      } else {
        ans[id] = tmp.second;
      }
    }
    int nx = next[i];
    if(nx <= n) {
      modify(1, 1, n, nx, {next[nx], A[i]});
    }
  }
  for(int i = 1; i <= q; i ++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

[51Nod 1220]约数之和

沿用约数个数和一题的思路……可以列出此式:

\[\sigma_1(ij) = \sum_{a | i}\sum_{b | j} ab[\gcd(\frac{i}{a}, b) = 1]\]

然后我们考虑去化简原式:

\[
\begin{aligned}
\sum_{i = 1}^n\sum_{j = 1}^n\sum_{a | i}\sum_{b | j} ab\sum_{d | \frac{i}{a}, d | j}\mu(d)
\end{aligned}
\]

接下来我们考虑枚举\(d\),但是\(a\)和\(b\)的贡献又有点麻烦了……

\(b\)的贡献还好说,直接枚举\(b\)本身是\(d\)的多少倍就是\(\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\)。那\(a\)的贡献如何考虑?

我们考虑直接去枚举\(a\)本身……可以注意到一定有\(a\le\lfloor\frac{n}{d}\rfloor\)(因为\(\frac{i}{a}\ge d\)),所以直接枚举\(a\)本身之后再考虑\(\lfloor\frac{n}{a}\rfloor\)范围内\(d\)的倍数的数量即可(相当于找\(\frac{i}{a}\)),因此贡献为\(\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\)。

那么继续化简原式:

\[
\begin{aligned}
\quad&\sum_{d = 1}^n\mu(d)\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\\
=&\sum_{d = 1}^n\mu(d)d(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} i\lfloor\frac{n}{id}\rfloor)^2\\
=&\sum_{d = 1}^n\mu(d)d S_1^2(\lfloor\frac{n}{d}\rfloor)
\end{aligned}
\]

此处\(S_1\)表示\(\sigma_1\)的前缀和。

接下来预处理\(\mu(d)d\)的前缀和,考虑杜教筛。我们发现该函数和\(\mathrm{id}\)卷出来就是\(\epsilon\)(证明可以考虑贝尔级数……这种方式非常有效,并且还能帮我们找到需要卷的函数,我有时间会专门撰文写一下),所以杜教筛一波即可。这部分总复杂度为\(O(n^{\frac{2}{3}})\)。

至于\(S_1\),我们考虑不大于\(n^{\frac{2}{3}}\)可以直接预处理,剩下的用时就用\(O(\sqrt{n})\)的方法求(考虑到反演不会用到\(S_1\)的重复状态所以不需要记忆化)。用类似于杜教筛复杂度证明的方法可以证明该部分总复杂度为\(O(n^{\frac{2}{3}})\)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
const int N = 1000000;
using ll = long long;
const ll ha = 1000000007LL;
const ll i2 = 500000004LL;
ll mud[N + 5], sig_1[N + 5];
int prm[N + 5]; bool vis[N + 5];
void sieve() {
  int cnt = 0;
  mud[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      mud[i] = (ha - i);
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        mud[v] = 0; break;
      } else {
        mud[v] = (mud[i] * mud[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = i; j <= N; j += i) {
      sig_1[j] = (sig_1[j] + (ll(i))) % ha;
    }
  }
  for(int i = 1; i <= N; i ++) {
    mud[i] = (mud[i - 1] + mud[i]) % ha;
    sig_1[i] = (sig_1[i - 1] + sig_1[i]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
ll calc_id(ll x) {
  ll v1 = x, v2 = x + 1LL;
  if(x & 1LL) {
    v2 /= 2LL;
  } else {
    v1 /= 2LL;
  }
  return ((v1 * v2) % ha);
}
ll calc_mud(ll n) {
  if(n <= (ll(N))) return mud[n];
  if(ma.count(n)) return ma[n];
  ll ans = 1, las = 1;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans - (ns * calc_mud(n / i)) % ha + ha) % ha;
    las = nv; i = next + 1LL;
  }
  ma[n] = ans; return ans;
}
ll calc_s1(ll n) {
  if(n <= (ll(N))) return sig_1[n];
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans + (ns * (n / i)) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_mud(next); ll ns = (nv - las + ha) % ha;
    ll pv = calc_s1(n / i); pv = (pv * pv) % ha;
    ans = (ans + (ns * pv) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", calc(n));
  return 0;
}

[LibreOJ 2185][SDOI2015]约数个数和

首先我们有这样一个式子:

\[d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(\frac{i}{a}, b) = 1]\]

怎样理解这一结论呢?我们知道\(ij\)的约数\(d\)一定可以被分解为\(ab\)使得\(a | i, b | j\),但这种划分可能会非常的多,我们要保证每个约数\(d\)只有一种划分被统计过。

那么考虑上述划分方法。对于\(i\)和\(j\)中一个有一个没有的质因子,是一定会划分到\(a\)和\(b\)中固定的一个的。那么考虑一个在\(i\)和\(j\)中都出现的质因子\(p\),假设\(p\)在\(d\)中出现的次数超过了\(i\)和\(j\)中任何一个的话,那么\(p\)在\(a\)中一定会尽可能多的出现(否则\(\frac{i}{a}\)中会出现\(p\),而这样无论如何一定有\(p | b\),因此会不满足\(\gcd(\frac{i}{a}, b) = 1\))。如果没超过呢?那么一定会全部划分到\(a\)中(其他情况下有\(p | b\)并且会出现\(p | \frac{i}{a}\))。

下面考虑应用这个结论(为了方便,使用等价的\(d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(a, b) = 1]\),假设\(n\le m\)):

\[
\begin{aligned}
\quad&\sum_{i = 1}^n\sum_{j = 1}^m \sum_{a | i}\sum_{b | j}\sum_{d | i, d | j}\mu(d)\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{ad}\rfloor\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{bd}\rfloor\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}d(a)\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}d(b)
\end{aligned}
\]

后面两个和式可以随便\(O(n)\)欲处理一下(然后我当初写了个\(O(n\sqrt{n})\)的神必预处理……),然后这个题做完力,,,

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
typedef long long int_t;
const int maxn = 50005;
int_t miu[maxn], miu_s[maxn], f[maxn];
void process() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  const int N = 50000;
  miu[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      miu[i] = -1LL; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
      int v = prm[j] * i;
      vis[v] = true;
      if(i % prm[j] == 0) {
        miu[v] = 0; break;
      } else {
        miu[v] = miu[i] * -1;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    miu_s[i] = miu_s[i - 1] + miu[i];
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = 1; j <= i;) {
      int nx = i / (i / j);
      f[i] += (int_t(nx - j + 1)) * (int_t(i / j));
      j = nx + 1;
    }
  }
}

int_t solve(int n, int m) {
  int_t ans = 0;
  for(int i = 1; i <= std::min(n, m);) {
    int nx = std::min(m / (m / i), n / (n / i));
    ans += (miu_s[nx] - miu_s[i - 1]) * f[m / i] * f[n / i];
    i = nx + 1;
  }
  return ans;
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  process(); int T;
  scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    printf(LO, solve(n, m)); puts("");
  }
  return 0;
}

[LibreOJ 2100][TJOI2015]线性代数

颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1,而\(A_i\)为1会导致答案减去一个\(C_i\)。

因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益,但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力,,,

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
  add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}

int d[maxno];
int s, t, num;
bool bfs() {
  static bool vis[maxno];
  std::fill(vis, vis + num + 1, false);
  std::fill(d, d + num + 1, 0);
  std::queue<int> Q; Q.push(s);
  d[s] = 1; vis[s] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1;
        Q.push(v); vis[v] = true;
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ret = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i], f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ret += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ret;
}
int dinic() {
  int ret = 0;
  while(bfs()) {
    for(int i = 0; i <= num; i ++) cur[i] = first[i];
    ret += dfs(s, 0x7f7f7f7f);
  }
  return ret;
}

int n;
int main() {
  int ans = 0;
  scanf("%d", &n);
  s = 0, t = n * n + n + 1;
  num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = (i - 1) * n + j; int val; scanf("%d", &val);
      ans += val; ins_edge(s, u, val);
      ins_edge(u, n * n + i, 0x7f7f7f7f);
      ins_edge(u, n * n + j, 0x7f7f7f7f);
    }
  }
  for(int i = 1; i <= n; i ++) {
    int val; scanf("%d", &val);
    ins_edge(n * n + i, t, val);
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

[51Nod 1237]最大公约数之和 V3

首先这个题和能量采集几乎完全一致……稍微有点反演常识的人都知道答案事\(\sum_{i = 1}^n\varphi(i)\lfloor\frac{n}{i}\rfloor^2\),然后你需要用\(\varphi\)的前缀和,这个东西直接杜教筛搞一波就行了。这样总复杂度事\(O(n^{\frac{2}{3}})\)的,下面给出证明。

先考虑杜教筛的部分。杜教筛可以看做一个转移复杂度为\(O(\sqrt{n})\)的DP,他的状态一定是通过总的\(n\)整除一个数得到的。不大于\(n^{\frac{2}{3}}\)的状态我们都事先预处理,那么我们假设所有大于\(n^{\frac{2}{3}}\)的状态都被计算了一遍,这些状态一定事通过\(n\)整除一个不大于\(n^{\frac{1}{3}}\)的数得到的。因此复杂度为:

\[\sum_{i = 1}^{n^{\frac{1}{3}}} \sqrt{\lfloor\frac{n}{i}\rfloor}\leq \int_0^{n^{\frac{1}{3}}} \sqrt{\frac{n}{x}}\mathrm{d}x = 2n^{\frac{2}{3}} = O(n^{\frac{2}{3}})\]

至于莫比乌斯反演,不考虑杜教筛的复杂度的话就只是\(O(\sqrt{n})\)而已了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <utility>
using ll = long long;
constexpr ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

const int N = 10000000;
ll phi[N + 1]; int prm[N + 1]; bool vis[N + 1];
void sieve() {
  phi[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi[i] = i - 1; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j]; if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        phi[v] = phi[i] * prm[j]; break;
      } else {
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi[i] = (phi[i] + phi[i - 1]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
const ll i2 = inv(2LL);
ll phi_sum(ll n) {
  if(n <= (ll(N))) return phi[n];
  if(ma.count(n)) return ma[n];
  ll fg = (n % ha) * ((n + 1LL) % ha) % ha * i2 % ha;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll len = (next - i + 1LL) % ha;
    fg = (fg - (len * phi_sum(n / i)) % ha + ha) % ha;
    i = next + 1LL;
  }
  ma[n] = fg; return fg;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll b = ((n / i) % ha) * ((n / i) % ha) % ha;
    ll ns = phi_sum(next);
    ans = (ans + (((ns - las + ha) % ha) * b % ha)) % ha; las = ns;
    i = next + 1LL;
  }
  return ans;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", calc(n));
  return 0;
}

[BZOJ 4025]二分图

只会做水题力……qwq(搞错大小写,自裁请

每条边存在的时间事一个区间,因此考虑线段树分治……首先当然要写一个可撤销并查集。

然后每个点维护他到父亲的边的边权膜2,合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了,因为LCA到根的部分会算两遍,对答案无影响。

代码:

/**************************************************************
    Problem: 4025
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9928 ms
    Memory:34840 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
const int maxn = 100005;
const int maxno = maxn << 2;
const int maxm = 200005;
int n, m, T;
 
int p[maxn], siz[maxn], d[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; siz[i] = 1; d[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
int get_d(int x) {
  if(p[x] == x) {
    return 0;
  } else {
    return (d[x] + get_d(p[x])) % 2;
  }
}
typedef std::pair<int, int> upd;
upd link_set(int x, int y, int v) {
  if(siz[x] > siz[y]) std::swap(x, y);
  p[x] = y; siz[y] += siz[x]; d[x] = v;
  return std::make_pair(x, y);
}
upd merge_set(int x, int y) {
  int v = (get_d(x) + get_d(y) + 1) % 2;
  return link_set(get_fa(x), get_fa(y), v);
}
void unlink_set(const upd &pr) {
  int x = pr.first, y = pr.second;
  p[x] = x; siz[y] -= siz[x]; d[x] = 0;
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
std::vector<upd> event[maxno];
std::stack<std::pair<int, upd> > S;
void update(int o, int L, int R, int ql, int qr, upd v) {
  if(ql <= L && R <= qr) {
    event[o].push_back(v);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
  }
}
int val[maxno];
void solve(int o, int L, int R) {
  for(int i = 0; i < event[o].size(); i ++) {
    const upd &pr = event[o][i];
    int x = pr.first, y = pr.second;
    if(is_same(x, y)) {
      if((get_d(x) + get_d(y)) % 2 == 0) {
        val[o] = 0;
        break;
      }
    } else {
      S.push(std::make_pair(o, merge_set(x, y)));
    }
  }
  if(L == R) {
    if(val[o] != 0) val[o] = 1;
  } else {
    if(val[o] != 0) {
      int M = (L + R) / 2;
      solve(o << 1, L, M);
      solve(o << 1 | 1, M + 1, R);
    }
  }
  while((!S.empty()) && S.top().first >= o) {
    upd v = S.top().second; S.pop();
    unlink_set(v);
  }
}
void print(int o, int L, int R) {
  if(L == R) {
    if(val[o]) {
      puts("Yes");
    } else {
      puts("No");
    }
  } else {
    if(val[o] != -1) {
      val[o << 1] = val[o];
      val[o << 1 | 1] = val[o];
    }
    int M = (L + R) / 2;
    print(o << 1, L, M);
    print(o << 1 | 1, M + 1, R);
  }
}
 
int main() {
  memset(val, -1, sizeof(val));
  scanf("%d%d%d", &n, &m, &T);
  for(int i = 1; i <= m; i ++) {
    int u, v, s, t; scanf("%d%d%d%d", &u, &v, &s, &t);
    s ++; if(s <= t) update(1, 1, T, s, t, std::make_pair(u, v));
  }
  init_dsu(); solve(1, 1, T); print(1, 1, T);
  return 0;
}

[LibreOJ 2472][九省联考2018]IIIDX

一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解

还有样例过于草(出题人钦点淫梦运营

考虑从小到大枚举序列的每一位置\(p\),然后我们发现每一位置的值的合法性事单调的(小的合法,大了就不合法),这样可以对每一个位置二分答案。

然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)(表示当前还没有被预定的大于等于\(i\)的数有多少个),然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响,然后每次一个点确定是什么值了也要修改对应的前缀区间。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, addv[o]); paint(rc, addv[o]);
    addv[o] = 0;
  }
}

int left[maxn];
void build_tree(int o, int L, int R) {
  // addv[o] = 0;
  if(L == R) {
    minv[o] = left[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = INF;
    if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

int d[maxn], d2[maxn];
int lsiz;
void process() {
  std::sort(d + 1, d + 1 + n);
  std::sort(d2 + 1, d2 + 1 + n);
  lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
  for(int i = 1; i <= n; i ++) {
    d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
    left[d[i]] ++;
  }
  for(int i = lsiz - 1; i >= 1; i --) {
    left[i] += left[i + 1];
  }
  build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
  for(int i = n; i >= 1; i --) {
    siz[i] ++;
    int f = (int)floor((R(i)) / k);
    siz[f] += siz[i];
  }
  for(int i = 1; i <= n; i ++) {
    int f = (int)floor((R(i)) / k);
    if(f > 0) {
      update(1, 1, lsiz, 1, A[f], siz[i]);
    }
    int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
    while(true) {
      if(R - L <= 3) {
        for(int j = R; j >= L; j --) {
          if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
            ret = j; break;
          }
        }
        break;
      }
      int M = L + (R - L) / 2;
      if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
        L = M;
      } else {
        R = M;
      }
    }
    A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
  }
}

int main() {
  scanf("%d%Lf", &n, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &d[i]); d2[i] = d[i];
  }
  process(); solve();
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    printf("%d", d2[A[i]]);
  }
  puts(""); return 0;
}