2021-9-20 Test

发表于

100 + 100 + 0
中间好像摆了不少时间，导致没有深入思考 T3
T1 做到快下考，其实根本不难写，但怕翻车写了比正解还长的暴力并拍了很久

common

一棵以 rtrt 为根的树，点带权，定义 sumisum_i 表示点 ii 为根的子树 内权值和，两种操作：1. 单点修改 2. 求 ∑i=lrsumi\sum\limits_{i=l}^r sum_i

n,m≤1×105n,m\le 1\times 10^5

Sol:

~没有看错，是子树内权值和~

首先能得出一个十分 naivenaive 的暴力，使用 BITBIT 单点修改，再暴力的处理询问，这样修改复杂度 O(log⁡n)\mathrm O(\log n) ，询问复杂度 O(n×log⁡n)\mathrm O(n \times \log n)

如果你看到 7070 分暴力忍不出了开始 rushrush ，没准你就走上了错误的道路

然后我们发现修改快的像正解，而询问有亿点点慢，于是我们考虑一个经典套路 – 根号平衡

把原点序列分个块，再预处理出每个点在每个块的影响力，就可以 O(log⁡nn\mathrm O(\log n \sqrt n 查询， O(nlog⁡n)\mathrm O(\sqrt n \log n) 修改乐。

/* ==============================
 *  Author : Odalys 
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
  T w=1; a=0;
  char ch=getchar();
  for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
  for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
  a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define int unsigned int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int> 
#define vi vector<int> 
#define wife puts("MckennaGrace")
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e5 + 10;
struct edge {
  int to, nxt;  
} e[N << 1];
int head[N], cnt, val[N];
inline void add (int u, int v) {
  e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}

int n, m, rt;
int dfn[N], dfntot, low[N];
struct BIT {
  int sum[N];
  inline void upd (int x, int v) { 
    for (int i = x; i <= n; i += (i & (-i))) 
      sum[i] += v; 
    }
  inline int ask (int x) { 
    int Ans = 0; 
    for (int i = x; i; i -= (i & (-i))) Ans += sum[i]; 
    return Ans; 
  }
} tr; 
int Sum[N];
void dfs (int u, int fa) {
  dfn[u] = ++dfntot;
  Sum[u] = val[u]; 
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa) continue;
    dfs(v, u); 
    Sum[u] += Sum[v];
  }
  low[u] = dfntot;
} 
int bel[N], siz, blo, Ans[N];
int To[N][318];
void dfs1 (int u, int fa) {
  To[u][bel[u] - 1]++;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa) continue;
    For (j, 0, blo - 1) 
      To[v][j] += To[u][j];
    dfs1(v, u); 
  }
}

inline void work (int u, int v) {
  For (i, 0, blo - 1) {
    int x = To[u][i];
    Ans[i + 1] += x * (v - val[u]);
  }
  tr.upd(dfn[u], v - val[u]);
  val[u] = v;
}

inline int sol (int l, int r) {
  int ret = 0;
  //if (bel[l] < bel[r]) return 0;
  if (bel[l] == bel[r]) {
    For (i, l, r) 
      ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1);
    return ret;	
  }
  For (i, bel[l] + 1, bel[r] - 1)
    ret += Ans[i];
  For (i, l, min(n, bel[l] * siz))
    ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1);
  For (i, (bel[r] - 1) * siz + 1, r)
    ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1); 

  return ret;
}

signed main() {
  read(n), read(m);
  For (i, 1, n) read(val[i]);
  For (i, 1, n) {
    int u, v; read(u); read(v);
    if (!u) rt = v;
    else add(u, v), add(v, u); 
  }
  dfs(rt, 0); 
  For (i, 1, n) 
    tr.upd(dfn[i], val[i]); 
  siz = sqrt (n), blo = n / siz;
  for (int i = 1; i <= blo; ++i) 
    For (j, (i - 1) * siz + 1, i * siz) 
      bel[j] = i, Ans[i] += Sum[j];
  if (blo * siz < n){
    For (i, blo * siz + 1, n) bel[i] = blo + 1;
    blo++;
  }
  dfs1(rt, 0);
  //For (i, 1, n) 
  //	Debug(dfn[i]), Debug(low[i]); 
  //For (i, 1, n)
  //	cout << bel[i] << " " ;
  //puts("");
  while (m--) {
    int opt, u, v; read(opt); read(u); read(v);
    if (opt == 1) 
      work (u, v);		
    else 
      printf ("%llu\n", sol(u, v));
  }
  return 0;
  
}

art

kn,mk_{n,m} ，求生成树个数

n,m≤1×1018n,m\le 1\times 10^{18}

Sol:

这个 n,mn,m 范围一看就有结论啦

使用 matrix treematrix\ tree 玩一玩矩阵可得到结论

Ans=nm−1×mn−1Ans = n^{m-1} \times m^{n-1}

注意到 n,mn,m 一乘就爆 ll 于是要使用龟速乘

hands

从 (0,0)(0,0) 出发，每次可前往 (u+Ax,v+Ay)/(u+Bx,v+By)(u+Ax, v+Ay) / (u+Bx, v+By) ，问到 (n,m)(n,m) 的方案数

n,m≤500,∣Ax∣,∣Ay∣,∣Bx∣,∣By∣≤500n,m\le 500, |Ax|,|Ay|,|Bx|,|By|\le 500

Sol:

乍一看像是 iodwadiodwad 出过的题
实际上也是的
虽然这玩意可以走负的，但把这两种走法看做两个向量，题目保证这两个向量不平行，也就意味着这两个向量可以张成所有点，于是转换一下坐标就是那道题了。