说什么呢，还是自己菜啊
【打表】C. Meaningless Operations
题目大意
求$f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.$
$2 \le a_i \le 2^{25} - 1$
题目分析
题挺有意思的。其中对于$2^x-1$打表。
附上有理有据的tutorial.
【思维题】E. Magic Stones
题目大意
每次可选择一个三元组$(c_{i-1},c_i,c_{i+1})$，将其变为$(c_{i-1},c_{i-1}-c_i+c_{i+1},c_{i+1})$.问序列$a[]$能否变为$b[]$
题目分析
没救了，以前做过一道$(c_{i-1}+c_i,-c_i,c_i+c_{i+1})$的题，居然考试时候没看出来是一样思路。
考虑构造差分数组：发现$a[]$能够成为$b[]$当且仅当两数组的差分数组$a'[1]=b'[1]$且$a'[2...n]$和$b'[2...n]$排序后相等。
1 #include2 const int maxn = 100035; 3 4 int n,a[maxn],b[maxn]; 5 6 int read() 7 { 8 char ch = getchar(); 9 int num = 0, fl = 1;10 for (; !isdigit(ch); ch = getchar())11 if (ch=='-') fl = -1;12 for (; isdigit(ch); ch = getchar())13 num = (num<<1)+(num<<3)+ch-48;14 return num*fl;15 }16 int main()17 {18 n = read();19 for (int i=1; i<=n; i++) a[i] = read();20 for (int i=1; i<=n; i++) b[i] = read();21 for (int i=n; i>=1; i--)22 a[i] -= a[i-1], b[i] -= b[i-1];23 if (a[1]!=b[1]) puts("No");24 else{25 std::sort(a+1, a+n+1);26 std::sort(b+1, b+n+1);27 for (int i=1; i<=n; i++)28 if (a[i]!=b[i]){29 puts("No");30 return 0;31 }32 puts("Yes");33 }34 return 0;35 }
【数据结构】F. Nearest Leaf
题目大意
有一颗编号为dfs序的树。询问q次点v到编号为l...r之间的叶子的最短距离。$3 \leq n \leq 500\,000, 1 \leq q \leq 500\,000$
题目分析
感觉和[LNOI2014]LCA一定程度有些异曲同工之妙。
建立线段树表示树上每一个节点到点$x$的距离。之所以这样表示，是因为方便在树上转移这颗线段树。考虑边$(u,v,w)$，那么转移到$v$时，所有$v$一侧的节点距离都应减去$w$；同时$u$一侧的节点距离都加上$w$。（出题人非常良心地提供了编号=dfs序的数据好评）因此发现只需要一个支持区间加和区间最小值的线段树即可。
1 #include2 typedef long long ll; 3 const int maxn = 500035; 4 const int maxq = 500035; 5 const int maxm = 1000035; 6 const ll INF = 1e16; 7 8 struct QRs 9 { 10 int l,r,id; 11 QRs(int a=0, int b=0, int c=0):l(a),r(b),id(c) {} 12 }; 13 struct node 14 { 15 ll mn,add; 16 }f[maxn<<2]; 17 struct Edge 18 { 19 int v,val; 20 Edge(int a=0, int b=0):v(a),val(b) {} 21 }edges[maxm]; 22 int n,q; 23 int size[maxn]; 24 ll ans[maxq],val[maxn]; 25 int edgeTot,head[maxn],nxt[maxm],deg[maxn]; 26 std::vector qr[maxn]; 27 28 int read() 29 { 30 char ch = getchar(); 31 int num = 0, fl = 1; 32 for (; !isdigit(ch); ch = getchar()) 33 if (ch=='-') fl = -1; 34 for (; isdigit(ch); ch = getchar()) 35 num = (num<<1)+(num<<3)+ch-48; 36 return num*fl; 37 } 38 void write(ll x){ if (x/10) write(x/10);putchar(x%10+'0');} 39 void addedge(int u) 40 { 41 int v = read(), c = read(); 42 ++deg[u], ++deg[v]; 43 edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot; 44 edges[++edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot; 45 } 46 void dfs1(int x, int fa, ll d) 47 { 48 size[x] = 1; 49 if (x!=1&°[x]==1) val[x] = d; 50 else val[x] = INF; 51 for (int i=head[x]; i!=-1; i=nxt[i]) 52 { 53 int v = edges[i].v; 54 if (v!=fa) dfs1(v, x, d+edges[i].val), size[x] += size[v]; 55 } 56 } 57 void pushup(int rt) 58 { 59 f[rt].mn = std::min(f[rt<<1].mn, f[rt<<1|1].mn); 60 } 61 void pushdown(int rt) 62 { 63 if (f[rt].add){ 64 f[rt<<1].mn += f[rt].add, f[rt<<1|1].mn += f[rt].add; 65 f[rt<<1].add += f[rt].add, f[rt<<1|1].add += f[rt].add; 66 f[rt].add = 0; 67 } 68 } 69 void build(int rt, int l, int r) 70 { 71 if (l==r){ 72 f[rt].mn = val[l]; 73 return; 74 } 75 int mid = (l+r)>>1; 76 build(rt<<1, l, mid); 77 build(rt<<1|1, mid+1, r); 78 pushup(rt); 79 } 80 void update(int rt, int L, int R, int l, int r, int c) 81 { 82 if (L > R) return; 83 if (L <= l&&r <= R){ 84 f[rt].mn += c, f[rt].add += c; 85 return; 86 } 87 int mid = (l+r)>>1; 88 pushdown(rt); 89 if (L <= mid) update(rt<<1, L, R, l, mid, c); 90 if (R > mid) update(rt<<1|1, L, R, mid+1, r, c); 91 pushup(rt); 92 } 93 ll query(int rt, int L, int R, int l, int r) 94 { 95 if (L <= l&&r <= R) return f[rt].mn; 96 ll mid = (l+r)>>1, ret = INF; 97 pushdown(rt); 98 if (L <= mid) ret = query(rt<<1, L, R, l, mid); 99 if (R > mid) ret = std::min(ret, query(rt<<1|1, L, R, mid+1, r));100 return ret;101 }102 void dfs2(int x, int fa)103 {104 for (int i=0, mx=qr[x].size(); i
END