danihao123's Blog

[BZOJ 3992][SDOI2015]序列统计

终于调过去了……~~（然而不就是道NTT+生成函数水题吗至于调半天）~~

首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。

然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。

注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。

代码：

/**************************************************************
    Problem: 3992
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6652 ms
    Memory:1864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1, p);
  ans = (ans * ans) % p;
  if(b & 1LL) ans = (ans * a) % p;
  return ans;
}
ll inv(ll x, ll p) {
  return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
  int bd = sqrt(x + 0.5);
  for(ll i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
    if(x == 1LL) break;
  }
  if(x > 1LL) V.push_back(x);
}
ll get_phi() {
  if(m == 2LL) return 1LL;
  ll mi = m - 1LL;
  std::vector<ll> V;
  break_up(mi, V);
  for(ll i = 2; i <= mi; i ++) {
    bool ok = true;
    for(int j = 0; j < V.size(); j ++) {
      ll b = mi / V[j];
      if(pow_mod(i, b, m) == 1LL) {
        ok = false;
#ifdef LOCAL
        printf("%lld not passed!\n", i);
#endif
        break;
      }
    }
    if(ok) {
      return i;
    }
  }
}
 
int bi, len;
int flip(int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void ntt(ll *A, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(i);
    if(v < i) std::swap(A[i], A[v]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
    if(flag) xi_n = inv(xi_n, ha);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1;
      for(int j = i; j < i + L; j ++) {
        ll p1 = A[j], p2 = A[j + L];
        A[j] = (p1 + (p2 * w) % ha) % ha;
        A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
        w = (w * xi_n) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B) {
  static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("B :");
  for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
  puts("");
#endif
  ntt(A); ntt(B);
  for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
  ntt(C, true);
  ll inv_n = inv(len, ha);
  for(int i = 0; i < len; i ++) {
    C[i] = (C[i] * inv_n) % ha;
  }
#ifdef LOCAL
  printf("C (not processed) :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  for(int i = 0; i < len; i ++) {
    int v = i % (m - 1LL);
    if(v != i) {
      C[v] = (C[v] + C[i]) % ha;
      C[i] = 0LL;
    }
  }
#ifdef LOCAL
  printf("C :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
  static ll B[maxn];
  static ll res[maxn];
  std::copy(A, A + len, res);
  std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("res : ");
  for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
  puts("");
#endif
  while(b) {
    if(1LL & b) {
      std::copy(res, res + len, B);
      poly_mul(A, B);
      std::fill(B, B + len, 0);
    }
    std::copy(res, res + len, B);
    poly_mul(res, B);
    std::fill(B, B + len, 0);
    b >>= 1LL;
  }
}
 
int main() {
  static bool vis[maxn];
  static ll A[maxn];
  scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
  ll phi = get_phi();
  for(int i = 1; i <= sz; i ++) {
    int v; scanf("%d", &v);
    if(v == 0) continue;
    vis[v] = true;
  }
  int logx = 0;
  bi = 0; len = 1;
  while(len <= (2 * m - 2)) {
    bi ++; len <<= 1;
  }
  for(int i = 0; i < (m - 1); i ++) {
    int v = pow_mod(phi, i, m);
    if(vis[v]) {
      A[i] ++;
#ifdef LOCAL
      printf("log(%d) : %d\n", v, i);
#endif
    }
    if(v == gl) {
      logx = i;
    }
  }
  poly_pow(A, n);
  printf("%lld\n", A[logx]);
  return 0;
}

[BZOJ 2115][Wc2011]Xor

这个可以有啊（赞赏）！

我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。

然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。

然后这样可以发现，用$1$到$n$的路径来异或一个环，可以得到新的一条$1$到$n$的路径。

这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条$1$到$n$的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……

代码：

/**************************************************************
    Problem: 2115
    User: danihao123
    Language: C++
    Result: Accepted
    Time:652 ms
    Memory:6544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = d;
  return cnt;
}
void ins_edge(int u, int v, ll d) {
  int e1 = add_edge(u, v, d);
  int e2 = add_edge(v, u, d);
  rev[e1] = e2; rev[e2] = e1;
}
 
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
  for(int i = 60; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
  vis[x] = true; sum[x] = s;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    int v = to[i];
    used[i] = used[rev[i]] = true;
    if(vis[v]) {
      insert((s ^ sum[v]) ^ dist[i]);
    } else {
      dfs(v, s ^ dist[i]);
    }
  }
}
 
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; ll d;
    scanf("%d%d", &u, &v); scanf(LO, &d);
    ins_edge(u, v, d);
  }
  dfs(1, 0LL);
  ll ret = sum[n];
  for(int i = 60; i >= 0; i --) {
    if(!T[i]) continue;
    if(!(ret & (1LL << i))) {
      ret ^= T[i];
    }
  }
  printf(LO, ret); puts("");
  return 0;
}

[BZOJ 2876][NOI2012]骑行川藏

我终于A了……~~不就是拉格朗日乘数法的模板题吗~~

首先这道题最优情况下一定有（这里用$E_i$表示第$i$段路程的耗能）：$\sum_{i = 1}^n E_i = E_u$。

然后这个东西是一个等式限制条件，然后我们还要最小化总用时，给人拉格朗日乘数法的即视感……

不管怎么说让我们来列式子吧：

\[h(x_1, x_2,\ldots ,x_n, \lambda) = \sum_{i = 1}^n \frac{s_i}{x_i} + \lambda \sum_{i = 1}^n k_i s_i (x_i - v_i)^2\]

\[\frac{\partial h}{\partial x_i} = -\frac{s_i}{x_i^2} + 2\lambda k_i s_i (x_i - v_i)\]

然后你会想这TM怎么解方程……

但是我们想一想，把$\frac{\partial h}{\partial x_i} = 0$稍作整理，得：

\[\frac{1}{2k_i\lambda} = x_i^2 (x_i - v_i)\]

对于式子的左边，是一个关于$x_i$的增函数（因为这道题默认了$x_i\geq 0$且$x_i\geq v_i$），然后不妨令$\frac{1}{\lambda} = u$，可以发现$u$越大则$x_i$越大！这样一来那么我们的限制条件就会更加难以满足。

所以我们可以二分这个$u$来解这些方程。

BTW，这题卡精度非常厉害……

代码：

/**************************************************************
    Problem: 2876
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3960 ms
    Memory:1524 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
typedef double R;
const R eps = 1e-12;
const int maxn = 10005;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) {
      return -1;
    } else {
      return 1;
    }
  }
}
R s[maxn], k[maxn], V[maxn];
R rf(int i, R v, R delta) {
  return v * v * (v - V[i]) - delta;
}
R rf2(int i, R v) {
  return 3 * v * v - 2 * v * V[i];
}
R gen_rt(int i, R delta) {
  R x = 1e6;
  int lambda = 100;
  while(lambda --) {
    R a = rf(i, x, delta);
    if(sign(a) == 0) break;
    R da = rf2(i, x);
    x -= a / da;
  }
  return x;
}
int n; R E;
R gen_lft() {
  R l = 1e-14, r = 1e16;
  while(r - l > eps) {
#ifdef LOCAL
    printf("State [%.18lf, %.18lf]\n", l, r);
#endif
    R M = (l + r) / 2;
    R T = 0;
    for(int i = 1; i <= n; i ++) {
      R v = gen_rt(i, M / (2 * k[i]));
      T += (v - V[i]) * (v - V[i]) * k[i] * s[i];
    }
    if(sign(T - E) <= 0) {
      l = M;
    } else {
      r = M;
    }
  }
  return l;
}
 
int main() {
  std::cin >> n >> E;
  for(int i = 1; i <= n; i ++) {
    std::cin >> s[i] >> k[i] >> V[i];
  }
  R M = gen_lft();
  R tm = 0;
  for(int i = 1; i <= n; i ++) {
    R v = gen_rt(i, M / (2 * k[i]));
    tm += s[i] / v;
  }
  printf("%.8lf\n", tm);
  return 0;
}

[BZOJ 3925][ZJOI2015]地震后的幻想乡

赛艇，赛艇.jpg

首先这个问题的本质就是让你求一个边权在$[0, 1]$间均匀随机分布的无向图的MST的最大边边权的期望……

有一个很经典的式子：

\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]

然后考虑那个$p$咋整。

首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）$S$，式子可以这么写（这里不妨用$T$来表示两个点集间的边的数目）：

\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]

显然答案是$\int_0^1 p_{S, x}\,\mathrm{d}x$，但这玩咋求……

然后我们定义一个状态$d$：

\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]

把其中的$p$展开，整理一下，得到：

\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]

里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……

不就是$d_{S_0, T(S, S - S_0) + k}$ 吗？

然后这样整个$d$就可以搞一波状压DP了。

然后观察$d_{S, 0}$（这里不妨假设S为全集）：

\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]

这不就是我们要的答案吗？

至于边界处理，$d_{\{1\}, x}$全部搞成0就行。

代码：

/**************************************************************
    Problem: 3925
    User: danihao123
    Language: C++
    Result: Accepted
    Time:100 ms
    Memory:1272 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
 
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
  if(s == 1) return 0;
  if(vis[s][k]) return d[s][k];
  d[s][k] = 0;
  int lit_s = s >> 1;
  for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
    int s0 = lit_s0 * 2 + 1;
    int t = 0;
    for(int i = 1; i <= m; i ++) {
      int u = edge[i][0], v = edge[i][1];
      if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
      if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
        t ++;
      }
    }
    int z = k + t;
    d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
    if(s0 == 1) break;
  }
  vis[s][k] = true;
  return d[s][k];
}
 
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v); u --, v --;
    edge[i][0] = u, edge[i][1] = v;
  }
  printf("%.6lf\n", f((1 << n) - 1, 0));
  return 0;
}

[BZOJ 1095][ZJOI2007]Hide 捉迷藏

蛤蛤蛤我这题终于调出来了~~~（然后1A了）~~

点分树处女作。其实点分树的思想并不难理解，就是把点分的过程抽象化到一棵树上。

其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。

代码（其中有海量本来拿来调试的代码，慎读）：

/**************************************************************
    Problem: 1095
    User: danihao123
    Language: C++
    Result: Accepted
    Time:15268 ms
    Memory:128944 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
void add_edge(int u, int v) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
}
 
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
void dfs_1(int x, int father = 0, int depth = 1) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
 
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int fa = 0) {
  bool ok = (2 * siz[x] >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != fa) {
      ok = ok && (2 * siz[v] <= siz[nrt]);
      gen_rt(v, x);
    }
  }
  if(ok) rt = x;
}
int crt;
int cfa[maxn];
typedef std::priority_queue<int> heap;
struct dheap {
  heap Q, D;
  void push(int x) {
    Q.push(x);
  }
  void pop() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    Q.pop();
  }
  int top() {
    while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
      printf("deleting %d\n", D.top());
#endif
      Q.pop(); D.pop();
    }
    return Q.top();
  }
  void del(int x) {
    D.push(x);
  }
  size_t size() {
    return Q.size() - D.size();
  }
  int sec() {
    int fir = top(); pop();
    int ret = top(); push(fir);
    return ret;
  }
};
dheap all;
dheap Q[maxn], sg[maxn];
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      cfa[divide(v)] = x;
    }
  }
  return x;
}
int n;
int get_ans(dheap &q) {
  return q.top() + q.sec();
}
bool sta[maxn];
int dist(int x, int y) {
  int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)];
#ifdef DEBUG
  printf("dist(%d, %d) : %d\n", x, y, ret);
#endif
  return ret;
}
void light_on(int p) {
  sta[p] = true;
  int x = p;
  int og = -1, ng = 0;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) {
      old_ans = get_ans(Q[x]);
    }
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].push(dist(p, cfa[x]));
      ng = sg[x].top();
    }
    x = cfa[x];
  }
}
void light_off(int p) {
  sta[p] = false;
  int x = p;
  int og = 0, ng = -1;
  while(x) {
    int old_ans = -1, old_sg = -1;
    if(Q[x].size() > 1) old_ans = get_ans(Q[x]);
    if(sg[x].size() > 0) {
      old_sg = sg[x].top();
    }
    if(og != -1) Q[x].del(og);
    if(ng != -1) Q[x].push(ng);
#ifdef DEBUG
    printf("%d deleting %d\n", x, og);
#endif
    if(Q[x].size() > 1) all.push(get_ans(Q[x]));
    if(old_ans != -1) all.del(old_ans);
#ifdef DEBUG
    int tmp = -1;
    if(Q[x].size() > 1) tmp = get_ans(Q[x]);
    printf("ans of %d : %d -> %d\n", x, old_ans, tmp);
#endif
    if(cfa[x] != 0) {
      og = old_sg;
      sg[x].del(dist(p, cfa[x]));
      if(sg[x].size() > 0) {
        ng = sg[x].top();
      } else {
        ng = -1;
      }
    }
    x = cfa[x];
  }
}
void print_dheap(dheap &q) {
  std::vector<int> V;
  while(q.size() > 0) {
    int t = q.top(); q.pop();
    printf("%d ", t);
    V.push_back(t);
  }
  puts("");
  for(int i = 0; i < V.size(); i ++) {
    q.push(V[i]);
  }
}
 
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    add_edge(u, v); add_edge(v, u);
  }
  dfs_1(1); dfs_2(1);
#ifdef DEBUG
  for(int i = 1; i <= n; i ++) {
    printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]);
  }
#endif 
  crt = divide(1);
#ifdef DEBUG
  printf("crt id %d\n", crt);
  for(int i = 1; i <= n; i ++) {
    printf("cfa[%d] : %d\n", i, cfa[i]);
  }
#endif
  int num = 0;
  for(int i = 1; i <= n; i ++) {
    light_on(i); num ++;
#ifdef DEBUG
    printf("heap while inserting %d : ", i);
    print_dheap(all);
#endif
  }
  int q; scanf("%d", &q);
  while(q --) {
    char op[3]; scanf("%s", op);
    if(op[0] == 'G') {
      if(num == 0) {
        puts("-1");
      } else if(num == 1) {
        puts("0");
      } else {
        printf("%d\n", all.top());
      }
    } else {
      int i; scanf("%d", &i);
      if(sta[i]) {
        light_off(i);
        num --;
      } else {
        light_on(i);
        num ++;
      }
    }
#ifdef DEBUG
    print_dheap(all);
#endif
  }
  return 0;
}

[BZOJ 3295][CQOI2011]动态逆序对

又一道坑了很久没有写题解的……

删除操作特别的棘手，但好在我们可以离线~时光倒流之后，删除就变成了添加。

每个点加进来之后，对答案的贡献可以分为两部分：

加入比他早，位置在他前面，值比他大的点。
加入比他早，位置在他后面，值比他小的点。

然后两者都可以用CDQ统计~~（我还偷懒用同一个CDQ做的）~~。

代码：

/**************************************************************
    Problem: 3295
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2332 ms
    Memory:5768 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
    int id;
    int p, v;
};
 
int n;
ll C[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int p, int v) {
    while(p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}
ll sum(int p) {
    ll ret = 0;
    while(p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}
int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
void clean(int p) {
    while(p <= n && C[p] != 0) {
        C[p] = 0;
        p += lowbit(p);
    }
}
 
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
    if(L == R) {
        return;
    }
    int M = L + (R - L) / 2;
    CDQ(L, M, flag); CDQ(M + 1, R, flag);
    for(int p = L, l = L, r = M + 1; p <= R; p ++) {
        if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
            tmp[p] = A[l];
            add(A[l].v, 1);
            l ++;
        } else {
            tmp[p] = A[r];
            ans[A[r].id] += query(A[r].v + 1, n);
            r ++;
        }
    }
    for(int i = L; i <= M; i ++) {
        clean(A[i].v);
    }
    for(int i = L; i <= R; i ++) {
        A[i] = tmp[i];
    }
}
bool cmp_id(const Query& a, const Query& b) {
    return a.id < b.id;
}
 
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
    int m;
    scanf("%d%d", &n, &m);
    int id_siz = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= m; i ++) {
        int a;
        scanf("%d", &a);
        delS.push(a);
        del[a] = true;
    }
    for(int i = 1; i <= n; i ++) {
        if(del[arr[i]]) {
            pos[arr[i]] = i;
        } else {
            id_siz ++;
            A[id_siz].id = id_siz;
            A[id_siz].p = i;
            A[id_siz].v = arr[i];
        }
    }
    while(!delS.empty()) {
        int a = delS.top(); delS.pop();
        id_siz ++;
        A[id_siz].id = id_siz;
        A[id_siz].p = pos[a];
        A[id_siz].v = a;
    }
    CDQ(1, n, true);
    sort(A + 1, A + 1 + n, cmp_id);
    for(int i = 1; i <= n; i ++) {
        A[i].v = n - A[i].v + 1;
    }
    CDQ(1, n, false);
    for(int i = 1; i <= n; i ++) {
        ans[i] += ans[i - 1];
    }
    for(int i = 0; i < m; i ++) {
        printf("%lld\n", ans[n - i]);
    }
    return 0;
}

[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树，那就需要启发式合并了。

继续阅读

[BZOJ 1483][HNOI2009]梦幻布丁

做了很久了吧，但现在才写题解……（斜眼

首先记录一个起始的颜色段数，然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是，很多时候并不是把小链表的扔到大的里面的情况，而是恰好反过来的情况，如何处理？

这种时候，我们可以交换两个颜色的“真实身份”。合并的时候，把每个点当成它的“真实身份”处理即可。

继续阅读

[BZOJ 3252]攻略

近期心情不顺，坑了一堆没写的题解……（嗯我反演等回来再填坑吧（逃

好了还是说说这题吧，私以为鄙人的做法还是蛮妙的：

定义$d(x)$表示$x$到根上所有点的权值和，$d_{max}(x)$为$x$所在的子树中所有点的$d(x)$的最大值。对一个结点，他的所有儿子中$d_{max}(x)$最大的称为重儿子，其他作为轻儿子，然后做一遍树剖。然后将所有重链的权值和扔到一个数组里，降序排序，选前$k$大求和即可（不够的话全选）。

为什么？

显然，尽可能选叶子是划算的。然后，任意一条重链链顶的父亲所在的重链的权值和必定大于该重链，所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并，恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的，所以答案是最优的。

继续阅读

[坑]狄利克雷卷积和反演

开个坑，记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了，就讲讲性质吧。

有几个一定要记住的东西：

\[\mu \ast 1 = e\]

\[\varphi \ast 1 = id\]

\[\mu \ast id = \varphi\]

这几个在推式子的过程中都有很大的作用，务必要记住。

所谓莫比乌斯反演，其实就是：

\[F = f \ast 1\Leftrightarrow f = F \ast \mu\]

（谜之音：其实很多所谓“反演题”都没用到这俩性质啊……）

关于莫比乌斯函数本身，还有一个好康的性质：

\[(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i\]

继续阅读

« 上一页 1 2 3 4 5 6 7 8 9 10 11 12 下一页 »

[BZOJ 3992][SDOI2015]序列统计

[BZOJ 2115][Wc2011]Xor

[BZOJ 2876][NOI2012]骑行川藏

[BZOJ 3925][ZJOI2015]地震后的幻想乡

[BZOJ 1095][ZJOI2007]Hide 捉迷藏

[BZOJ 3295][CQOI2011]动态逆序对

[BZOJ 2733][HNOI2012]永无乡

[BZOJ 1483][HNOI2009]梦幻布丁

[BZOJ 3252]攻略

[坑]狄利克雷卷积和反演

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器