[BZOJ 2321][BeiJing2011集训]星器

物理题可还行(其实我是想学势能方法,然后误入了……

给每个星星(假设他在的位置是\((i, j)\))定义势能\(E_p = i^2 + j^2\),定义势函数\(\Phi(S)\)来表示状态\(S\)时所有星星势能的和。

然后我们发现,当两个星星互相吸引时(假设他们同行,坐标分别为\((i, j)\)和\((i, k)\),且$j<k$),他们的坐标会变为\((i, j + 1)\)和\((i, k - 1)\),势能的总减少量(也就是势函数的减小量)为\(2(k - j - 1)\)。

因此,整个过程中势函数的总减小量,就是答案的两倍。因此算出操作前后的势能做差即可……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
typedef long long ll;
int main() {
  int n, m; scanf("%d%d", &n, &m);
  ll E = 0LL;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      ll delta = i * i + j * j; ll x;
      scanf("%lld", &x); delta *= x;
      E += delta;
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      ll delta = i * i + j * j; ll x;
      scanf("%lld", &x); delta *= x;
      E -= delta;
    }
  }
  E /= 2LL;
  printf("%lld\n", E);
  return 0;
}

[LibreOJ 2562][SDOI2018]战略游戏

aji圆方树毁我青春,,,省选现场看出来是圆方树但写不出点双滚粗。

显然可以割的点是某两个点的某一条简单路径上的割点,然后两点间的简单路劲的并就是圆方树上的路径,割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并,就需要虚树。

然后做完了……直接建圆方树,每次询问建虚树xjb统计即可。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
  for(int i = 0; i < maxn; i ++) {
    G[i].clear();
  }
}
void add_edge1(int u, int v) {
  G[u].push_back(v); G[v].push_back(u);
}

using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
  static std::stack<pii> S;
  pre[x] = ++ dcnt; int low = pre[x];
  int cld = 0;
  for(auto v : G[x]) {
    pii e = std::make_pair(x, v);
    if(!pre[v]) {
      S.push(e); cld ++;
      int lowv = dfs(v, x);
      low = std::min(low, lowv);
      if(lowv >= pre[x]) {
        iscut[x] = true; bcc_cnt ++;
        bcc[bcc_cnt].clear();
        while(true) {
          pii ee = S.top(); S.pop();
          int f = ee.first, g = ee.second;
          if(bccno[f] != bcc_cnt) {
            bccno[f] = bcc_cnt;
            bcc[bcc_cnt].push_back(f);
          }
          if(bccno[g] != bcc_cnt) {
            bccno[g] = bcc_cnt;
            bcc[bcc_cnt].push_back(g);
          }
          if(f == x && g == v) break;
        }
      }
    } else if(pre[v] < pre[x] && v != fa) {
      S.push(e);
      low = std::min(low, pre[v]);
    }
  }
  return low;
}
int n, m;
void calc_bcc() {
  std::fill(pre, pre + 1 + n, 0);
  std::fill(iscut, iscut + 1 + n, false);
  std::fill(bccno, bccno + 1 + m, 0);
  dcnt = bcc_cnt = 0;
  for(int i = 1; i <= n; i ++) {
    if(!pre[i]) dfs(i);
  }
}

std::vector<int> G2[maxn + maxm];
void cz2() {
  for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
  G2[u].push_back(v); G2[v].push_back(u);
}

int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
  printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
  cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
  d[x] = s; anc[x][0] = fa; dep[x] = depth;
  for(auto v : G2[x]) {
    if(v != fa) {
      dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
      siz[x] += siz[v];
    }
  }
}
void process_lca() {
  memset(anc, -1, sizeof(anc));
  cnt2 = 0;
  int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
  printf("s : %d\n", s);
#endif
  for(int j = 1; (1 << j) < s; j ++) {
    for(int i = 1; i <= s; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) anc[i][j] = anc[a][j - 1];
    }
  }
}
int lca(int x, int y) {
  if(dep[x] < dep[y]) std::swap(x, y);
  for(int j = 18; j >= 0; j --) {
    int a = anc[x][j];
    if(a != -1 && dep[a] >= dep[y]) {
      x = a;
    }
  }
  if(x == y) return x;
  for(int j = 18; j >= 0; j --) {
    int a1 = anc[x][j], a2 = anc[y][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      x = a1; y = a2;
    }
  }
  return anc[x][0];
}

void process() {
  calc_bcc();
  cz2();
  for(int i = 1; i <= bcc_cnt; i ++) {
    int id = n + i;
    for(auto u : bcc[i]) {
      add_edge2(u, id);
    }
  }
  process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
  return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
  int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
  int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
  return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
  std::vector<int> V;
  for(int i = 1; i <= sz; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::set<int> ds; ds.insert(V[0]);
  for(int i = 1; i < sz; i ++) {
    ds.insert(V[i]);
    ds.insert(lca(V[i - 1], V[i]));
  }
  V.clear(); for(auto u : ds) V.push_back(u);
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::stack<int> S;
  int ans = 0;
  for(int i = 0; i < V.size(); i ++) {
    int u = V[i];
    while(!S.empty() && !is_anc(S.top(), u)) {
      S.pop();
    }
    if(!S.empty()) {
#ifdef LOCAL
      printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
      ans += get_delta(u, S.top());
    }
    S.push(u);
  }
  for(auto u : ds) {
    if(u <= n) ans ++;
  }
  ans -= sz;
  return ans;
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &m); cz1();
    for(int i = 1; i <= m; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      add_edge1(u, v);
    }
    process();
    int q; scanf("%d", &q);
    while(q --) {
      int sz; scanf("%d", &sz);
      printf("%d\n", query(sz));
#ifdef LOCAL
      fflush(stdout);
#endif
    }
  }
  return 0;
}

[LibreOJ 121]可离线动态图连通性

LCT+扫描线应该随便做吧这题……但我学了一下线段树分治

这个问题有删除非常的恶心,让我们考虑怎么去掉删除的影响。

每条边存在的时间段是一个区间,而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标,对所有询问建线段树,然后对一段区间加边就是一个区间打标记,最后扫一遍线段树就可以解决问题。

同时需要注意,这个题在DFS线段树的过程中,往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩,但是可以按轶合并。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
  Node *fa; int siz;
  Node() {
    fa = NULL; siz = 1;
  }
  void sc(Node *c) {
    siz += c -> siz;
    c -> fa = this;
  }
  void brk() {
    fa -> siz -= siz;
    fa = NULL;
  }
};
Node *r[maxn];
int n;
void init_set() {
  for(int i = 1; i <= n; i ++) {
    r[i] = new Node();
  }
}
Node *get_fa(Node *x) {
  if(x -> fa == NULL) {
    return x;
  } else {
    return get_fa(x -> fa);
  }
}
Node *link_set(Node *x, Node *y) {
  if(x -> siz < y -> siz) std::swap(x, y);
  x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
  return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
  return (get_fa(x) == get_fa(y));
}

const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
  if(ql <= L && R <= qr) {
    event[o].push_back(e);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
    if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
  }
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
  if(L == R) {
    que[o] = e;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      add_query(o << 1, L, M, p, e);
    } else {
      add_query(o << 1 | 1, M + 1, R, p, e);
    }
  }
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
  for(auto e : event[o]) {
    int u = e.first, v = e.second;
    if(!is_same(r[u], r[v])) {
#ifdef LOCAL
      printf("Merging %d and %d.\n", u, v);
#endif
      S.push(std::make_pair(merge_set(r[u], r[v]), o));
    }
  }
  if(L == R) {
    int u = que[o].first, v = que[o].second;
    if(u == -1 && v == -1) {
      ret[L] = -1;
    } else {
      if(is_same(r[u], r[v])) {
        ret[L] = 1;
      } else {
        ret[L] = 0;
      }
    }
  } else {
    int M = (L + R) / 2;
    solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
  }
  while(!S.empty() && S.top().second >= o) {
    Node *u = S.top().first; S.pop();
    u -> brk();
  }
}

std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
  int m; scanf("%d%d", &n, &m);
  init_set();
  pii fl(-1, -1);
  for(int i = 1; i <= m; i ++) {
    pii e; int op;
    scanf("%d%d%d", &op, &e.first, &e.second);
    if(e.first > e.second) {
      std::swap(e.first, e.second);
    }
    if(op == 2) {
      add_query(1, 1, m, i, e);
    } else {
      add_query(1, 1, m, i, fl);
      V.push_back(e);
      if(op == 0) {
        ma[e].push(i);
      } else {
        int last = ma[e].top(); ma[e].pop();
        add_event(1, 1, m, last, i - 1, e);
      }
    }
  }
  for(auto e : V) {
    while(!ma[e].empty()) {
      int g = ma[e].top(); ma[e].pop();
      add_event(1, 1, m, g, m, e);
    }
  }
  solve(1, 1, m);
  for(int i = 1; i <= m; i ++) {
    if(ret[i] != -1) {
      if(ret[i]) {
        puts("Y");
      } else {
        puts("N");
      }
    }
  }
  return 0;
}

[LibreOJ 2558][LNOI2014]LCA

现在才做这题TAT

如果询问的是一个子集和\(z\)的所有LCA的深度的和,那可以把子集里每一个元素到根的路径全部加1,然后根到\(z\)的路径上的和就是答案。

如果是区间的话,每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间,然后离线,给询问排个序然后就好做了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
using ll = long long;
const ll ha = 201314LL;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}

const int maxno = maxn << 2;
ll sumv[maxno], addv[maxno];
void maintain(int o) {
  sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;
}
void paint(int o, int L, int R, ll v) {
  v %= ha;
  addv[o] += v; addv[o] %= ha;
  sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;
}
void pushdown(int o, int L, int R) {
  if(addv[o] != 0LL) {
    ll v = addv[o]; addv[o] = 0;
    int M = (L + R) / 2;
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, L, M, v); paint(rc, M + 1, R, v);
  }
}
int ql, qr; ll v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    paint(o, L, R, v);
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
ll query(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha;
    if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha;
    return ans;
  }
}

int siz[maxn], fa[maxn], dep[maxn], hson[maxn];
void dfs_1(int x, int f = 0, int depth = 0) {
  fa[x] = f; dep[x] = depth; siz[x] = 1;
  int maxs = 0;
  for(auto v : G[x]) {
    if(v != f) {
      dfs_1(v, x, depth + 1);
      siz[x] += siz[v];
      if(siz[v] > maxs) {
        maxs = siz[v]; hson[x] = v;
      }
    }
  }
}
int top[maxn], tid[maxn], dfn[maxn];
void dfs_2(int x, int a) {
  static int cnt = 0; cnt ++;
  top[x] = a; tid[cnt] = x; dfn[x] = cnt;
  if(hson[x]) {
    dfs_2(hson[x], a);
  } else {
    return;
  }
  for(auto v : G[x]) {
    if(v != fa[x] && v != hson[x]) {
      dfs_2(v, v);
    }
  }
}

int n;
void update(int x, int y, const ll &delta) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y]; v = delta;
    modify(1, 1, n); return;
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x]; v = delta;
  modify(1, 1, n);
  update(fa[top[x]], y, delta);
}
ll query(int x, int y) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y];
    return query(1, 1, n);
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x];
  ll ret = query(1, 1, n);
  return (ret + query(fa[top[x]], y)) % ha;
}

struct Q {
  int l, z;
  int id; ll p;
  bool operator <(const Q &res) const {
    if(l == res.l) {
      return id < res.id;
    } else {
      return l < res.l;
    }
  }
};
Q que[maxn << 1];
ll ans[maxn];

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 2; i <= n; i ++) {
    int f; scanf("%d", &f); f ++;
    add_edge(f, i);
  }
  dfs_1(1); dfs_2(1, 1);
  for(int i = 1; i <= q; i ++) {
    int l, r, z; scanf("%d%d%d", &l, &r, &z);
    l ++; r ++; z ++;
    Q &L = que[i * 2 - 1]; Q &R = que[i * 2];
    L.id = R.id = i; L.p = -1; R.p = 1;
    L.z = R.z = z; L.l = l - 1; R.l = r;
  }
  std::sort(que + 1, que + 1 + 2 * q);
  int p = 0;
  for(int i = 1; i <= 2 * q; i ++) {
    const Q &t = que[i];
    while(p < t.l) {
      p ++; update(1, p, 1);
    }
    ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha;
  }
  for(int i = 1; i <= q; i ++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

[LA 5135][WF2011]Mining Your Own Business

点双开坑……

考虑每个点双。如果一个点双有一个(全局的)割点,那么必须要在该点双的一个非割点处建一个出口(否则割掉这个割点会出事)。如果一个点双的割点多于一个,那么其实并没有必要在这里建出口,因为不管割掉那个点,这个点双里面的点总有办法走到一个只有一个割点的点双里。

有一种特殊情况……就是整个图是点双联通的,这样的话随便找两个点建出口就行了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
const int maxn = 100005;
std::vector<int> G[maxn];
int n;
void clear_graph() {
  for(int i = 1; i <= 100000; i ++) {
    G[i].clear();
  }
}
void add_edge(int u, int v) {
  G[u].push_back(v); G[v].push_back(u);
}

std::map<int, int> ma;
int sz;
int trace(int x) {
  if(ma.count(x)) {
    return ma[x];
  } else {
    ma[x] = ++ sz;
    return sz;
  }
}

using Edge = std::pair<int, int>;
int dcnt, bcc_cnt;
int pre[maxn];
bool is_cut[maxn]; int bccno[maxn];
std::vector<int> bcc[maxn];

std::stack<Edge> S;
int dfs(int x, int fa = -1) {
  pre[x] = ++ dcnt; int low = pre[x];
  int cld = 0;
  for(auto v : G[x]) {
    Edge e = std::make_pair(x, v);
    if(!pre[v]) {
      S.push(e); cld ++;
      int lowv = dfs(v, x);
      low = std::min(low, lowv);
      if(lowv >= pre[x]) {
        is_cut[x] = true;
        bcc_cnt ++; bcc[bcc_cnt].clear();
        while(true) {
          Edge ee = S.top(); S.pop();
          int f = ee.first, g = ee.second;
          if(bccno[f] != bcc_cnt) {
            bccno[f] = bcc_cnt; bcc[bcc_cnt].push_back(f);
          }
          if(bccno[g] != bcc_cnt) {
            bccno[g] = bcc_cnt; bcc[bcc_cnt].push_back(g);
          }
          if(f == x && g == v) break;
        }
      }
    } else if(pre[v] < pre[x] && v != fa) {
      S.push(e); low = std::min(low, pre[v]);
    }
  }
  if(fa < 0 && cld == 1) is_cut[x] = false;
  return low;
}
void calc_bcc() {
  std::fill(pre, pre + 1 + sz, 0);
  std::fill(is_cut, is_cut + 1 + sz, false);
  std::fill(bccno, bccno + 1 + sz, 0);
  dcnt = bcc_cnt = 0;
  for(int i = 1; i <= sz; i ++) {
    if(!pre[i]) dfs(i);
  }
}

using ll = long long;
int main() {
  int cs = 0;
  while(scanf("%d", &n) == 1) {
    if(n == 0) break;
    cs ++; sz = 0; ma.clear();
    clear_graph();
    for(int i = 1; i <= n; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      u = trace(u); v = trace(v);
      add_edge(u, v);
    }
    calc_bcc();
    ll a1 = 0, a2 = 1LL;
    for(int i = 1; i <= bcc_cnt; i ++) {
      int cnum = 0;
      for(auto x : bcc[i]) {
        if(is_cut[x]) cnum ++;
      }
      if(cnum == 1) {
        a1 ++;
        a2 *= (ll(bcc[i].size() - 1));
      }
    }
    if(bcc_cnt == 1) {
      a1 = 2; ll s = bcc[1].size();
      a2 = s * (s - 1LL) / 2LL;
    }
    printf("Case %d: %lld %lld\n", cs, a1, a2);
  }
  return 0;
}

[UOJ 195][ZJOI2016]大♂森林

ETT野蛮,LCT文明,,,

换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点,每个实点(就是在树中真实存在的点)向他之前最晚建立的一个虚点认父。

然后虚点初始的时候应该向上一次的那个虚点认父(我们可以近似的认为第一个虚点就是1)。然后我们用类似于扫描线的做法,等到了虚点存在的区间里就把它爸爸改成相应的实点,出去了相应区间之后就再改回来。这样这题就很好做了,我们认为虚点点权为0,实点点权为1,然后查询就好做了。

然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理,因为同一个编号的结点一定分布编号连续的一段树里,所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。

再有一点就是查询的时候……如果直接查询两点间splay的和的话,可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离,再用LCA去掉不需要的。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
  Node *fa, *ch[2];
  int val, sumv;
  bool rev;
  int d() {
    return ((this == fa -> ch[1]) ? 1 : 0);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c;
    c -> fa = this;
  }
  void maintain() {
    sumv = ch[0] -> sumv + ch[1] -> sumv + val;
  }
  void paint() {
    rev = !rev;
    std::swap(ch[0], ch[1]);
  }
  void pushdown() {
    if(rev) {
      ch[0] -> paint();
      ch[1] -> paint();
      rev = false;
    }
  }
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
  nil = cur = pool;
  nil -> val = nil -> sumv = 0;
  nil -> rev = false;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
  x -> val = x -> sumv = val;
  x -> rev = false;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
  return x;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  Node *y = x -> fa; int d = x -> d();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  y -> sc(x -> ch[1 ^ d], d);
  x -> sc(y, 1 ^ d);
  y -> maintain(); x -> maintain();
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) y -> fa -> pushdown();
    y -> pushdown(); x -> pushdown();
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
  // x -> maintain();
}
Node *access(Node *x) {
  Node *nx = x, *y = nil;
  Node *ct = T(1);
  while(x != nil) {
    splay(x); x -> pushdown();
    if(x -> fa == nil) ct = x;
    x -> sc(y, 1); x -> maintain();
    y = x; x = x -> fa;
  }
  splay(nx); return ct;
}
Node *evert(Node *x) {
  access(x); x -> paint();
  return x;
}
void link(Node *x, Node *y) {
  evert(x); x -> fa = y;
}
void cut(Node *x) {
  access(x);
  x -> ch[0] -> fa = nil;
  x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
  evert(x); access(y);
  int d = x -> d();
  y -> ch[d] = nil; y -> maintain();
  x -> fa = nil;
}

int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
  if(a > x) {
    std::swap(a, x), std::swap(b, y);
  }
  if(b < x) return std::make_pair(n + 1, n + 1);
  if(b >= y) return std::make_pair(x, y);
  return std::make_pair(x, b);
}

int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
  freopen("forest1.in", "r", stdin);
  freopen("out", "w+", stdout);
#endif
  int m; scanf("%d%d", &n, &m);
  init_pool(); refresh(T(1), 1);
  int cnt0 = 1, cnt1 = 0, cnt2 = 0;
  Node *last1 = T(1);
  seg[1][0] = 1; seg[1][1] = n;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
    if(ope[i][0]) {
      scanf("%d", &ope[i][3]);
    }
    if(ope[i][0] == 0) {
      int c = ++ cnt0;
      refresh(T(c), 1);
      link(last1, T(c));
      seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
      printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
    } else if(ope[i][0] == 1) {
      Node *n1 = T(m + i);
      refresh(n1); link(n1, bef[i] = last1);
      int l = ope[i][1], r = ope[i][2], x = ope[i][3];
      auto s = seg_and(l, r, seg[x][0], seg[x][1]);
      l = s.first, r = s.second;
#ifdef LOCAL
      printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
      beg[l].push_back(i); end[r + 1].push_back(i);
      last1 = n1;
    } else {
      int x = ope[i][1], u = ope[i][2], v = ope[i][3];
      query[x].push_back(i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(auto id : end[i]) {
      Node *n1 = T(m + id);
      cut(n1, T(ope[id][3])); link(n1, bef[id]);
    }
    for(auto id : beg[i]) {
      Node *n1 = T(m + id);
      cut(n1, bef[id]); link(n1, T(ope[id][3]));
    }
    for(auto id : query[i]) {
      int u = ope[id][2], v = ope[id][3];
      evert(T(1)); access(T(u));
      int ret = T(u) -> sumv;
      Node *lca = access(T(v));
      ret += T(v) -> sumv;
      access(lca);
      ret -= lca -> sumv;
      ret -= lca -> sumv - 1;
      ans[id] = ret - 1;
    }
  }
  for(int i = 1; i <= m; i ++) {
    if(ope[i][0] == 2) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}

[UOJ 113][UER #2]手机的生产

神哎……

既然与的优先级比或高,那么我们就可以用或把程序切成若干段,每一段的值决定了最后的取值。

考虑从左往右计算某一段。如果有一个手机某一段运算结果为0,那么它会继续往下运算,反之则会停止运算。

对于每一个在前\(i\)段的值都是0,然后开始跑第\(i + 1\)段的手机。他们都会额外产生\(l\)(这一段的fork个数)个手机,并且由于这些手机一被生产出来的返回值就是0,所以新的这些手机在这一段取值为0。而原来的老手机,在这一段的取值事1,于是之后的运算就不会接着做了。

这样一来,我们就可以动态维护在之前的段里的返回值全是0的手机,然后就可以做了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 100005;
const ll ha = 998244353LL;

bool op[maxn];
int main() {
  std::vector<int> vec;
  int last = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= (n - 1); i ++) {
    char buf[5]; scanf("%s", buf);
    if(buf[0] == '|') {
      vec.push_back(i - last);
      last = i;
    }
  }
  vec.push_back(n - last);
  ll pre0 = 1LL;
  ll ans = 1LL;
  for(auto x : vec) {
    ans += (pre0 * (ll(x))) % ha; ans %= ha;
    pre0 = (pre0 * (ll(x))) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}

[UOJ 48][UR #3]核聚变反应堆

先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd,然后在除掉一个最小的质因子即可。

那么我们先把\(a_1\)分解质因数,然后所有数和它求一个gcd,然后去去掉一个尽可能小的质因子。注意到一个数\(p\)的质因子数量是\(O(\log p)\)级别的,所以每一个数找到要除的那个最小的质因子只需要\(O(\log a_1)\)的时间。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
const int maxn = 100005;
using ll = long long;
ll V[maxn]; int vcnt = 0;
void des(ll x) {
  ll m = (ll)sqrt(x + 0.5);
  for(ll i = 2; i <= m; i ++) {
    if(x % i == 0) {
      V[vcnt ++] = i;
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1LL) V[vcnt ++] = x;
}
ll gcd(ll a, ll b) {
  if(!b) return a;
  else return gcd(b, a % b);
}

ll A[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
  }
  des(A[1]);
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    ll bs = gcd(A[i], A[1]);
    if(bs == 1) {
      printf("-1"); continue;
    }
    for(int j = 0; j < vcnt; j ++) {
      if(A[i] % V[j] == 0) {
        bs /= V[j];
        break;
      }
    }
    printf("%lld", bs);
  }
  puts("");
  return 0;
}

[CF 618F]Double Knapsack

我zzs就算掉光rating,R2爆炸,也不会做你们半道构造题!

啊构造题真好玩(一转)。

不妨钦定\(A\)中所有元素的和不大于\(B\)的。然后把两个集合按照任意顺序搞成一个序列,然后求出两者的前缀和\(SA\)和\(SB\)。

考虑对于0...n的\(SA_i\),找出\(SB\)中不大于他的数中最大的一个(不妨设为\(SB_j\)),可以发现有\(0\leq SA_i - SB_j\leq n - 1\)(不然\(j\)还能再大)。然后发现:我们处理的\(i\)和\(j\)的数对有\(n + 1\)组,但是\(SA_i - SB_j\)的取值却只有N种!也就是说一定存在\(i\neq i'\)且\(j\neq j'\)满足\(SA_i - SB_j = SA_{i'} - SB_{j'}\)。

我们找出两对这样的数对,移一下项就可以构造一组解了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
using pii = std::pair<int, int>;
int n;
void gen_S(int *arr, ll *S) {
  S[0] = 0LL;
  for(int i = 1; i <= n; i ++) {
    S[i] = (S[i - 1] + (ll(arr[i])));
  }
}

const int maxn = 1000005;
std::vector<pii> cs[maxn];
int main() {
  scanf("%d", &n);
  int *A = (int*)calloc(n + 1, sizeof(int));
  int *B = (int*)calloc(n + 1, sizeof(int));
  ll sum_A = 0LL, sum_B = 0LL;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); sum_A += A[i];
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]); sum_B += B[i];
  }
  bool flip = false;
  if(sum_A > sum_B) {
    flip = true;
    std::swap(A, B);
    std::swap(sum_A, sum_B);
  }
  ll *SA = (ll*)calloc(n + 1, sizeof(ll));;
  ll *SB = (ll*)calloc(n + 1, sizeof(ll));;
  gen_S(A, SA); gen_S(B, SB);
  for(int i = 0; i <= n; i ++) {
    int j = std::upper_bound(SB, SB + n + 1, SA[i]) - SB - 1;
    ll val = SA[i] - SB[j];
    cs[val].push_back(std::make_pair(i, j));
  }
  int l1, r1, l2, r2;
  for(int i = 0; i < n; i ++) {
    if(cs[i].size() > 1) {
      int i1 = cs[i][0].first;
      int j1 = cs[i][0].second;
      int i2 = cs[i][1].first;
      int j2 = cs[i][1].second;
      if(i1 > i2) {
        std::swap(i1, i2);
        std::swap(j1, j2);
      }
      l1 = i1; r1 = i2;
      l2 = j1; r2 = j2;
      break;
    }
  }
  if(flip) {
    std::swap(l1, l2);
    std::swap(r1, r2);
  }
  printf("%d\n", r1 - l1);
  for(int i = l1 + 1; i <= r1; i ++) {
    if(i > l1 + 1) putchar(' ');
    printf("%d", i);
  }
  putchar('\n');
  printf("%d\n", r2 - l2);
  for(int i = l2 + 1; i <= r2; i ++) {
    if(i > l2 + 1) putchar(' ');
    printf("%d", i);
  }
  putchar('\n');
  free(A); free(B);
  free(SA); free(SB);
  return 0;
}

[UOJ 21][UR #1]缩进优化

神题啊……

考虑让答案最小不好做,那么我们想,把连续的一段空格变成一个TAB(假设TAB长度为\(x\))就是减少\(x - 1\)空格,那么我们尝试去最大化减小的空格的量。

然后考虑枚举\(x\)是啥,然后去算减少的空格的量。对于任意\(a_i\),减少的空格量就是\((x-1)\lfloor\frac{a_i}{x}\rfloor\),这似乎可以整除分块哎……

但是会被T掉。我们想,其实我们对任意\(x\),我们去枚举\(\lfloor\frac{a_i}{x}\rfloor\)就行啦,要查询满足条件的\(a_i\)数量可以预处理一个权值前缀和然后就能\(O(1)\)做啦、

假设\(X = \max\{a_i\}\),那么每一个\(x\)对时间复杂度的贡献就是\(O(\frac{X}{x})\)。这不就是调和级数吗?所以时间复杂度事\(O(X\ln X)\)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
const int maxn = 1000005;
typedef long long ll;
int a[maxn], C[maxn];
int n, bd;
void process() {
  for(int i = 1; i <= n; i ++) {
    C[a[i]] ++;
  }
  for(int i = 1; i <= bd; i ++) {
    C[i] += C[i - 1];
  }
}
ll sum;
ll query(int x, int p) {
  int l = x * p;
  int r = x * (p + 1) - 1;
  if(r > bd) r = bd;
  return (C[r] - C[l - 1]);
}
ll calc(int x) {
  ll delta = 0;
  for(int i = 1; i <= (bd / x); i ++) {
    ll cnt = query(x, i);
    delta += (ll(i)) * cnt * (ll(x - 1));
  }
#ifdef LOCAL
  printf("ans of %d : %lld\n", x, sum - delta);
#endif
  return (sum - delta);
}

int main() {
  scanf("%d", &n);
  sum = 0LL; bd = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &a[i]);
    bd = std::max(bd, a[i]);
    sum += a[i];
  }
  process();
  ll ans = sum;
  for(int i = 1; i <= bd; i ++) {
    ans = std::min(ans, calc(i));
  }
  printf("%lld\n", ans);
  return 0;
}